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曲リピートしてた「メルヘンデビュー!」(安部菜々)の歌詞を覚えた。

2013-06-20

2013 TCO Marathon Round 3 CircleSeparation

15:45 | 2013 TCO Marathon Round 3 CircleSeparation - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク - 2013 TCO Marathon Round 3 CircleSeparation - yowa の TopCoder 日記

マラソンおつかれさまでした。これにて今年の TCO マラソン予選ラウンドは終わり。

今年も日本人の決勝進出者が多いみたいなので、みなさんがんばってください!

スライド

雑記

早い段階で「シミュレーション(当たり判定しながら円を動かす)はめんどいからやらない!」と決め打ってた。

今になって思えば、そっち方面はうといので(採用するかどうかはともかく)基礎的なことだけでも調べるといろいろ面白い情報に巡り会えたんじゃないかなーとちょい後悔。

調べるだけなら今からでもできるけど、今からやってもモチベーションが違うからなー。

2013-05-16

2013 TCO Marathon Round 2 FragileMirrors

06:10 | 2013 TCO Marathon Round 2 FragileMirrors - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク - 2013 TCO Marathon Round 2 FragileMirrors - yowa の TopCoder 日記

TopCoder部に日記を書くのは1年半ぶりとな。

TCOマラソンR2の参加メモ。暫定8位と、思わぬ高順位。

追記

スライドの最後に「Nが奇数偶数スコアがだいぶ違う(けど理由は調べてない)」と書いたけど、上位の方のTweetを見ると、奇偶性はだいぶ重要な要素だったようだ。

2011-11-08

Marathon Match 74 AntiTravelingSalesperson

04:16 |  Marathon Match 74 AntiTravelingSalesperson - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク -  Marathon Match 74 AntiTravelingSalesperson - yowa の TopCoder 日記

最終日にアイデアが浮かばず時間を持て余したので、今回の感想をスライドにまとめてた。

seed 1~4 の実行結果

f:id:yowa:20111108045700p:image:w200f:id:yowa:20111108045701p:image:w200f:id:yowa:20111108045702p:image:w200f:id:yowa:20111108045703p:image:w200

追記: ファイル名で振り返る

「新しいアイデアを試すときにファイル名を変える」という流れでコードを書いてるので、ファイル名を時系列順に辿ることで思考過程を振り返ってみようのコーナー。

nothing.cpp

毎度 Marathon 開始時に作る、何もしないプログラム(空の配列を返すなど)。

simple.cpp

ビジュアライザを動かすために、自明解を出力するプログラム。とりあえず example submit してみて、エラーがなければ full submit する。

そのコードをベースにちょっとずつコードが増えていき、気づいたらちっとも simple じゃなくなるのが毎度のテンプレ

triple.cpp

シェルピンスキーのカーペットみたいな)再帰構造で点を配置してみた。結果スカスカになって最短辺の距離が短くなり、あまり総距離を稼げ無そうなのでボツ。再帰ごとに点の数が3x3倍になるので triple (9倍なのに triple ?)。

lattice.cpp

四角格子状に点を配置。「格子(lattice)」って用語で合ってるのか自信なくてぐぐったりする。point lattice でいいのかな。Point Lattice -- from Wolfram MathWorld

fail.cpp

seed ごとの入力を書きだすためのプログラム。ビジュアライザにスコア計算させないために(←時間がかかるから)、不正な値を返すので fail 。

triangle.cpp

三角格子状に点を配置。

i_want_fast_nn.cpp

この時点での Nearest-Neighbor 解を求めるコードが遅かったので、なんとか速くならないか試行錯誤してた。ここでのコードは上手くいかず結局捨てた。

range_test.cpp

「一度求めた解の、順路を変えない範囲で点を動かす」作戦に使うため、点の範囲(区間)を表現するクラスを書いてた。

tour.cpp

↑のヤツを実際に書いた。順路のことを tour と呼ぶことにした。

rec.cpp

