今週のGNC練習会

ICPC

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1886
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1887
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1888
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1889
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1890
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1891
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1892
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1893

の8問。12年も前のWorld Finalsの問題。
ムーアの法則によるとCPU性能が1/256のころの問題なので、
あまりCPUを食いそうな問題はない…のか？
入力がオフィシャルじゃないのか知れないけど、
とにかく通らない。こりゃ参った。


まず簡単そうな1988を渡されるので解く。
これは問題なくAccept。
次に1887を渡される。これは最小"非増加"列を求める問題。
無論アルゴリズムなんて覚えていなかったが、
二乗のアルゴリズムはすぐに思いついて、
それから仕切りのみ考慮してSetを用いることにより
nlognのアルゴリズムを構築。そのままでは最小"減少"列が求まるので、
うまく弄って非増加列長が計算できるようにする。
これも書いたら通った。
次に1890がなんだかサイズが小さいということなので、
これを解くことに。
すぐに思いつくアルゴリズムの計算量は階乗オーダ。
これで入力はn=8まで。
今の時代だったら最低10は来そうな感じ。
これも普通に実装したら普通に通った。
次に、どうやら簡単そうな1893を書く。
書くの自体はすぐに終わったけど、
なんとこれが全然通らない。
誤差の処理とかかなりまともに実装しても通らない。
何度送っても通らないので、
他のチームがぼちぼち通り出した1886に切り替え。
問題のスペシフィケーションがかなりあいまいらしいのだが、
適当に解釈して実装。
かなり適当だったけど、書いたら通ってしまった。
さて、1893はやはり通らない。
1892は誰も通っていない問題なので、とりあえず回避しようという方向になる。
1891か1889のどちらかをやろうということになったのだが、
もし入力サイズが小さければ1889の方がさっくりと実装できそうだったので、
入力サイズがある程度を超えていないかどうか、assertをかけて調べる。
(なんか酷いやり方だけど…問題に載ってないんだもん)
結果想定内のサイズだったので、こちらに特攻することに。
(今気づいたんだけど、PKUって出力が遅延評価？されて、
間違い一個目でプログラムの実行がストップするから、
一個目の入力しかチェックできてなかったかも？)
プログラム自体はすぐできるものの、
なんとMLE。これはおかしい。(今思うと、ちゃんとチェックできてなかったからか)
メモリを削減して再投稿。今度はWA。
なんか良く分からないけど微妙に希望が。
ごちゃごちゃ修正。
WAがTLEに変化。ショック。
それから後はごりごり線形の最適化を続ける。
TLEの連発。もうだめだ…終了。
1891に行っていたほうが良かったかも。
1891はとても難しそうには見えない。
しかし、Accept率が異様に低いのが気になる。
終了後どこかのだれかが練習用に作ったらしい入力を拾ってくる。
1983を通してみる。たくさん相違が。
いろいろ直してみるもどう考えてもおかしな入力が来る。
結局どう直しても通らず。この問題は怪しすぎる…。
良く分からず。コンパイラをG++からC++に変えれば通るという話も有ったが、
少なくともうちのソースは通らなかった。
あと、1889はDPではなくて、枝刈探索でExpオーダのアルゴリズムだったみたいだ。
これが探索って…私の感覚もまだまだだな…。
ちなみに、DPによるプログラムは最終的にテスト入力を
ローカルで1.7秒で処理できるまでに高速化されたが、
PKUのタイムリミット一秒はさすがに厳しかったようで。
もう少し最適化すれば通らないことも無いような気がするんだけど…。


というわけで、今回は全体的にいまいち。
問題もいまいちな様な気が…
これが昔のWorld Finalsなのか。