■ [CodeChef]January Challenge 2015 
2年ぶりくらいに参加した。
このコンテスト形式、マイペースに取り組めて良いので今後も出ようと思う。
Chef and Stones(CHEFSTON)
やる
http://www.codechef.com/viewsolution/5713322
Gcd Queries(GCDQ)
配列を前から見ていった累積GCDと後ろから見ていった累積GCDを覚えておく
http://www.codechef.com/viewsolution/5713655
Sereja and Votes(SEAVOTE)
取り得る和の上限と下限を求める
http://www.codechef.com/viewsolution/5713840
One Dimensional Kingdoms(ONEKING)
よくあるGreedy
最初、区間の開始・終了をオブジェクトとしてソートしていたらTLEした
座標の範囲が狭かったので座標をキーにしてソート無しでやった
http://www.codechef.com/viewsolution/5714255
Chef and A Large Permutation(CLPERM)
実装も知識も無く考察のみで解ける愉快な問題
存在するカードを昇順に並べた配列をBとする。
B_1〜B_n のカードを使って S=ΣB_i(1<=i<=n) までの全ての整数を表せるとすると、B_n+1 を考えると次のようになる
- B_n+1 <= S+1 の場合
- B_1〜B_n+1 のカードを使って ΣB_i(1<=i<=n+1) までの全ての整数を表せる
- B_n+1 > S+1 の場合
- S+1が表せない
これをそのままやるとO(N-K)だが、カードの数が連続している範囲をまとめて処理するとO(K)になる
http://www.codechef.com/viewsolution/5717846
Queries on the String(QSET)
count[x][y] := (文字列先頭からx文字目まで見たときの数値 % 3 == y) ? 1 : 0
上記の値をSegmentTreeで管理する
この問題が今回の中で一番難しかった気がする
http://www.codechef.com/viewsolution/5716782
Xor Queries(XRQRS)
永続SegmentTree
xor最大化やk-th smallestのクエリに対しては、上から1bitずつ決めていく
http://www.codechef.com/viewsolution/5867272
Sereja and LCM(SEALCM)
D（なぜかコード中ではUという名前にしてしまった）を素因数の冪に分解して、包除原理で補集合の要素数を求める
http://www.codechef.com/viewsolution/5872152
Ranka(RANKA)
白を下から埋めていく→黒を1つ置いて白を全滅させる
を繰り返す
黒が最後まで行ったらいったん黒を全滅させ、盤面を90度回転させた形で同様のことをやる
http://www.codechef.com/viewsolution/5873615
Sereja and Number Division 2(SEAND2:タイブレーク)
焼きなましただけ
ΣB の値が大きいケースに長く時間をかけるようにした
http://www.codechef.com/viewsolution/5729963
CodeChefではJavaはC++の2倍時間を使えるけど、有利なのかどうかはよくわからない
結果
- 10問中10問AC
- 14位/7943人
