つーさのくーかん

7月2日です。
16時半から19時半まで、いよいよという感じですが、国内予選でした。
例によって、ミーティングルームを貸し切りでの参加なのです。

Aはまぁ、0からの「相対」座標で計算することに気づいたら、配置をシミュレートして解く。
何の問題もない……おｋ、順調だ。

Bは入力が厄介なだけで、ちゃんと迷路を表現したら経路探索するだけ。
え、Bでいきなり経路探索？　と思ったけど、まぁ、フツーに書けたので、開始40分ごろに提出。
Wrong Answer！　おーえー……まじで？　この単純な解法のどこに問題があるというんだあああああ。
しばらくコードを読んだり、変数をはき出してみたりするもわからん。Bを放置してCへ。

C。正四面体数ってなに？　式が与えられてるのでテーブルを作ればいいのかな？
探索方法をどうするか。最小の組み合わせを求めればいいのだから、BFSかな？
でも、テーブルの要素結構ある。深さに対して枝分かれがヤバイのでBFSはメモリ不足に陥りそうだよね。
というわけで、枝刈り付きのDFSを組んでみる。サンプルが通る。
データセットをもらってくるが、1つ目の入力からして計算が終わらない……。
DPに切り替える。ちょっと考えて、コードを書く。さくっと計算して提出する。
Wrong Answer！　うは、万事休すか……。

1時間半が経過して1問しか解けていない状態が、未だかつてあったろうか……。
新しい問題に進むか、バグを取るかでちょっと相談。
結局、BC解けずして未来はないと、バグを取る方向に。

まず、B問題について、サンプルの1ケース目についてちゃんと入力できてるか確認する。
こんな変な入力見たことない。どう考えてもアヤシイのはそこ。
でもdata[]の中身は正常に見える。えー、じゃあ探索がおかしいっていうのか？
こんなに書き慣れている最短経路探索にバグが混入するものか？
そう訝しみながら一応調べてみるものの、何の問題もない。
どう考えても問題は見つけられない。入力がおかしいんだろう。

デバッグを初めて十数分後のことである。
けろさんが見つけてくれたバグは、「最終行の入力を読んで、棄てて、全部に壁立ててる」というものだった。
焦っていた僕が書いてしまったバグだ。コピペするときにif文を落としたのだ……。あー、なんということだろう。笑えない。
３つのサンプルすべてで、一番下の行がすべて壁でも答えが変わらないということもわかった。
僕はもう怖くて画面を見ていられないので、提出は全部けろさんに任せた。
Correct Answerだったとのお達しをいただく……うぅ。穴掘って埋まっていたい。

続いてC問題のデバッグである。
なんでWrongAnswerなのか。DPが間違っているのか？　サンプルは通ったぜ……？
データセット1の出力を見ると、1列目に11とか13とか書いてある。
おっと……これはポロック予想が外れていることを示している！
そんな問題が未解決なわけはない。

しばらく、コードとにらめっこである。
10^6っていくつだろう……0何個？　6個か。ふとそんな疑問を抱いて0を数えていたら
……見つけた。テーブル作成関数の終了条件、0が5個しか書いてない。
10^5までしかテーブル作ってない……！
0を1つ足して再計算し、1列目の数字が5以下に収まっていることを確認。
祈るような気持ちで提出し、Correct Answerとのお達しをいただく。

3問終わって、残り時間は40分程度。順位はだいぶ下の方。もう1問通さないと通過は厳しそうだ。
ここで、Dへ行くのかEへ行くのか。
両方の問題を読んで理解し、方針を立てるのに15分程度を使ってしまう。
このとき、なにも考えずにDに行けばよかったのかもしれない。

Dは下からブロックを認識して、ツリー構造を作って、再帰的に計算するだけか。コーディングめんどくさそう。
Eは、えーと。なんだこれ？　探索？　いや、ラベル？　コスト計算どうすんの？　？？？
結局、ぱっと方針が思いつかないEは放置、Dを書き始めるが終わりませんでした！

うーん。万事休すかー。
プロコンの最中に「万事休す」って言葉使ったの何度目だろうと思いつつ天井を仰ぐ。
去年までチームメンバーだったコーチは、一足お先に選抜チームのチェックを終えてたらしい。
「ダメだった」と非常に残念なオーラを出していた。まぁ、一応自分たちでも確認しようと数えてみる。
とーだい、とーだい、とーこーだい……。あれ、26位じゃね？　その後4回確認した。

僕は、通過した喜び以上に自分の書いたバグが信じられなくて、相当に鬱状態。
その後のご飯の席では、周りに相当迷惑を掛けてしまったと反省している。
でも。頭を使った後のご飯。おいしかった……。泣いた。

プロコン。
プログラムを書くコンテストであるうちは楽しいが、デバッグのコンテストになると途端にきつい大会になる……。
バグは産みたくない、ものだ……。

後に、http://imoz.jp/2010/07/icpc-domestic/ によれば、

とか。
正式発表は出てないけれど、これがそのままなら通過したことになるのか。
一緒に戦ってくれた2人とその他関わっているすべての人に心からの感謝を。