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を見たりする。さすがに時間切れ。