Hatena::Grouptopcoder

yowa の TopCoder 日記

TopCoder yowa / twitter: @yowa

2013-08-12

ICFPC 2013 参戦記

01:35 |  ICFPC 2013 参戦記 - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク -  ICFPC 2013 参戦記 - yowa の TopCoder 日記

ICFPC 2013 http://icfpc2013.cloudapp.net/

参加者のみなさん、おつかれさまでした。

最終スコアは 964 だった。詳細は、正答964/誤答205/未着手651。

追記 (2013/08/13 07:41)

ソースうpった。Ruby 600 行、C++ 600行くらい。 https://github.com/yowa/ICFPC2013

問題

サーバに用意してあるプログラム(入力が64-bit整数、出力も64-bit整数関数)を当ててる、というもの。

問題数は 1420 個だったけど、途中で +200 +200 があって、最終的には 1820 個だった。

プログラムを当てるために、こちらが行えるクエリは2種類。

  • eval: 引数を最大256個を与えると、その答えを返してくれる。

「f_1(0), f_1(0xFF), f_1(0x0123456789ABCDEF) の値は、それぞれ何ですか?」

『1, 0x100, 0x0123456789ABCDF0 だよ』

  • guess: この関数であってる?と尋ねる。正解だとスコアもらえて、間違うと反例を教えてくれる。

「f_1 は (lambda (x) (plus x 1)) でしょ?」

『残念。f_1(1) は 0 なんですよ。あなたのプログラムは 2 を返しますよね?』

「…じゃあ、 f_1 は (lambda (x) (if0 (xor x 1) 0 (plus x 1))) だったり?」

『そう、それ。+1点です。』

各問題について「どんな演算子が使われてるか(operators)」「演算子が使われてる合計回数(size)」は最初から分かっている。

また重要なこととして、時間制限・クエリ数制限がある。1つの問題に使える時間は5分(eval, guess をした時点からタイマーが動く)で、クエリは最大5回/20秒 しか呼べない。時間切れしたらスコアは得られないし、guess しても正解かどうか教えてくれなくなる。

やったこと(まとめ)