基本アイデアである「四角格子を順番に辿るけど、4点に1点は後回し」作戦だけでスコアがどのくらい出るか試そうと書いた、20行くらいのコード。 rec は recursive の略なんだけど、どのあたりが recursive なのかは謎。

embed.cpp

「小さい N は格子作戦が上手くハマらないけど、うまくいくパターンは別にあって、それをコード埋め込めば点数伸びるんじゃね?」という妄想を確かめるためのコード。妄想は妄想だった。埋め込みの embed。embed って別の単語の過去分詞っぽくね?

revenge.cpp

「前は失敗したけど、NN 解を求めるコードを今度こそ速くするんだ!」と復讐に燃えていたので revenge 。

renew.cpp

単純な山登りだったのを、焼きなましっぽく悪い方への変更も確率的に許してみたコード。そのあたりのノウハウを持ってないので芳しくない結果に終わった。基本的な改善戦略を変更したから renew 、だった気がする。

eleven.cpp

埋ーめー込ーみー。N = 10~1万 だけど一様分布じゃなくて、いちばん出現するのは N = 11 (1.38%) だから、それに特化してなにか埋め込みできないのーとか迷走してた。

prosho007prosho0072011/11/10 23:47スライドすごく分り易かったです。自分も格子状、三角状考えましたが最終的には迷走してしましました。スライドのお陰で少しすっきりしました。

2011-07-15

TopCoder Open 2011 Marathon Match Round3: StringCompression

17:38 |  TopCoder Open 2011 Marathon Match Round3: StringCompression  - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク -  TopCoder Open 2011 Marathon Match Round3: StringCompression  - yowa の TopCoder 日記

