ICPC 2008 アジア地区予選 参加記
本番で書いたコードが送られて来たら思い出しながらしみじみ書こうかと思ったんですが、一向にその気配が無いので今更ながら書きます。とりあえず当日だけ。僕たちはトップチームとかでは全然ないので参加者が読んでも新たな知見を得られたりするわけではありませんが、これを読んだ人が興味を持って来年参加してくれたりしたら良いかなぁと。時間は覚えてないのでかなり適当です！
-75分
戦いは朝食から始まってました。スケジュールが全く同じ参加者全員が一つのホテルに詰め込まれているため朝食バイキングに長蛇の列が。30分以上並ぶ人もいたような。僕たちのチームは並ぶのに20分位かかって、食べ終わって出た時には40分位経ってたと思う。でも美味しかったから良いです。アホほど食った。
バスに乗って会場に到着すると既に開始10分前。余裕持って起きたはずなのになぁ。机の上に筆記用具等を並べて準備をし始める。
-5分
他のチームの人がなかなか集まらない。おそらく朝食のせい。ざわざわ。開始1分前になっても会場に入る人の流れは止まらない。こんな状態で始めるのかなぁ、えー始まった。
0分
心臓ばくばくになりながら封筒を開けると、なんと、問題セットが1部しか入ってない！これはひでー。去年はちゃんと3部あったような気がする。メモ用紙はどうしろって言うんだろ。とりあえずAとBの読解をお願いして自分はテンプレートや.emacsを書き始める。
5分
テンプレート書き終わる。Aを読んでた人に問題の説明をお願いするも、全然分からない。ただ大変分かりにくい問題だと言う事はわかった。他のチームも風船上がってないし、とりあえず焦らず、分かったらまた教えてーと言ってBを聞く事にする。
10分
Bも分からないｗこれは俺に問題があるのか。でもBは疑似コードを紙に書いてくれると言うので、書き終わるまでAに取り組む事にする。
25分
Aの説明にまだ曖昧な所があるけど、とりあえず書かなければ始まらないので書く。でも書いてて分からない所を聞いても返事が曖昧だ。うーむ。書き終わってもサンプルと一致しない。ちょっとこの流れはまずい。するとBの疑似コードが出来たというので再びBにスイッチ。
35分
Bの疑似コードを打ち込んだらサンプルと一致した。おーー！Submit & Accepted。結局Bを一番最初に通してしまった。終わった後で他のチームの人に「今年のA分かりづらかったですよねー」と言ったらみんな同意してくれたけど、「B先に通しましたよー」っていったら同意してくれなかった。
50分
Aの問題解釈が何度も変わってコードがぐちゃぐちゃになりながらも、ようやくサンプルと一致するコードが出来たので送信。Accepted。うーむちらほら4問通すチームも出始めた。まずいまずい。
60分
Cを聞いたらなんだか簡単そう。シミュレートして探索するだけか。探索部分が気になるけどとりあえずシミュレート部を書こう。三つの針の位置から時間を逆引きするためにvector
80分
シミュレート部が完成したので探索部分を書く。針の割当はnext_permutationした後で0~59を足して60でmod取ってやれば良くて、後は単なる探索を書くだけ。おっけー楽勝ーと思って書き始める。とりあえず全探索を書いてサンプルと一致したので、送信。TLE。げーやっぱ深さ12で全探索は辛いか…。考えるのが面倒だったので適当に枝刈りを入れる（現在までの最小の時間差を保持して、超えるなら枝刈り）。速くなったので送信。が、WA！サンプルと完璧に一致してるのでどうしようもない。枝刈りも間違ってない。うーん。PCの前で悩んでも仕方ないのでコードを印刷して紙デバッグをお願いする。
100分
まぁ目標6問だから1問50分で解けば良いわけで…と鼓舞。たださすがに2問しか解けてないのはまずかろう、と思ってstandingsを見ると、意外とみんな解けてなくて、10~12位くらいだった気がする。
問題解説をしてもらってFが見るからに探索なので次に取り組む事に決める。
120分
今度はじっくり解説してもらう。6色に塗り分けられた6面体をxy平面上で転がしていって目的地に辿り着くまでの最短ターンを求める問題。ただしマス目の色と6面体の上の面の色が一致するようにしか転がせない。なるほどねーサイコロと幅優先探索ね。状態数を計算するに、幅(30)*高さ(30)*サイコロの状態(24)*どこまで色を踏んだか(6) = 13万。楽勝でメモリに乗る。やるだけじゃん。うまい。spaghetti sourceのサイコロを写経して、dice
160分
Fをやっている間にstandingsを見て次に解くべきだろうと決めていたGに取りかかる。チームメイトに解説してもらうと、要するに長さ5000の文字列が与えられるので12個の単語のpermutationと一致する箇所を求めろとの事。箇所なので、文字列がaaで単語がa,aの時は2ではなく1になる。naiveには5000*12!だけどこれは終わらないな、と思っていると本文にも終わらないと書いてあったらしい。親切すぎる。こんなの誰もひっかからないだろー。疑似コード（深さ優先探索）まで書いてもらっていたので書き写し、サンプルと一致したので送信。TLE。はい。
180分
定数倍の最適化を何度か施し（てTLEをもらっ）ている間にチームメイトが最悪ケースを考えてくれていた。文字列がa...(5000)で、単語がa,a,..,bの場合。5000回単語に関して深さ優先探索するコードだったので、全てのpermutationが一致しない場合に結局5000*12!かかってた。はい。流石にnext_permutationは回避したものの見事にひっかかってました。しかしこれは別のアプローチが必要そうだ。
200分
CのバグをつぶすかGを考えるかで迷う。Cは全く糸口が掴めない。一方Gは計算量的にDPしか無いような気がする（文字列の長さが既に5000なのでせいぜいその10000倍位の計算しか必要でないはず）。チームメイトに了解を取ってGを進める事にして、Cのデバッグと問題読解を引き続きお願いする。
210分
PCの前に誰も座らず紙に向かう時間が始まる。GがDPだとするとまず計算途中の状態というのをはっきりさせないといけない。どのような情報があれば、ある箇所に全ての単語を使用したマッチが可能か分かるのかを考える。単語全体の集合をSとしてpermutationの最後で使う単語をs1とすると、s1以外の単語の集合S'を使って直前までマッチ出来た時にそこでs1がマッチ出来れば良い。もっと言うと単語の順序は必要なくて、どの単語を使用した時にどの箇所でマッチできるかが分かれば良い。使った単語の集合は単語の数が12個までなので12ビットあれば表せる。ビットDPか…ICPCではゆるいDPしか見た事ないし自信無いなぁ。と思いながら計算量を見積もると5000 * 2 ^ 12 = 2000万。dp[5000][1 << 12]はboolで取れば20MB。ぴったりだ、間違い無い。コード自体はシンプルになるので簡単なコードを書いてサンプルで試してみると、出力は少し間違っているものの計算自体は一瞬で終わる。おーー来た来た！
230分
Gを手直しすると出力が合うようになったのでSubmit。どきどきしながら結果を待っていると、なんとTLE。えーー。とここでチームメイトが紙でバッグでCのバグを発見してくれた。0~59までの値を足して60でmodを取る部分で、for文の終了条件がなんと「0 < 59」になっている。うわ！！これだこれ！59を意識しすぎていたのか何なのか。「0 <= 59」に書き換えて送信。これでWrong Answerだったらどうしようもないなーとか思って待っていると、今度はAccepted。よしこれで4問目。
250分
Gは計算量的にTLEはあり得ないので遅い原因を探す。と、単語が文字列とマッチするかを判断している部分が、あらかじめ5000箇所 * 12単語だけ計算すれば良いはずの所ループの中で繰り返し呼ばれている。これを外に追い出してみると数倍速くなったので送信…Accepted！浮かれてチームメイトと抱き合う。
260分
残り40分。解法さえ分かればもう一問いける時間。standingsを見るにDとEのどちらかを解く事になりそう。Dが強実装でEが空間幾何、どちらかと言えばEの方が解いたチームが多い。けれどもうちのチームに幾何要員は居ないのでDに行くしかない。直線が沢山与えられるので、それらをデジタル表示の数字（0~9)として見なした時に、それぞれの数字がいくつ出現したかを数える問題。直線はそれほど多くないので全対全で交差判定をしてUnionFindで分類して、それぞれの数字を構成するらしき直線の集合ごとに処理してやれば良さそう。チームメイトによると、直線が一本だけだったら1しかあり得ないし、四本で交点が四つだったら0しかあり得ない、みたいな調子で直線の数、交点の数、交点の種類（端点を共有するのか直線上に端点が乗るのか）を用いれば、2と5を除いて分類できる。2と5だけはccwで角度を調べないといけなくて少し面倒。との事。素晴らしい。ここまで来ればあとは実装を頑張るだけ。書いて書いて書いて書いて書く。
299分
書いて書いて書いて書いて、250行を超えようかという所で残念ながら時間切れ。書き始める前にもう少し整理するべきだった。。。
300分
疲れたー。結局試合中に席を離れたのは一度だけで軽食を食べる時間がなかったのがちょっと残念だった。その後選手の所まで来てくれたコーチと感想戦。GはDPだったとかDが面倒過ぎたとかFは実は簡単だったらしいとかそういう話をした。
