CodeChef March Challenge 2018

PSHTRG

Q=1 で考えてみよう。これは，数列をソートして最大 3 つを見る，それで駄目なら次の 3 つを見るというのを繰り返すことで求められる。この繰り返しが O(log max a) 回しか起きないことに気がつくと，50th max 程度まで保持するセグメント木があれば解けることがわかる。最悪ケースはフィボナッチ数列だろう。

実装：https://gist.github.com/pekempey/829c0d930e2a992a2041e8f363d2f8be

CHEFKNN

最終的な結果が K 色を含むようなものの総数は，第一種スターリング数によって S(N+1, N+1-K) と表せる。自分はこの事実に実験で気がついたが，おそらくは組合せ論的に導けるものなのだろう。この事実に気がつければ，やるべきことは第一種スターリング数の計算の高速化のみとなる。第一種スターリング数は rising factorial の展開係数として現れるので rising factorial を高速に展開すればよい。分割統治でやると O(n log² n) だが，少し工夫すると O(n log n) になる。多分 100pts は O(n log n) のためなんだろうけど，変な O(n log² n) が通ってるように見えるな。

実装：https://gist.github.com/pekempey/eeadc0c5306db890a8d9a742d2f433fd

ちなみに自分のコードは T=5, N=10⁶, K=10⁶ だと 5 sec 以上かかる。T=4 ですら 5 sec 以上掛かる。明らかに最悪ケースが入っていない。展開時の係数を求める際に，具体値を求めて係数表現に戻すという方法もあるらしい。これなら FFT 1 回でいいし速そう。

CUTTREE

与えられたスコアは，頂点 u と頂点 v が連結ならば 1 増えるようなスコアと言い換えられる。これに気がつけば部分点がとれる。満点解法はこれを高速化するだけである。高速化するには距離が等しい頂点対をまとめて計算すればよい。距離 d の頂点対の総数を計算するには重心分解と畳み込みが使える。これを求め終わった後に，もう一度畳み込みを行って最終的な答えを得る。しかしこの畳み込みは任意 mod のものである。任意 mod の畳み込みは様々な方法があって，Karatsuba 法や NTT 9 回，FFT 4 回などがある。

実装：https://gist.github.com/pekempey/4782989f6417ad6de97a6864ca33e39f

公式解説

March 2018: Questions Tagged With march18 - CodeChef Discuss
CHEFKNN: CHEFKNN - Editorial - CodeChef Discuss
CHEFTREE: CUTTREE - Editorial - CodeChef Discuss