この記事はCompetitive Programming Advent Calendar Div2012 12/3の記事として書かれたものです。
こんにちは。tozangezanです。一応今年はIOI2012に日本代表として参加してきました。それから、今年は大会で優勝が1つも取れませんでした。気がついたら受験生になってしまいました。
今日はJOIを初めとした、大会経験のあまりない初心者向けとしてプログラミングコンテストへの作戦的なものを書こうと思います。アルゴリズム的な話題はすでにいくらでも記事があるでしょうし、このAdvent Calendar中にいろいろな人が書いてくれると思うので、アルゴリズムの話題からすこし離れたことを並べていきたいと思います。JOIは高校2年生以下しか参加できませんが、大学生以上の方も部分的に内容を役に立ててくれたら嬉しいです。
・予選対策
予選は、比較的特殊なコンテスト形式です(Google Code Jamと同じ形式です)。課題と入力ファイルが与えられるので、その入力ファイルに対する出力ファイルとソースコードを提出します。ただし、(おそらく)審査の対象になるのは出力ファイルのみで、ソースコードは実行していないと思われます(本当にそうなのかは分かりません)。また、予選は好きなプログラミング言語で挑戦することができます。多分Excelでも参加できます。
このような変わった形式のコンテストなので、普段と違う点を意識しないといけません。重要なのは次に挙げるようなものです。
・入出力をファイルに行うこと
初心者はここで戸惑うことが結構あります。ファイル入出力の関数は実を言うと僕も書けないのですが、CygwinとかLinuxのterminalとかを使っている人なら標準入出力の仕様でソースコードを書いても、実行時に標準入力のかわりにファイルから読んだり標準出力のかわりにファイルに書き出したりできます。入力のほうは「< ファイル名」で出力のほうは「> ファイル名」です。
Cygwinなら、「./a < in.txt > out.txt」、terminalなら「./a.out < in.txt > out.txt」とかすれば、in.txtから読み込んでout.txtに書き出すことができます。
・実行時間制限・メモリ制限がいくらでもあること
いくらでもあるといっても、さすがにコンテスト時間は3時間で、メモリだって自分のPCに入ってる量しか使えないので有限です。しかし、予選では10分動かして一つの出力を出しても問題ないのです。ですから、ある程度オーダーを見積もって、だいたい計算量が10^10(100億)とかになるのなら、それをそのまま実行してゆっくり待ってみてもいいかもしれません。ただしその間の時間を無駄にしないように他の問題を解くのとかに充てたほうがいいと思います。あと、こういうことをする時はコンパイルのときにファイル名と一緒に「-O2」と書いておくと実行が速くなるのでおすすめです。
それから、さすがに実行時間制限がないとはいっても、満点解法が多項式時間(O(N^3)とか)の問題を指数時間(O(2^N)とか)の解法で満点取るのは無理だと思います。見積もりましょう。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0537 とか
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0548 とか
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0570 は待つのに適しています。とはいってもどれも予選6だし解けなくても通過できますね。確か中3のときのJOIでトナカイが出て、(いろいろあってコンテスト時間が5時間に延長されたので)1つのファイル10分くらいかけて解いた覚えがあります。
・フィードバックが帰ってこないこと
JOI予選は入出力例が1つだったり2つだったりする問題が非常に多いです。しかも自分の出力がどのくらい合っているのかがコンテスト中に把握できないので、バグで20点落としている可能性がなかなかぬぐいきれないので心臓によくありません。ということで、時間があるなら慎重を期して新しく入力ファイルを自分で作ってみたり、入力1(大概結構サイズが小さく、手で試せることもある)とかを自分で手で解いて答えがあっているかどうかを確かめるのもよいでしょう。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0569 僕は去年の予選でこの問題の入力1をペイントを使って手で合ってるかどうか確かめました。(ペイントを使うのが合法的どうかはグレーですがまあMathematicaも使ってもよいらしいので大丈夫だと思います)
・提出する量が多く確認も出来ないこと
提出ミスが毎年多いです。現在レッドコーダーのあの人も提出ミスの経験者だったりします。6問あってそれぞれファイルを6つ提出するので36回も提出ボタンを押さないといけません。出力ファイルの番号はあっていますか？ソースコードの番号はあっていますか？よく確認して提出しましょう。競技中に自分が提出したファイルをダウンロードして自分で見ることもできます。確認するのに活用しましょう。
・満点を取ると図書カードがもらえること
満点めざしてがんばってください。特に予選免除の人(ima1000とか)は6番から逆順に解いて、その問題が解けるまで次の問題が解けないみたいな縛りプレイをするといいと思います。予選が免除されてるのに4点～116点を取るとか恥ずかしいですよね！？
以上のことに気をつければ多分予選は乗り切れます。がんばりましょう。
・本選対策
本選はよくある感じのプログラミングコンテストです。交通費が全額(学割で余る人もいる)支給されて、1泊2日で無料で宿泊ができます。宿泊にするかどうかは選択制ですが、多くの人が宿泊するので、「しない」に丸をつけてしまった人は毎年後悔しているようです。合宿行くのは妥当に競技強い人が多いですが、ときどきどう考えても合宿いける実力があるのに変な理由で落ちてしまう人もいるので、事故らないようにこんなところを気をつけてみるといいでしょう。
・フィードバックを活用する
本選はソースコードを提出する形式で、ソースコードを提出用のサーバーに提出するとテストケースにあっているかどうか(正解か、不正解か、時間オーバーしてるか、メモリオーバーしてるか、変なエラーかなど)が返ってきます。問題によってどのくらいの量の情報が得られるかどうかが違います。Over View Sheet(配られます)に
「完全」と書いてあったらすべての採点データの正誤ともらえる点数がすべて分かってしまいます(満点取れてたらこの問題もう見る必要ないですよね)
「部分」と書いてあったら採点データの一部の正誤が分かります。しかし何点もらえるかも、他のデータがどのくらい合っているかも分かりません。「一部のデータ」が偏っているかもしれません(すべて部分点解法用とか)
「例のみ」と書いてあったら入力例のデータの正誤しか分からないのでほとんど意味がありません。残念でした。
基本的に問題が簡単な順に「完全」、「部分」、「例のみ」となる傾向がありますが、IOIではどの問題も完全だし、一概に完全フィードバックの問題が簡単とはいえないと思います。ただし今までのJOIでは完全の問題は簡単に作られています。完全フィードバックの問題が多いといいですね！
・巨大な配列を取るときは
大きな配列が取りたいときは、グローバル(関数の外)で取るか、staticをつけましょう。これで死んでる人を何人か見たことがあります。特にTopCoderしか対策しない人に多いですね。
・1日目について
合宿行きたいんなら早く寝ましょう。合宿いったら7日間あるんだからそのときに遊べばいいじゃない。
以上のことに気をつけて問題解きなれとけば本選は通過できるでしょう(ただし最近はここらへんのレベルがすごく上がってきています)。がんばってください。
・合宿対策
合宿はさすがに慣れてる人たちが慣れてる形式でコンテストをやる場みたいな感じになってるので、問題やりこんでおけば問題ないと思います。気をつける点といったら…
・時間配分
今年の合宿は5時間で3問でした。それより前も5時間で3問の日があることが多いので、5時間3問という形式で行われるとします(去年まで5時間4問とかあったけどあんなの時間足りるわけないと思います)。まず問題文は全部読みましょう。時間はたっぷりあるので。それから部分点も取れそうなものはすべて取りにいきましょう。時間はかなりあります。
問題はデバッグPhaseになったときとかです。今年の合宿のFish、IOIのtournamentはかなり長時間デバッグしていたのですが、だらだらデバッグするのは本当に効率が悪く無駄です。割り切って集中して考え直すとか、ソースコードを書き直すとかをやったほうが結果的によいことがあります。特にiteration。
あと、output onlyがある日は、他の問題が解けなくて詰まったらoutput onlyをやるのも1つの手だと思います。今回はかなり直前に改善してみたので再提出が5個中3個しかできなかった…
・全問解き終えたら
全部解き終わったら小さいケースを全探索するソースコードを書いて、それからランダムに小さめのケースを生成するソースコードを書いて、答えが本当に合っているか照らし合わせてみましょう。ただし、ときどき全探索コードが間違っているせいで2つのプログラムで答えが違うということになることもあります。
・3日目で2位の人と300点差がついたら
4日目はどこかに遊びに行きましょう。
・俯瞰
・スモールマスコットが本選や合宿に持っていけるはずです。スモールマスコットを持っていくのも交流とかで役に立つかもしれません(それから単純に見ていて面白い)。僕は本選と合宿にはルカリオを、IOIには国立科学博物館で買ったオオカミのぬいぐるみを持っていきました。他の国の選手もだいたいそんな感じのものを持ってきていました(スウェーデンの人のスモールマスコットはシロクマでした)。別に▲ペロリン▲じゃなくてもよいです。
・JOIに参加するかどうか迷っている人は、遠慮せずに出てみると良いと思います。オリンピックとか名前が高尚そうに見えますが、敷居はパソコン甲子園くらいの高さだと思うので、出て損することはないですよ！
・同じ学校で競技プログラミングをやっている人がいると、問題に関して話をしたりとかできてすごく良いと思います。だからと言ってそんなに簡単に競技プログラマーが増えると思いませんが……
読んでくださいましてありがとうございました！JOI予選がんばってください！
(本当に大学生以上が読むところが無かった…)
