pekempelog

ペケンペイのブログ

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 log2 n) だが,少し工夫すると O(n log n) になる。多分 100pts は O(n log n) のためなんだろうけど,変な O(n log2 n) が通ってるように見えるな。

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

ちなみに自分のコードは T=5, N=106, K=106 だと 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