基本的な solver のシステムはこんな感じになった。

  • (Ruby) 問題情報を読み込む。
  • (C++) 与えられた size, operators で表現できるプログラムを全列挙する。
    • 演算子回数が多いととても時間が足りない。
    • 現実問題としては、時間よりメモリ。1000万個も列挙すればメモリが尽きて死ぬ。
    • 死ぬまで長くて 5 秒とかなので、時間なんて気する必要はない(←フラグ
  • 列挙できず死んだら、この問題は後回し。
  • (Ruby) てきとーな入力で eval する。
    • ランダムな64-bit整数をいくつか
    • コーナーケースになりそうな 0, 1, 0xff, ~0, 0x8000000000000000 とかそんなの。
    • 一度に256個渡せるけど、めんどくて20個くらいしかやらなかった。
  • (C++) 列挙してるプログラムに ↑のeval で投げた入力を食わせて、出力が一致するものだけに絞り込む。
  • (Ruby) 絞り込み結果から 1つ選んで guess する。guess に失敗したら、失敗時の入出力を使って更に絞り込む。
  • 可能解は全列挙してるので、必ず正解する。

やったこと(開始 12 時間)

問題を開いたら (lambda (x) ..) とかいうのが見えたので、parser が必要だなあと思って Ruby で書き始めるけど、なかなかうまく書けない。2~3 時間悪戦苦闘した後に「サーバから "(lambda (x) .. )" みたいなのが送られてくるわけじゃないから perser なんて必要ない」と気づく。

開始 12 時間くらいで solver はだいたい出来てて(列挙部も Ruby だったけど)、もう新しいアイデアとかねーよ、とか思ってた。

やったこと(中だるみ)

ライトニングスコアが 318 点。詳細は 318/6/1096。solver の送信バグや、仕様の勘違いで時間切れが 6 問出たけど、解こうとした問題は全部解けてる感じ。

その後、列挙を C++ で書いたり、本質的な重複を減らすめに式の簡約をやったり((and 0 X) は 0 と同じだよねー、(if0 S 0 S) は S と同じだよねー、引数が全て定数な演算は結果も定数だから同じ値はまとめれるよねー、右シフト3種 shr1, shr4, shr16 は順序入れ替えても同じ結果だから1つしか列挙しなくていいよねー、とか)したけれど、これらの改善を全部合わせても「対応できる size が最大11だったのが、12まで可能になりました!」みたいに、ちっとも本質的な改善ではないのだった。知ってた。

やったこと(最終日の深夜 0 時を回りました)

締め切り前 7 時間半で、345/6/1469。ライトニングから 27 点しか進んでない。

で、やっと「失敗してもいいから、とりあえず全部の問題にチャレンジするだけしてみよう!」と重い腰を上げ、ダメ元作戦スタート。

これまでの経験から「size: 11, operators:[if0, and, not, plus, xor] とか言っといて、結局答えは (lambda (x) (not x)) で通るんじゃねーか」的なことが多かったので、size が 30 とかある問題も size を 12 に決め打ちした上で solver を動かした。んで、演算子が多い問題だと列挙できずに死ぬので size を 11 → 10 → 9 と減らしていく感じに。

これはもちろん「解なし」になるケースがあるんだけど、そこは人力で解ける問題もあるかもーと思って、「解なし」の時はアラートを鳴らして eval, guess 履歴を眺めることにした。

しかし。size 9 の全列挙では実現できない、本質的に size 10以上あるプログラムを、入出力眺めただけで人手で解こうなんてオレに無理無理ですよ。結果、アラートが有効利用されることはなく、アラートとして鳴らしてた『ミスった~』というゆっくりボイスが、とにかくうるさいだけだった。あとアラートを1回鳴らすのに 2~3秒費やしてたのが累積して…。

残り1時間半で、881/139/800。ダメ元作戦で挑んだ問題に 536勝 133敗 で勝率 80% と、予想以上の好成績。

残るはタイプ fold の問題(400問)と、タイプ bonus の問題(400問)。

fold が後回しだったのは、例題(train)を10個くらい見たら必ず一番外側に fold が来てたので、そう決め打っていいのかなー、とか思ってたから。で、決め打ちしたコードを書いて、さて動かす前にもう1個だけ例題を見ようかーとか思ったら、いまさら一番外側じゃない例に出会った。

あわてて任意の場所に出るように書き直し。すると変数束縛の都合上で式列挙が複雑化。なんとか書いたものの、fold は3項演算だから組み合わせが爆発して、サイズが 8 とかでも列挙できずに死ぬケースも。結局「例題ではあんだけfold が一番外側にあるのが多かったんだし、どうせダメ元フェーズなんだから、一番外側に決め打っちゃえ」という結論に。

んで動かしはじめたんだけど、fold 問題 400 中 150 問目に挑んでる途中で、クエリを投げるとサーバが "contest is over" を返すようになった。TIME UP でござる。お疲れさまでしたー。最終結果は、964/205/651 。

fold 問題は 83勝 66敗 勝率 55% と歩留まりは悪かったものの、残り 250 問を完走してれば +120 点くらいは見込めたわけで(皮算用)。

利用価値の無いゆっくりアラートを最後まで有効にしっぱなしだったり、クエリの時間制限に余裕を持たせすぎてたり、いろいろな時間的なムダを省いてたら、完走できてたんじゃないかなー。だれだよ、初期段階で「時間なんて気する必要はない」なんて思ってたの。

やれただろうこと

  • 列挙の絞り込み
    • operators に含まれる演算子は必ず(形式的にしろ)使われてるんだから、使ってないやつがあったらアウト、的な条件を使えば列挙する数を減らせたはず。
    • (shr1 (and x 1)) は x に依らず 0(定数)みたいなの。ノードごとにビットマスクを持っといて、演算するごとに伝搬していって、マスクが 0 になったら 0 だよー、的な。
      • 発展形で反転マスク(1 だと分かってるビットを覚えとく)とかも。
    • まあ絞り込みを頑張っても扱えるサイズが1増えるか増えないか程度の影響だろうので、あんま必要は無い。けれど、やってて楽しい部分だった。
  • 列挙→eval→guess ではなく、eval→列挙→guess という順序でやる。
    • 列挙の絞り込み条件に eval した入出力を利用できるので、扱えるサイズもぐんと大きくなるんじゃないかなー。
    • けど「最初の eval から 5分以内に正答出さないと時間切れ」というルールにビビリまくってて、eval 後に列挙しててバグ落ちしたらどーすんのさー、とか思って却下してた。
      • 練習問題(train)は無限に生成できるんだから、そっちで調整すれば良かったんですよ
  • 列挙したヤツの使い回し
    • 問題毎に毎回1から列挙してたけど、他の人の参戦記を見た感じ、DB につっこんで使い回してる人が多かった。
      • だって、DB とか使い方わかんないし……。

よかったこと

  • RubyJSON の扱いとか post の仕方とかわかった。
  • 人手を介さず回るシステムが形になった。
    • たいてい「結果は手で送信する」「入力のパラメタ見てコードを手調整する」という段階で満足してたので、これは大きい。
  • オレが必要以上に失敗を恐れるタイプであることが浮き彫りになった。
    • 先に eval するのにビビったり、大きいサイズの問題に対する有効策が無いのにもかかわらず、ダメ元フェーズに移行するのが遅かったり。
  • ラストスパート時に1曲リピートしてた「メルヘンデビュー!」(安部菜々)の歌詞を覚えた。