skyaozoraの日記

競技プログラミングの練習法について

17:39

CompetitiveProgramming Advent Calendar Div2012の13日目の記事です。今回は、競技プログラミング（特にTopcoder）の練習法について書こうと思います。正直自分もまだまだ競技プログラミングに関して修行が足りていない身ではありますが、一応ある程度の経験はある訳ですし、ことTopcoderにおいてはRedCoderという実績があるので、少しはみなさんの上達の助けになるのではないかと思いましたので。あと、「上達するには練習問題をとけばいいって言うけど、どう解けばいいのか分からない」という意見も見かけたのもこういう記事を書こうと思ったきっかけです。

練習問題の解き方

まず普通に問題を開いて、自分で解法を考えてコーディングしてデバッグしてをやってみましょう。それで正解できればもちろん問題無いですが、どうしても解法が思いつかない場合、又は解法は浮かんだのにどうしても答えがあわないといった時は、答えを見てしまいましょう。答えというのはその問題に対して正解したコードのことです。答えを見てしまうというのはギブアップして安直な道に進んでるみたいで抵抗があるという方もいると思いますが、いくら考えても出てこないものは出てこないで、ストレスを溜めてしまう前に答えを見てしまいましょう。（むしろ自力でスラスラ解けるような問題だったら解いてもあまり練習にはなりません。確かに解くスピードは上がりますけど…）

で、答えのコードを見て解法を理解したら、実際に自分でその解法を実装して通してみましょう。ただ他人の答えを写すだけなんて…と思う人もいるかもしれませんが、この「実際に自分で実装して通す」という過程で身に付くものも多いので。コードを見てどのような処理が行われているかを把握して、自分で考えてコードを書くというのが理想ですが、行われている処理が良く分からない場合はコードを丸写ししてみるのもいいと思います。丸写ししているうちに「そうか、ここではこういう処理を行っているのか」と気付くこともあります。

で、この「実際に正解したコードを見る」という過程が重要なために、練習に使用する問題としてはTopcoderのSingleRoundMatchで出題された問題を使うことをお勧めします。ArenaのPracticeRoomで練習すれば手元の環境は必要ありませんしね。PracticeRoomではwriter解を始めPracticeRoomに提出された他のコードを見ることも出来ますし、TopcoderのサイトではそのSRMの本番中に通ったコードを見ることも出来ます（https://www.otinn.com/のstatistics->sumarriesというところで全てのSRMの結果が見れて、問題ごとの点数の部分をクリックするとその人のコードが見れるのでお勧めです）。コードを読んだだけでは理解できない点はMatchEditorials(TopcoderのページのCompetitions->Algorithm->SRM->Statisticsから)を読めばいいと思います。ついでに言えば、自力で解けた問題に関しても、余裕があれば他の人のコードやEditorialsを読むことによってよりシンプルな解法に気付いたりできると思います。またSRMはDivisionが2つあり、それぞれ難易度順に並んだ3問があるので、問題を解く前から難易度を予想でき、自分にあった難易度の問題を選べると言う利点もあります。

もちろんこれは練習問題に限らず、実際にSRMに出た後も同様です。解けそうだけど解けなかった問題はどこが間違ってたのかを確認してPracticeRoomで通して置くことをおすすめします。やはりコンテストに出たら出っぱなしではなくこの様に復習すると実力は伸びやすいと思います（自分も最初は出っぱなしで灰色でしたが、復習するようになってからちょっとずつレートが上がるようになりました）。

あと余談といえば余談ですが、問題は新しい方から解きましょう。現在Arena上にある最古のセットであるSRM144のDiv2の問題はDiv2にしてはやたら面倒で、「とりあえず最初からやろう」とSRM144から解き始めて心を折られてしまう人もいました。これに比べたら新しい問題の方が簡単ですし、「あ、この問題は本番で解いたし解法も覚えてる」と周りの方に助言してもらえる確率も上がります。

ちなみに、他にもAtcoderやAOJでも正解したコードを見ることが出来ます。こちらはTopcoderと違って日本語なのでその点でのとっつき易さもあると思います。

人にも聞いてみよう

問題を解いてて分からないことがあったら周りの経験者の方にどんどん質問していきましょう。自分も昔はよくchokudaiさんにメッセで質問して答えて頂いてたのが上達の大きな要因になっていると思います。

周りにそういう質問が出来る人がいないという場合でも、Twitterで競技プログラマーの人たちをフォローしてたりすると、SRMの終了直後はみんな問題の話をしてるので、それを参考にしたり、あとは解法に関して質問しても答えてくれると思います。もちろん事情があってTwitterを使いたくないという方もいるでしょうが、そのような場合でも、Twitterの競技プログラマーのリスト（探せば見つかると思います）をブックマークするなどしておけば、SRM直後に問題に関する色々な知見が得られると思います。

競技プログラミング関連の色々なオンサイトイベントに出てみよう！

直接競技プログラミングの実力の向上には関係ないように思えますが、オンサイトイベントに参加することはお勧めします。例えば、今月の頭にあったUTPC2012とかはコンテストの後に懇親会をやってましたし、最近はDeNAさん主催のTopcoderOnsiteInJapanなんかも行われています。

こういうオンサイトイベントに参加してみて、今までハンドルネームしか知らなかった方々と実際に会ってみると、本当に面白くて魅力がある方々だというのが分かると思います。実際に口頭で質問や議論をすることが出来ますし、何より競技プログラミングがもっと好きになれるんじゃないでしょうか。自分も競技プログラミングの問題を考えるのが好きだったっていうのももちろんありますが、それを通じて色々な人と知り合えたっていうのも今まで楽しく続けてこれた大きな理由だと思います。

なので、地理的な問題が無ければ是非積極的にこういったオンサイトイベントに参加してみるのをお勧めします。（もちろんこういうイベントに参加しづらいからといって競技プログラムをやる上で不都合というわけでもないです）

まとめ？

とりあえずこんな感じで、結局殆どTopcoderに関する話になってしまいましたが自分の考える上達法は伝えられたと思います。まぁTopcoderにおける実力が伸びればもちろん競技プログラミングの実力が伸びてるってことなので、他のコンテスト等でも充分に役立つと思います（傾向の違いもあるので一概には言えませんが）。あともちろんここに述べたのはあくまで方法の１つなので、他の方法を聞いてみたり試してみたりするのもいいと思います。ただ自分は（分かる問題も分からない問題も）「実際に正解になったコードを見る」ことが大事だと思っているのでこのような記事を書きました。

それではみなさん、楽しいTopcoderライフを！（2年連続で同じ締め）