ICFPC2010参戦記
問題設定とかは http://d.hatena.ne.jp/ku-ma-me/ を見ればいいとして、
金曜日21:00〜23:00
問題読みタイム。さっぱりわからないが、一番下に最初にやるべきことが書いてあったので、0を送ればいいっぽい、サーバが死に掛けてて全く送れない。やっと反応があったときにはすでに登録されてるよって出る。
それはいいとして、次は回路を理解せよということだったので、まず回路のフォーマットを推測して、適当に作った回路を送り始める。「22022022022022022」を返してくる回路を見つけてこれがヒントになるかと思ったが、時間切れで電車に乗る
土曜日
帰宅して、適当に回路を作って送りつける作業を続ける。結論として、次のような回路を考えればゲートの動作を推測できることが分かった。
X +---+ | | | +-*-*-+ | | | | +-*-*-+ | | | | | +---+ A | +---+ | | | +-*-*-+ | | | | +-*-*-+ | | | | | +---+ B | +---+ | | | +-*-*-+ | | | | +-*-*-+ | | | | | +---+ C
最初に１ゲートのを送ってAの出力を調べて、次に２ゲートのを送ってBの出力を調べて、を繰り返せば入力と出力のペアはいくらでも得られる。これを左右反転した回路に対しても行って、
左入出力 02120112100002120 00100202221110100 01221000201200221 02110011002121022 00122120010101102 01211021122222000 02101101211111211 00112002101201012 右入出力 22022022022022022 21202210221202210 20221022020221022 22102202212020221 21121022111202211 20202202021120202 22120221202112022 21112020221102210
これをじっと眺めてれば、左に2を入力したときに左からは0,1,2の全通りが出てるので、
in | out 2 ? | 0 X 2 ? | 1 ? 2 X | 2 ?
よく見ると、「2->0」の直後に「2->2」があるので、Xが等しいことが分かる。途中で計算間違いを莫大にしたので時間がかかったけど、記録によると1:30ごろにゲートは確定したようだ。
回路作成
というわけで、今度は任意の出力を出せる回路を作る方法を考えないといけないわけだが、最初に考えたのは常に0を出す基本回路を作るんじゃねとか思ってみたりしたんだけど、どう頭をひねっても想像もできないので、やめてもっと直接にやる方法を思いついた。
とりあえず、回路全体をこの形に固定することにする
inp | +---+ | |Y | +-*-*-+ | | | | +-*-*-+ | | |X | | +---+------X | | 残りの回路 out +------Y'
この回路はinpとoutのtrit列が与えられたとき、 inp[0] = out[0] ならば解があって、
Y = 0::Y' inp[0] = out[0] X[0] = inp[0]×0-1 Y[k] = inp[k]-out[k] X[k] = inp[k]×Y[k]-1
のように、XとY'のtrit列を完全に決定できる。しかも、Y'の列の長さはoutの長さより1短い。
よって、inpからoutを出す回路を作る問題はinp[0]=out[0]のときは、1短い入出力の問題に単純化できた。
同様に inp[0]-2=out[0]のときは、ちょっと改造して Y = 2::Y' にすればいいので、
+---+ +-------+
| | | |
| +-*-*-+ |
| | | |
| +-*-*-+ |
| | | |
+---+ | |
| |
+-+ |
| |
| +---+ |
| | | |
+-*-*-+ | |
| | | |
+-*-*-+ | |
| | | |
| +---+---+
inp | |
| +---+ |
| |Y |
+-*-*-+ Y'
| |
+-*-*-+
| |X
| +-----X
|
outとつなぐと、Y = 2::f(Y') となる。このfが全単射になるように繋がないといけないので右出力を使えないのです。
これでkey prefixは通った。朝の7時半ごろ。そのまま寝て起きて、夜になったら車フォーマットを研究することにする。
日曜日
午前2時ぐらいにやっと車のフォーマットがほぼわかった。引き続き燃料の解析。午前3時半に最初の燃料が通過する。この時点で簡単な車にがんがん給油してればもっと点数も高かったんだけど、メインの問題を考え始めてしまった。一人でやってるとしかたがないよね。
このへんで、サンプルの車を解こうとするが、さっぱり理解できない。こんな車解けるのか？ランダムに行列を生成したり、ちょっとした変異を加えても全く答えに近づいているような気配がない。9時半まで悩んで全く解決しなかったので寝る。
21時ごろに起きて、大衆車に給油する仕事をすませる。そのあとサンプル車の解き方を考えるのだが、こういう問題の基礎知識がないのでさっぱりわからない。非線形の最適化問題とかやったことないよ。
23時にあきらめてWORKINGを見たりする。さすがに時間切れ。
