本番れぽ

ACM/ICPC

まずは問題を三人で読む。A,B,C,E,Fを読んだところで、一度同期。

  • 問題Aは数列の部分和に関する問題。普通に簡単そう。
  • 問題Bはちょっとだけ面倒なシミュレーションの問題。問題文にあるとおりにシミュレートするプログラムを書けばいいだけだけど、これでハマって後に響くと嫌なのでとりあえずは後回しにしたほうがよさそう。
  • 問題Cは六面体の回転に関する問題。ダイスの回転をするライブラリを持っていたのでそれを使えば簡単に解けそう。
  • 問題Dは問題文が長かったのでいったんパス。
  • 問題Eはバイナリツリーを作る問題。インプットの大きさが6までと小さいので、Generate&Testで十分。ただ、バイナリツリーの生成が面倒そう。
  • 問題Fは計画問題。明らかにDPの匂いがたちこめている。


とりあえずは順当に簡単そうな問題Aをぼくとtoyoが解きにかかった。YAMAはその間に残りの問題を読みに回る。問題Aは特に問題もなくAC。


そしてYAMAから問題D,Gの解説を聞く。

  • 問題Dは探索問題。深さが6までと浅く指定されているのが気になる。
  • 問題Gはグラフの問題。解法がすぐには思いつかない。


問題Cの六面体の問題がダイスの回転をするライブラリで瞬殺できそうなのでそちらへ。
とりあえずぼくがライブラリを入力して、その間にtoyo,YAMAは他の問題を考える。
入力が終わったところで二人は問題Eを考え始めていた。toyoをナビゲータに借りて問題Cをコーディング、これも特に問題なくAC。


toyoはYAMAと一緒に問題Eに戻ることにして、ぼくは他の問題を考える。DPの匂いがしていた問題Fの解法を思いついたので、とりあえず紙上でDPの式を作成。DP自体は簡単だけど、距離行列の作成のほうがバグが入りやすそう。
解法が出来上がったところで二人がまだコーディングにとりかかっていなかったので、とりあえず入力とDP部分だけをコーディング。残りの距離行列を作成するだけになったところで、toyoをナビゲータに借りて詰め。
二つある式を混同してしまって間違った出力が出てしまい、ちょっとだけあせったが、5分くらいで気づいて修正。AC。


toyo,YAMAに問題Eをまかせて、ぼくは放っておいた問題Bの方針を考える。
汚くコーディングするとハマるのは明らかなので、コーディング前に紙の上でメソッドやフィールドの設計をやっておいた。


二人が問題Eを書き終わったが答えが合わず、デバッグに回っていたので、とりあえず枠組みだけコーディング。
問題Eの紙デバッグが終了したところでYAMAと交代して、コードを修正し、submit。しかしWA。再び二人はデバッグに。


問題Eでハマりかけている状況で、実装がすべてでハマりが怖い問題Bを平行してやるのはちょっと危険だったのだけど、今日は割と調子が良くて自信があったので、一人で実装してみることにした。そのかわり、いつもの３倍慎重にコーディング。
結果、一発でコンパイルが通って、Sample Inputに対して一発で正答が返ってきた。最後にInputの条件を再確認して、submit。AC。


ここで問題Eをやっている二人に合流。最初のWA後に誤差の問題じゃないか、といって出力の桁数を増やしてまたsubmitしたが、またWAを食らった。
完全にハマっていたので、一度離れたほうが良いと思って二人には他の問題にとりかかってもらうことにして、ぼくが問題Eのデバッグに回る。二人は問題Gにとりかかった。
しばらくしてバイナリツリーがすべて生成されていないことに気づいて、そこのコードを修正してsubmit。しかしまたもやWA。ぼくもハマってしまったか、と思ってしばらく悩んだ挙句、コピペミスが発覚。そこを修正してsubmit。
これで通らなければもうあきらめるしかないと思っていたけど、AC。なんとか救われた。


残りの1時間弱では一問くらいしか解けないので、既に少し考えた問題Gと既にACしたチームがいる問題Dのどちらを解くかで悩んだ。
しかしどう考えても問題Dは探索問題。ごりごりと実装しなければいけないのでデバッグに時間がかかりそうだし、ACしたチームも大して多くはない。
なので、問題Gに全力を注ぐことに決定した。
しばらく考えた後、これで上手くいくんじゃないだろうか、という仮説が頭に浮かんできた。妖精さんが降臨したというか、もしくは電波を受信したというか。
上手くいくことの証明は出来ていなかったけど、もう既に時間が残り30分くらいに
なっていて迷っている時間がなかったので、実装を開始。
コーディングはぼく、YAMAにナビゲータになってもらって、toyoは仮説の証明or反例の作成をやってもらうことに。


しかしなかなかバグが取れず、残り15分になったくらいから焦り始めて、すごい勢いでデバッグ。ここら辺は本当に必死で、脳内CPUの使用率が150%を超えていた気がする。延々とstd::cerrデバッグをやって、やっとバグが取れて、一応仮説どおりのプログラムが完成。
祈る気持ちで、コンテスト終了の1分前にsubmitした。
その方法が正しいかどうかは結局証明できていなかったので、仮説が間違っていればアウト、合っていたとしても実装にバグがあればアウト。
返答が帰ってくるまでの約30秒間は長かった。そして画面にポップアップしてきた、ジャッジからの返答メッセージ。

Problem: G
Answer: Yes

思わず「やったー！」と叫んでいた。*1


そしてそのあとすぐに終了のカウントダウンが始まった。
five, four, three, two, one, zero.
会場いっぱいに響く、お互いを称える拍手。
コンテストが終わった。


_oopの成績は、9問中6問正解。去年3問しか正解できなかった雪辱は晴らした。

*1:そう、会場にいた人は聞いたと思いますが、終了間際に叫んだのは私です。