■ [CodeChef]Februray Challenge 2015
これがchef longのガチ問か
Chef and Chain(CHEFCH)
010101... とxorをとってbitcount
http://www.codechef.com/viewsolution/6128122
Chef and Equality(CHEFEQ)
最頻値の個数を数える
http://www.codechef.com/viewsolution/6128251
Let us play with rank list(RANKLIST)
与えられた制約の下でのranklist中の値が取り得る最大値を二分探索
http://www.codechef.com/viewsolution/6128614
Chef and Strange Formula(STFM)
Σ_{i<=x}i・i! と xΣ_{i<=x}i に分けて考える。
後者は O(1) だし、
前者は、 i>=M の項は mod M で0だから考えなくて良いので前計算できる
http://www.codechef.com/viewsolution/6129545
Chef and Strings(STRQ)
memo[i][j][k] := i文字目までで文字jの後に文字kが出てくる組み合わせの個数
count[i][j] := i文字目までで文字jが出てくる個数
こいつらを最初にDPで求めておくと各クエリ O(1) で組み合わせ数を計算できる
http://www.codechef.com/viewsolution/6130140
Time to Study Graphs with Chef(CHEFGRPH)
追加のedgeが貼られる頂点があるlayerだけ特別に計算する
http://www.codechef.com/viewsolution/6132411
Xor Matrix(XRMTRX)
実験するとわかる
たくさん場合分けしてしまったけれどもっと綺麗な方法はありそう
http://www.codechef.com/viewsolution/6135507
Devu and Locks(DEVLOCK)
ふつうにDPすると O(P^2 M^3) になる。少し定数倍高速化して60点
FFTかも、というのは感じていたが、その方向だとどっちにしろ難しそう(FFT書いたことない)なので
埋め込みできないかなーとかそんなことを考えていた
http://www.codechef.com/viewsolution/6158495
Payton numbers(CUSTPRIM)
小さいケースで実験してみたり、
簡単に表せる形にならないか各要素を足し引きしてみたりしたが
まったくわからなかった
Jigsaw Puzzle Solving(CHPUZZLE:タイブレーク)
密度が高い順にピースを並べて、最初に見つかった置けるところに置いていくだけ
もっと取り組む時間があれば小さいケースでは評価関数定めてビームサーチしてたのだが
問題としてはかなりバランスの良いものだったと思う
66.2pts
http://www.codechef.com/viewsolution/6283013
結果
- 826.155pts/1000pts
- 26位/7008人