総括

  • 途中で問題変更があった
  • テスタが更新されるまで作業を中断しておこう
  • 残り一週間切ってもテスタ更新されないけどどういうことなの……
  • 実はテスタのダウンロードページ自体の URL が変更されてた
  • ずっと旧ページをリロードしていたので更新に気づかなかったというオチ
  • なんだかんだで、暫定 23 位で終了
  • まあ、どうせ時間をフルに活用できても上位12人に入れたわけでもないしー
  • そもそも 12 人に入れてもアメリカまで行くつもりは無かったもん
  • だから、むしろ上位に入れなくてよかったよ!(すっぱいブドウ

問題

入力: 
 S[1] = abc3de2f
 S[2] = xx
 S[3] = oo3oo

出力: abcooxxoodexxf

みたいな単純置換による文字列展開メソッドがあって、出力から入力を推測するという問題。ただし出力にはランダムなエラーが入ってて、入力の方はスロット数と、各スロットの長さが与えられる。

やったこと

参照関係にループが無いので、一番深いところの文字列が一番たくさん出現するはず。なので「一番多く出現してる文字列を展開の末端だと見なして数字を割り当てて置換する」という処理を再帰的にやる感じで。

文字列特定フェーズ

出力にはエラーがあるので単純に出現数を調べることは無理、なので

  • 短い長さ(とりあえず l=4 でやった)での最頻文字列を調べ、 k とする。
  • k、および k と少しだけ違う文字列(とりあえず d=2 まで許容)を中心とする、前後の文字列を列挙
  • 各位置で出現文字の多数決を取る。求めたい文字列を構成する文字は得票数が多いはず
 (seed==2 の例)
                        k == "rlpr"
  hdcgwjoutluxeftusgfhwsnefrc|rlpr|zaulwxeztscgutvwqwwqyfjmpb
  hdczwatgimdpwvgvinshodqtori|rlpy|mevrwikuquxwuugshweqqqrwre
  amdnlrxupagdtfgubnpuwwyyfrc|rqpr|myurwaeeusfgjtuzqewqcfmcll
           :           :       :         :          :
  cgaoetlvygttxtgctuthwanyfrc|rlpr|oauggbeeutrepsyaulafccgguq
  rammhhewcnerqpxywnshpwqymdc|rlpr|yakrwjemustmouurmjcwqyvssr
  nrcauoqqgempdngutnahwwbyfjc|elpr|zfuhwgeoasplszavklgjjnfqbe
                ↓        投票      ↓
  plmzaxklgkunfggutnshwwqyfrc|rlpr|maurwieeusiwhfcdwaomtlfxgt
   150票くらい ||←この間は400票くらい獲得→|| 150票くらい 

  よって w = "gutnshwwqyfrcrlprmaurwieeus" が求める文字列っぽい! (このケースでは正解)
文字列置換フェーズ

例によってエラーがあるので、w とどのくらい異なる文字列まで置換するか?という問題が。とりあえず、長さ |w| の全部分文字列について w との距離を計算して分布を調べる。

 距離  件数
   0     0  ← 全文字一致するケース。置換するっきゃないでしょ。
   1     0
   2     0
   3     0
   4     0
   5     0
   6     1
   7    11
   8    21
   9    41
  10    76
  11   142
  12   172
  13   225   ← このあたりが、山の中心 
  14   220   ←  (27文字中, 13.5 文字くらい一致してるっぽい)
  15   244
  16   173
  17   117
  18    76
  19    31
  20    19   ← このあたりは上の山(置換すべき)? 下の山(そのまま)?
  21    23
  22   111
  23   740
  24  3532
  25 11559
  26 22575
  27 18815  ← 1文字も一致しないケース。置換するわけない。

んで、全部分文字列数を n、置換すべき文字数を m、ある文字がエラーで書き換わってる確率を p とすると、上の度数分布は(iid とみなせば)おーざっぱに二項分布2つの和 m B(|w|, 1-p) + (n-m) B(|w|, 25/26) に従うはず。なので m と p を推定してやると、距離 d だけ離れた文字列が上の山に含まれる確率が計算できて、十分高ければ置換する、と(実際は上下の山の対数尤度比でやってる)。

神頼みフェーズ

エラー率が高いケースでは想定解が求まる気がしない(or 想定解よりもっといい解があり得る)ので、ランダムで。多分こういうパターンが一番自由文字数が多くなる(総参照文字数あたりの展開後文字列長が最大になる)と思う(確かめてない)。

 S[1] = ????????????????????????444
 S[2] = ??????????????????????????????  ← 一番長いのを末端に
 S[3] = ?????????????????????2222     ← 自分より長さ順が1つ上のを参照
 S[4] = ???????????????????333      ← 参照回数は均す。端数が出る場合は末端側から増やす。

ので、

  • 参照文字の位置をシャッフル
  • そのパターンで展開
  • 各'?'に当てはまる位置の文字で投票し最多文字を'?'に当てはめる

というのを(正当法でいい解が見つからなかったら)時間の許す限り繰り返す、と。

やらなかったこと

  • 参照順 & 参照回数の推定。参照順と参照回数が決まれば、展開後の文字列長が定まる。参照は、自分より末端の文字列全てをそれぞれ1~4回行うので(長さあふれの時は打ち切り)、スロット数を n とすると、組み合わせは  (n-1)! 4^{n(n-1)/2} とおりくらい。展開後の文字列長は分かってるから(長いと打ち切られてるけど)、参照順 & 参照回数の組み合わせを絞り込むことができる……はずなんだけど、思ったより展開後が同じ長さになる組み合わせ数が多かったので、実用にならないと思い却下した。
    • あとで思えば、ある程度のスロットを埋めたあとで「このままやって大丈夫?」というのを調べる(枝刈りする)のには利用できた気がする。
  • w の長さの絞り込み。上の例だと高い確率で "gutnshwwqyfrcrlprmaurwieeus" だと断言できるのに、絞り込みに手が届かなくて、他の長さの候補も列挙した。おかげで 7! 回とかのの探索が必要になったのでタイムアウトによる探索打ち切りがあるよ!(優先度つきで見て回ってるので、正解っぽいのは先に見れてるはずだけど)
  • フレキシブルな置換。距離が微妙なケースでは「同じ距離でもある文字列は置換して別の文字列は置換しないのが正解」ということが当然ある。けど、やってない。
    • 「とりあえず微妙なのは置換しないでおいて、後で矛盾が生じたら改めて置換する」というのがうまくいきそうな手応えがあったけど、間に合わず。