今週のGNC練習会
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なのか。
ついでに
先日の Maximum Winter Contest 2006 のソースを微妙にインプルーブしてた。
http://www.aise.ics.saitama-u.ac.jp/~t_koh/PastProblems/Winter-Contest-2006/index.html
せっかくなので、晒してみる。
http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/a.cpp
最初からこれが書ければ30秒かからないのに
http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/b.cpp
純粋関数的に
http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/c.cpp
この問題はヒューリスティックが正解に違いない。
http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/d.cpp
仕様さえ分かればさして難しくないはず…。
文章から仕様は理解しづらいと思う。
http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/e.cpp
んまぁ、これも普通。
http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/f.cpp
これも普通か。連結かどうかのチェックを忘れないようにしないと。
http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/g.cpp
これも普通なのか。
テーブルは時間*駅で持ちつつ、
計算は電車*駅で抑えるのが楽するコツ。
http://fxp.hp.infoseek.co.jp/tmp/mwc_2006/h.cpp
最後も普通。
安楽椅子探偵
うーん、解答編を見たが…
まさか本当にテロップの無い人から犯人を持ってくるとは思わなかった。
しかし…あの二人ならやりかねないということか。
そういうわけで、まともに検証してなかった。
一度聞いた声を忘れない、という消去法の前提にしても、
サイン会で声をかけただけなのを覚えているというのは
なんだかムリがあったような気がするし、
あの出題編では、ノートを破った人が犯人と同一、
インターホンでのやり取りで知らない声が聞こえてきたという保障
両方厳しいような気がした。
うーん。
今度のことで、この辺のヒントは素直に用いるものだということが分かった。
たとえその結果が今回のようになったとしても。
あんまりあら捜しをするなということですな。
解答編終了後に本の告知みたいなのがあって、
え、、？び、びっくり館の殺人？
館シリーズ新刊ですか？
なんというか、前作から一年半だし、
まさか一年半で出ると思っていなかったし、
一年半でもずいぶん早いと思ってしまうし、
そもそもタイトルでびっくりだし、
読む前から驚かせるとは、さすが綾辻氏だなぁ…。
まぁ、出たら読ませてもらうことにします。
