■ [CodeChef] June Challenge 2017 
https://www.codechef.com/JUNE17/
A Good Set (GOODSET)
500,499,498,... を出力する
https://www.codechef.com/viewsolution/14009670
Xenny and Coin Rankings (XENRANK)
やる
https://www.codechef.com/viewsolution/14009805
Chef and the Feast (NEO01)
大きい値のものから順に、まとめた方が得する限りまとめる。それ以外は1つずつ使う
https://www.codechef.com/viewsolution/14213083
Pairwise union of sets (UNIONSET)
K/2より大きい集合はBitSetで、小さい集合は配列で持つ
len1 + len2 + .. + lenN ≤ 10000 の制約があるのでこれで速くなる
https://www.codechef.com/viewsolution/14013196
Triplets (SUMQ)
ソートしてしゃくとりっぽく
https://www.codechef.com/viewsolution/14012356
Chef and Prime Queries (PRMQ)
永続segtreeで殴った
https://www.codechef.com/viewsolution/14213423
Cloning (CLONEME)
まともにやったら判定できる気がしないのでハッシュ的な方法を使う。
累積和・累積二乗和、kビット目だけの累積和・いろんな素数でmodの累積和 を持っておく。
二つの範囲で、すべての値が一致していたら完全一致と判定する。
そうでない場合、食い違いが1個だと仮定すると、累積和と累積二乗和の差から、ひとつめの範囲にのみ含まれる値 x とふたつめの範囲にのみ含まれる値 y がわかるので、これが他の累積和たちと矛盾しないかを確認する。
矛盾しない場合、両方の範囲の中にxとyの間の値が存在しないことが必要なので、それを永続segtreeを使って確認する。
https://www.codechef.com/viewsolution/14212683
Euler Sum (ES)
eを有理数で近似する。
A * e = B + ε (0 <= ε << 1) のとき、e = B / A と思うと1〜Aまでの floor(i * e) の和は、算数をするとO(1)で求まる。
AとしてN以下でできるだけ大きいものを取る。i > A については、 i = A + j と分解すると、N -A についての問題に帰着されるので再帰的に解く。
そのようなAはどうやって見つけるかというと、まず100くらいまで探索して、整数よりちょっと大きくなる係数Pと、整数よりちょっと小さくなる係数Sを（そこまでの範囲で）決める。
- P * e = Q + ε (0 <= ε << 1)
- S * e = T - δ (0 <= δ << 1)
このとき、 (P + S) * e = Q + T + (ε - δ) で、整数とのズレの部分 ε - δ は絶対値が ε, δ どちらよりも小さくなるので、ε - δの符号に応じてPとSのどちらかをP+Sに更新する。
これを繰り返せば、端数部分をどんどん小さくできる。
通してる人がみんなPythonだったのでRubyで書いてみたら、10^4000はTLEになってしまった。定数倍の範囲だとは思うのだけど…。
https://www.codechef.com/viewsolution/14231349
Persistent oak (OAK)
13点分は、永続化の実装の練習なので実装をする。
https://www.codechef.com/viewsolution/14218335
Saboteur (SBTR;タイブレーク)
残す頂点の集合を決める。
始点の頂点を1つ決めて、連結している頂点の中からコストが大きなものを使っていく、というgreedyを始点を変えつつ時間いっぱい試す
https://www.codechef.com/viewsolution/14223678
89.8点
結果
- 852.817pts/1000pts
- 43位/9386人
- レーティング 2448->2422
ESの満点は取れないといけなかった感
