■ [CodeChef]October Challenge 2016 
ひさしぶりに参加した。ちょうど良い難易度だった。
Chef and Keyboard(CHEFKEY)
やる
https://www.codechef.com/viewsolution/11712752
Chef and Three Dogs(CHDOGS)
Three Dogs Problem でググると http://mathworld.wolfram.com/MiceProblem.html に行き着く
https://www.codechef.com/viewsolution/11712881
Fenwick Iterations(FENWITER)
実験するとわかる
https://www.codechef.com/viewsolution/11764653
Chef and Two String(CHEFTWOS)
2を使うのは次のように 2,2,1 と並んでいる形しかありえない
2 2 1 ? ---> <- --->
2が何個連続しているかを状態としてDPする。終端でぴったり終わらないといけないので最後だけちょっとややこしい
https://www.codechef.com/viewsolution/11766059
Big Queries(BGQRS)
遅延更新するSegmentTree。
各ノードに次の値を持たせる
- 配下の範囲に含まれる2の数,5の数の和
- 配下の範囲すべてに共通して含まれる2の数,5の数
- 配下の範囲がクエリ2によってひとつの等差数列に含まれているなら、その先頭の値
https://www.codechef.com/viewsolution/11770129
Sereja and Stones(SEASTONE)
石の配分を固定したとき、Eが大きい箱にたくさんの石を置くようにするのが最適なので、箱はEの値でソートする。
Eが最大の箱にすべての石を入れる、またはできるだけフラットになるように石をすべての箱に分配する、という戦略が良い上限になっているようで、枝刈り探索で十分早く答えが出た。メモ化もせず0.38秒。
forumによると、DPを加速する方針の計算量が保証できる解答もあるらしい
https://www.codechef.com/viewsolution/11790150
Power Sums(POWSUMS)
このあたりを使うと、与えられた情報からN変数の基本対称式の値がすべて求まる。
それを元に、a_i が満たすべきN次モニック方程式が出るので、きたまさ法を使って a_i^x の次数を落とせる。
https://www.codechef.com/viewsolution/11719575
Bear and Shuffled Points(GEOCHEAT)
逆向きに、すべての点がある状態から一つずつ取り除いていくと考える。
最遠点対は、凸包を作ってキャリパー法すると O(NlogN) でわかる。
取り除く点が最遠点対に一致したときのみ再計算する。点がランダムに並び替えられていることから、再計算は頻繁には起きないのでこれで間に合う。
ちなみに N=750000 のとき、再計算回数の期待値を計算してみると28くらいだった。
なおキャリパー法を蟻本を元に実装したら、停止しないケースがあって焦った。とりあえずアドホックに対応したけど、もうちょっとちゃんと対策しておかねば。
https://www.codechef.com/viewsolution/11864670
Tree Balancing(TREEBAL)
考える時間が無くて自明な部分点のみ。
https://www.codechef.com/viewsolution/11865084
Sereja and Progressions(SEAARI:タイブレーク)
まずは絶対値が大きい順にD個取り除く。
残りの値の最小値が配列の左端、最大値が右端にくるとして、それらを結んだ直線を仮の回答とする。
その直線からのずれが最も大きい位置を交換元とし、交換元の値が本来あるべき位置の周辺を探索し、入れ替えたときに最もコストが減少する位置を交換先とする。これをK回行う。
PriorityQueueを使って1回の交換あたり O(logN) で処理する。
https://www.codechef.com/viewsolution/11867199
83.106点
結果
- 893.106pts/1000pts
- 9位/6517人
