■ [CodeChef]March Challenge 2015 
http://www.codechef.com/MARCH15
使える時間が 週末×1 だけでは難問まで手が出せなくてつらい…
Chef and Notebooks(CNOTE)
やる
http://www.codechef.com/viewsolution/6418160
Sign Wave(SIGNWAVE)
実験すると規則性がわかる
2問目からやたら難易度上がって面食らった
http://www.codechef.com/viewsolution/6419514
Devu and his Class(DEVCLASS)
type=0はハミング距離数えるだけ
type=1は前から順に近いところへ移動させれば良い
type=2は1つずつ移動させることを考えたらtype=1と同じ
http://www.codechef.com/viewsolution/6421521
Count Substrings(STRSUB)
end[i] = i文字目から end[i] 文字目までに含まれる0の数と1の数がともにK以下であるような最大の整数
とする。これは尺取りっぽくやると O(N+K) で全体が求められる。また、endについて累積和を計算しておく。
end[mid] <= R かつ end[mid+1] > R となるmidを二分探索で求める。
[L,mid]の範囲の位置を左端とする文字列に関して数えるべきものの個数は、end[L]からend[mid]までの和からわかり、これは累積和を使って O(1)
[mid+1,R]に関しては、 1 + 2 + ... + R-mid なので O(1)
http://www.codechef.com/viewsolution/6418577
Sereja and Random Array(SEAPROAR)
線形合同法かどうかを判定する。
線形合同法の下位16bit目は2^17の周期でループし、かつXとしての周期は2^32なので、
下位16bit目の出現列としてあり得るものは全て、適当なseedから始めて得られた長さ2^17のビット列に含まれる
入力の先頭500文字がその中に出現するかを調べると良い（ローリングハッシュを使った）
http://www.codechef.com/viewsolution/6433305
Matrix(MTRWY)
逆からUnion-Find
http://www.codechef.com/viewsolution/6420460
Chef and Problems(QCHEF)
平方分割
http://www.codechef.com/viewsolution/6479333
Counting on a Tree(TREECNT2)
思いつかず
部分点だけならてきとーにやればできるんではと思ったが面倒になってしまった
Z≤10^6 なので各エッジは素因数を高々7個しか持たない、といったあたりがキーなのかな
Random Number Generator(RNG)
きたまさ法やって O(k^2 logN) で部分点
FFTとかで O(k logk logN) にできれば100点なんでしょう
http://www.codechef.com/viewsolution/6517890
Embedding(EMBED:タイブレーク)
時間なかったので着手せず
とりあえずハード制約だけ満たすものを作って、
Nが小さいものから焼きなましてく感じかな
評価基準は各ケースの絶対スコアの単純合計なので、点数を取れるケースでたくさん取るのがきっと重要
結果
- 710pts/1000pts
- 97位/5847人
