The University of Aizu Programming Contest 2009 Spring
大きな混乱も無かったわけではありませんが、どうにか無事終了しました。
参加していただいた皆さん、ありがとうございました。
暫定ですが、上位入賞者は以下の通りです。
- 1st Place LayCurseさん
- 2nd Place konakonaさん
- 3rd Place iwiwiさん
おめでとうございます！
現在のところ審判データの間違いは見つかっていませんが、正解者の少ないいくつかの問題について最終確認を行った上で最終結果が公表される予定です。
講評は後日公開されるかもしれない（まだ作ってないです）ので、ここでは簡単なコメントなどを書いてみます。
Problem A Vampirish Night
原案と問題文と審判データと模範解答を担当しました。
A問題は簡単な実装問題であるべき、というコンセプトに従って、なんの引っ掛けも無いタイピング問題になってます。
Problem B Cleaning Robot
問題文（日本語のみ）と模範解答を担当しました。
問題文の良いコンテキスト無いですか？とコーチ（原案担当）に訊かれたので、同じように正方形グリッドをうろつく問題のF問題と強引にくっつけました。
サイズの小さい、基本的な確率DP問題。なのに行列のn乗で解いた変態もいるとかいないとか。何の工夫もせずにDFSするとTLEになり、BFSするとジャッジサーバが落ちます。落ちました。
Problem C Emacs-like Editor
私はノータッチ（一応全ての問題に目を通して校正などのチェックはしていますが）。
Clarは来たものの、ジャッジミスはどうやら無いものと思われます。Emacs嫌いが何人も生まれた模様。
Problem D Indian Puzzle
ノータッチ。
バックトラック+構文解析というしんどい組み合わせですが、問題を抜かりなく定義するのもまたしんどかったみたいです。与えられたパズルの中で既に間違った等式が完成しているようなケースも特に禁止されていないのですが、本当に審判データにそんなケースがあるのかは謎。
Problem E Amazing Grace
原案と問題文と模範解答を担当しました。審判データはチームメイトのnobにお願いしました。
入力こそ大きいですが、制約が色々あるので答えはそこまで大きくなりません（おそらく最悪ケースでも500,000程度）。それを利用するとても簡潔なコードが書けます。
が、やっぱりタイムリミットは少し厳しかったかもしれません。
Problem F Cleaning Robot 2.0
問題文と模範解答を担当しました。
原案のnobから解法を聞いたものの何故それで正しく動くのか最初は全然理解できなくて、証明を書いたりnobに訊いたりしながらやっと（まだ不完全ですが）納得しました。アイデアはそれほど難しくないのですが、何も無いところからそれを閃くのは変態技。何考えてたらこんな問題思いつくんだろう・・・。
驚いたことに、最終的な解答は O(N^2) の計算量になります。
Problem G Building Water Ways
ノータッチ。
あまり自明でない枝刈りをいくつか入れた反復深化で解く問題・・・のはずが、LayCurseさんはDFSで簡単に解いたそうです。コーチ（原案担当）も首を捻るばかり。最終ではないもののそれなりの防衛問題だったはずなのですが。
Problem H Hedro's Hexahedron
問題文と模範解答を担当しました。
問題文で遊んでみました。サイシュウボウエイモンダイは「溶けない」と「解けない」を掛けていたりとか、他にも言葉遊びが色々詰まってます。そんなわけで、これ自体が最終防衛問題というわけではありません。
粘液が触れる部分の形の曲線の式が分かったら、あとは境界値の扱いに気をつけながら O(sqrt(n)) で頑張る問題です。
Problem I A Piece of Cake
原案と問題文と審判データと模範解答を担当しました。
このコンテストには会津大学の下級生や高校生が多く来るだろうと踏んでいたので簡単な問題を用意したのですが、思ったよりも赤い人たちの参加数が多くて、あっという間に解かれていったのでした。
スーパー雑魚問題。そもそも問題名が雑魚っぷりを主張しています。
Problem J ICPC: Ideal Coin Payment and Change
原案と問題文と審判データと模範解答を担当しました。
一度書いた問題が気に食わなくて、今日の明け方に書き直した問題。登場人物の名前も全然捻っていません。
問題文の範囲内でちょっとした罠を仕込んでおきました。そもそも気付くことすらなく回避した人がほとんどだと思いますが、もし引っかかった人がいたらごめんなさい。
これも少しタイムリミットが厳しかったかも。
その他、どうでもいい話をつらつらと。
- OB/OG会を見てもMaximum-Cupを見ても審判団は8人ぐらいいるものなのですが、このコンテストの審判団は3人。かなり大変でしたが、とにかくジャッジミスも（多分）無く終わってよかったです。
- ちなみに3人のおおよその役割は、コーチ……実装系の難問、Watch.c::nob……アルゴリズム系の難問、私……簡単な問題 + nobの問題の文章作成といった感じです。が、文章作成に手間取ったおかげで私のやるべき仕事がどんどんnobに降りかかっていきました。ごめんなさい。そしてありがとう。
- 夜になってトライアルに偉い人が続々とやってきたので驚愕。3時間ぐらいで全完されたりしないだろうかと不安になる。嫌な汗が出てきた。
- コンテストが始まってすぐ、Problem Aの日本語版がトライアルのものになっている手違いが発覚。よく分からないけど何故か起こってしまう現象だそうです。トライアルに参加しなかった何人かは引っかかってしまったみたいで、申し訳ありません。あと、トライアルに参加しなかった人はバージョン違いのせいでコンパイルエラーを何度か貰っていたり。
- 自分の作った問題を解かれるとこれほど安心するとは思わなかった。逆にWAされるとジャッジミスではないかと疑い、TLEされるとTLが不適切ではないかと疑い。後半になってくると落ち着いてきましたが。
- でもジャッジって面白いですね。さすがに何度もやる元気はないですけど。
- 上位の人たちはだいたい見たことがある名前ばかりですが、でもkonakonaさんって誰なんでしょう？分からない。けど無茶苦茶強い。
- 一方振るわない会津大生。6問ぐらい解いて欲しかったんだけどなー。
- コンテストは終わってるのにまだ送信は受付中。審判団は昨夜あんまり寝てないので、今日はもうジャッジをどうこうする気力はないんです。明日にでも送信は出来なくなりますが、同時にProblem Setに追加されると思います。多分Volume10の1019 - 1028あたり。
繰り返しになりますが、皆様のご参加ありがとうございました。次回の開催は未定ですが、もし機会がありましたらよろしくお願いします。
