UTPC 2009 （続き） - yuizumi’s diary

最近は実践から離れていたから，きっと今一つな成績になるだろう思っていたが，結局は 8 位と昨年並みでなかなかの成績だった．

昨年度と比べると，最初のほうの問題は若干易化したが，後半の問題が難化しているので，全体としては難化したと言ってよいのではなかろうか．実際の結果を見てもそのとおりになっている．

Problem A: 解き方もくそもなかったが，変数の初期化を忘れるというぽかをやってしまってまさかの Wrong Answer を食らう．昼飯を片手に参加していたことが災いしたか．主催者側が解説のときに最初の正答が 2 分強で届いたことに驚いた旨の発言をしていたが，この難易度ならばそんなものだろう．
Problem B: 中学だか高校だかの数学でさんざん解かされた問題そのものなので，解法に戸惑うことはなかったが．データ構造をどうするかで少しだけ迷ってしまった．このあたりの問題が素早く解けるかどうかでコンテストに慣れているかどうかがある程度わかるのではなかろうか．
Problem C: 一瞬は 9!×9! とか無理！と思ったものの，落ち着いて考えれば片方は順番を固定できるではないか，ということでさっさとコードを書き上げたら確率がサンプルと一致しない．えっ，勝敗は獲得したカードの枚数ではないだって？なお，ご多分にもれず stl::next_permutation() を利用した．私はインデックス（置換ともいう）で順列を作るのでソートを忘れるというミスはそもそも起こらない．
Problem D: いかにも作業問題で一目見たときの面倒さに身がたじろぐ．年をとった証拠に違いない．仮数部の処理はまあまあうまいことまとまったほうだと思う．
Problem E: 最初は「これは典型的なメモつきミニマックスの問題だ」とさっさとコードを書き上げるが長さが 20〜30 でも重くて話にならない．手順によらずに勝敗が決まることがなかなか見抜けなかったので苦労した．
Problem F: 下から昇っていけばステップが一意に決まることに気づかなかった．メモつきの幅優先と深さ優先の両方を試すが，状態数が 50K×50K もある時点で終わらないものは終わらない．もっとも，ビット演算とかいう名のベクトル演算器を駆使すれば終わるらしい．入力の最大長を倍にしておけばよかっただろうに．
Problem G: 少し考えて，同一人物が二回挨拶した時点で挨拶が終わらないことが確定するとわかったので，幅優先探索でループを検出しておしまい．
Problem H: 頭の片隅でずっと考えてはいたが確信の持てる解法には至らない．横線がキーになるのだろうと考えていたところ，想定解法では高さがキーになっていたので，思わずチャットで「そう来たか」という趣旨の発言をしてしまったが，横線たちは頭の中では当然のごとく（縦方向の位置で）ソートされていたことから実質的には同じことである．しかし，想定解法では妙に複雑なデータ構造が現れたので，思わずチャットで「これは解けない」と発言する．
Problem I: ねこの扉→人間の扉→ねこの扉という一連の流れは見抜けたが，そこから dijkstra を 3 回まわすというところに行き着くまでが大変だった．ちなみに，コンテストの最後のほうになって「れのんは確実に脱出できるか」と聞いたのは私である．長年の経験から，脱出失敗時の記述がないのは，該当するテストケースは最初から対象外にしていたため存在を忘れていただけだということはわかっていた．単に Wrong Answer ではまっていたので腹いせ（ぉ）に確認したにすぎない．ちなみに，人間の扉をひとつもあけずに脱出できるというケースを忘れていた（手元で挙動を確認しているときにたまたま気がついた）．
Problem J: いかにも面倒そうだったのでとっとと捨てた．このレベルの問題ですらも時間内に解かれてしまうのが，現在の日本における ICPC のレベルである．
Problem K: (ごにょごにょ)＝B(B-1) という等式がいかにもあやしい，というところに行き着くまでは何分もかからなかったが，その後を考えるだけの気力，知識，センス，時間の少なくともひとつが足りなかった．
Problem L: どうせラスボス（笑）とか最終防衛線（笑）とか呼ばれる類の問題だろうと思っていたので捨てた．昨年度よりは易しいかと思ったが聞いてみるとそうでもなかったらしい．