■ [部活]ReadingPhase攻略 
これはCompetitive Programming Advent Calendar（2011年）の21日目の記事です。
コンテストに参加していて、解法がわからなかったのではなく、問題の内容を理解できなかったりちょっとした見落としがあったりで解けなかった、というのは大変つまらないものです。
そんなしょうもないところで嵌まらないための対策を考えます。
問題文を読む
数学的な用語に関しては、だいたいは単語帳引くなり検索したりすれば意味はわかるでしょうが、それだけでは引っかかってしまう表現があります。
思いつくものをいくつか挙げます。他にもまだあると思うので、気づいた人はコメントなりつぶやきなりで教えてください。
- ascending
- 小さいものから大きいもの順。increasingも同じです。descending/decreasingはその逆。
- この単語だけでは、隣同士がイコールの場合が含まれるかどうかあいまいです。問題文の周囲に書いてあるはずなので確認しましょう。イコールが許されない場合は"strictly ascending"とか。
- lexicographical order
- integer
- 整数ですが、問題文によっては勝手に正の数とか0以上とか思い込んでしまう場合があるので注意
- その場合はたいていpositiveとかnonnegativeとかが付くと思います
- number
- 上と同じく、小数もあり得るのに勝手に整数だと思い込んでしまう場合が
- square
- 正方形です。長方形はrectangleです。
- 【追記】more than
- 「〜超」です。「〜以上」ではないです。単語を直訳して「より 大きい」と読むと勘違いしにくいのでは。less thanも同じく「未満」。
あとまれに、「この単語なんだよ意味わかんないよ」と思っていたらただの人名だった、ということもあります（自分だけ…？）。
タイムリーに今月のZOJ MonthlyのHで出くわしました。"mm"って名前があるの
ただ、ここで一番重要なのは「焦るな」ではないでしょうか。
問題文を急いで読んだところでせいぜい数十秒の差です。でも問題の内容を間違えて解釈してしまったら数分かそれどころじゃない差です。
入力の制約を読む
入力の最大値を確認するのは基本ですが、それ以外でも、ちょっと珍しい制約があったらそこが解法のキーになることもあります。敏感になっておきましょう。
例：
- SRM476 Div1-550 "FriendTour"
- 「Each element of friends will contain between 1 and 36 characters」
- UTPC2011 "巡回セールスマン問題"
- 「M ≦ N + 500」
- Xmas contest 2010 "Connect The Decoration"
- 「si の総和は 10 以下である」
加えて、最小ケース付近で何か特別なことが起きないかも確認する癖を付けましょう。
サンプルを読む
サンプルは有効活用しましょう。
特にTopCoderではサンプルが親切で、解説まで付いていることが多いので問題理解に大変役立ちます。
問題文が理解できないときは、とりあえずサンプルを眺めてみるとわかってくることがあるかも。
サンプルには簡単過ぎるケースも多いですが、ちょっとでも自信が無かったら丁寧に確認しましょう。
問題の制約を小さい方にはみ出て、まずは一番単純なケースから考えるのもアリだと思います（10≦NだけどN=1やN=2から考えてみるとか）。
最小のケースから制約を大きくしていって、自明なものが非自明に変わったときのギャップは何だったのか、というところに本質が見えてくることが多々あります。
アナウンスを読む
問題を作るのも人間ですから、問題文に誤りや曖昧な点が含まれていることもあります。
問題に訂正や追加説明が入るときは参加者に告知されますが、集中して問題解いてるのにそんなのなかなか気づけるもんじゃありません。
何かおかしいと思ったら、まずはコンテストのトップページを見るなりしてアナウンスがないかチェックしましょう。
おかしいと思うところがなくても、いつのまにか問題文が書き換わっていたりするので長時間コンテストではときどき息抜き程度に見ておくのが無難だと思います。
また、たいがいのコンテストシステムには主催者へ質問を出す仕組みがあるので、遠慮せず使いましょう。
「clar」や「question」、「message」などの言葉が見えるあたりにあります。
多くは「問題よく読め」と返されるオチだと思いますがくじけてはいけません。
何がわからないかを他人に説明しようとしてみることで理解が進む、というテディベア効果もあります。
clarがよく活用されている例：
- http://atcoder.jp/contest/24/detail
- http://twitter.com/#!/tomerun/status/122575122476449794 （GCJJ2011決勝）
コンテストの空気を読む
短時間で限られた数の問題に取り組むというコンテストの性質上、どうしても戦略的なところで結果に差が出てきます。
そんなところで上手くやってちょっと良い順位を取ったところで実力が伴っていなければどうしようもないという面もありますが、参加する以上は良い結果を出したいというのは人情ですし、Google Code JamやTCOの予選のように○○位以内にならないと通過できない、という場合はここが大きく明暗を分けることになります。
問題セットを見る
SRMやGCJ、Codeforcesのように、問題ごとに得点が異なるコンテストでは、（自分にとっての）解きやすさと得点が必ずしも連動するわけでもないので、得点の小さいものから順に取り組むことはそこまでこだわらない方が良いと思います。
特に、SRMで点数が変則的（250-500-1000以外）な場合は要注意です。
SRMで先にMediumやHardを開いておいて、Easyには周囲の提出状況を見つつ心の余裕を持って取り組むという戦略は最近ずいぶん一般的になってきました（自分はやったことありませんが…）。
順位表を見る（中盤）
問題数が多いコンテストでは、多くの人が正解している問題は簡単だろう、ということがわかります。
慣れてくると、通している人の顔ぶれからその問題の解法がどんな分野なのかまで想像が付くようなこともあるかも…（？）
順位表を見る（終盤）
SRMでは、再提出している人がどれだけいるかをチェックしましょう。上位コーダーが多数再提出していたら、どこか罠があるだろうというのがわかります。
残り時間内にあと1問解けるかどうか、というときは、各問題を最速で正解している人の提出時間から、気づけさえすればすぐ書けてしまう（望みがある）ものなのか、アルゴリズム考えても書くのが大変（望み薄）なのかがある程度判別できます。
もちろん、もうちょっとで解けそうな問題がある、という状況ならば気を散らさずそれに集中したほうが良いです。
ただし順位がとても重要なコンテストの場合は、その問題を正解したとしてボーダーラインに入れそうかどうかも気にしましょう。
