大学の授業でICPC対策 - Competitive Programming Advent Calendar
若輩者ながらCompetitive Programming Advent Calendarに参加させていただきます。
僕のは体験談のようなものなので、気軽に読んでください&長文で申し訳ないです。
今回は大学の授業としてICPC国内予選を突破するための対策を行ったときの話をしようと思います。
経緯
僕は大学３年の時に初めてプログラミングコンテストというものを知りました。これがACM−ICPCです。2年の授業でC言語によるプログラミングを習い、「プログラミング面白い！」と思っていた僕は、すぐさま参加を決めました。結果的にその年(2010年)のICPC国内予選を突破し、アジア地区予選に進出することができたのですが、これはほぼすべて先輩の能力の賜物といってよい状況で、先輩がいなくなってからも予選を突破できるか不安に思っていました。
そんな中迎えた3年後期、必須科目の中にコンピュータサイエンス実験2という授業がありました。これは「数人でチームを組み、課題に対する小研究を行う」というものです。この「課題」は教員から与えられたいくつかのものから選ぶのですが、最後の一枠に「自由課題」というものがあり、この枠では「顧問となる教員が見つかるなら、何をやってもよい」のです。他の課題を担当していなかったICPCに積極的な先生が「ICPC対策なら担当になってもよい」と(おそらく冗談くらいのつもりで)言ったのを聞き逃さなかった僕は、すかさず有志を3人集めてICPC対策をテーマとして申請し、次年度も国内予選を突破すべく対策を始めました。
前半
とりあえず最初に始めたことは、プログラミングコンテストについて書いているWebページ・書籍などをしらべ、情報をまとめることです。この時の情報整理には「KJ法」というのを使いました。これは、とにかく断片的でもいいからキーワードのようなものをメモしまくって、あとでそれをグループ化して階層構造や関係付けを持たせることで、全体像を掴むというものです(たぶん)。先生はこのKJ法をやたらとプッシュしまくっていました。というのも、「たぶん成果が微妙になるだろうから目立つ手法とか使っとくか」的なノリだったんだろうと思います。僕はガチで国内予選突破したかったのでそんなのはどうでもよいと思いつつも、単位が恋しいのでやりました。もちろんこれをやったおかげで乏しかったプロコンの知識がついたのでとても感謝しています、はい。
こうした調査の結果、重要な要素として、「アルゴリズム」「デバッグ」「チーム戦略」などが浮かび上がってきました。この辺で最終目標として「マニュアルを作る」という形を意識し始めました。実験の期間中に国内予選はないですし、成果としてあげられる「もの」がそれくらいしかないだろうと思ったので。しかしながら、マニュアル系の書籍として既に「プログラミングコンテストチャレンジブック」(通称・蟻本)という神本を始め、多くの書籍やWebページが存在するので、これらとの差別化を図らなければなりません。そこで我々は心を鬼にしてこれらをdisりつつ、「自コースから国内予選突破者を増やすことに特化した対策」を行うことで新規性を訴えました。少し具体的に説明すると、
- 国内予選の傾向を分析し、必要となるアルゴリズムの重要度・優先度を与える
- コースで授業を行っている内容については、説明を軽くし冗長性をなくす
- 学科履修言語のCでの実装のみを考える
などです。その他、
等も加え、実用性を向上させる試みも考えました。
中間発表
実験2では、11月の末に中間発表があります。ここまでの研究の進捗を報告し、先生方に意見をもらってこれからの研究に活かします。以下に中間発表の内容の一部を示します。
これは過去の国内予選で出題された問題のカテゴリの構成比を分析した図です。右の「突破最低ラインの問題」とは、各年の予選結果から突破に必要な問題数を調べ、他のサイトの評価を参考に簡単な問題からその数ぶんだけ選んだものです。図をみると、全体として幾何やグラフの出題は多いですが、突破に最低限必要な問題に的を絞ると、これらはほとんど出題されていません。これを理由に僕らは、「構文解析や幾何、グラフなんてほっといて、探索やシミュレーションをきちんと解けるように勉強しろよ、JK」と主張しました。異論は認めます。
ここで教授陣にはいろいろつっこまれましたが、一番印象に残ったのが「もっと問題解け」でした。当時一番解いていた僕でさえ30問程度、他はみんな一ケタ台という有様で、もっと解いた上で考察しなさい、という至極当然の話だったので、後半はそこから始めました。
アジア地区予選
実験期間中に国内予選はないですが、なんとか参加できたアジア地区予選は中間発表後にありました。アジア予選の体験を話しだすと脱線するのでここでは深く触れません。とりあえずむっちゃ楽しかったです。実験の観点からすると、ここで成果が出ると箔がついていい感じだったのですが、残念ながら2問正答の順位なしで悔しい結果となりました。しかし、実験的にも個人的にも対策の必要性をより強く感じるきっかけになったので、良い経験だったとも思っています(事実この後の春休みからTopCoder, codeforcesなどを始めたり、約一年間でAOJの問題を400問程解くなど、それまでとは比べ物にならないくらいプロコンに浸かりだしたので)。この時、chokudaiさんとかimoさんとかusagiさんとかから軽くお話を聞いたり(皆さんはまず間違いなく忘れていると思います)して、勝手に対策の方向性の参考にしました。
後半
後半は先に定義した「突破最低ラインの問題」をひたすら解くところから始めました。このとき、起きたバグ・間違いをすべてメモすることで、デバッグの章にも活かせるようにしました。で、問題をあらかた解き終わったころにはもうマニュアルを書き始めないと間に合わない状態だったので、すぐさま執筆作業に移りました。章立ては、
としました。デバッグは自分たちが問題を解いた経験を反映させました。対策の部分では、傾向分析の結果から、「シミュレーション」「探索」「数論(素数)」「動的計画法」を取り扱う事にしました。動的計画法が入っているのは分析よりも、個人的見解やimoの人たちが言ってたから、というのが大きいのはここだけの話です。実験メンバーにも内緒です。ライブラリには「素数(エラトステネスの篩など)」「リスト」「キュー」「スタック」(CだけだとSTLがないので)などを載せました。
二年生向け説明会
最終発表の前に、二年生向けのACM-ICPC勧誘会があったので、そこで講演するとともにマニュアルの評価をしてもらいました。「国内予選で問題たくさん解くと酒おごってもらえるよ」とか、「アジア予選ではSake Challengeあるよ」とかネタを挟みましたがよくよく考えると未成年もいるはずなので危なかったです。あ、ちなみにスベりました。貴重な意見も多くもらえたのですが、時間がなかったためすべてには手をつけず、誤字脱字を直したり、根本的にマズイところを修正したりに留めました。
最終発表
中間発表で傾向の話はしたので、最終発表では主に対策・ライブラリ周りの話を発表しました。アジア予選体験談も交えて尺を稼ぎました。コートをバッと脱いでICPC-Tシャツ(水色)を見せびらかしたりしました。あ、ちなみにスベりました。対策部分はトピック1つにつき例題を1つあげて、それを解説しつつ、考え方やそのカテゴリに分類するときの見分け方などを説明する形式をとりました。傾向がわかり、その問題を実装する能力が上がっても、判別する能力がないと話にならないと思っていたので、そこは少し意識しました。
国内予選2011
時は流れて2011年6月、国内予選。敗北しました。大敗北です。つまり、このマニュアルでは不十分だったということです。まあそもそもがこのマニュアルは「傾向を分析して優先度を示す」部分がメインといっていい内容で、「ここやればいいよ、ってとこは教えるからあとは頑張って」となるので、これだけで十分なはずはないのですが。僕は危機感を持っていたのですが、チームメイトは「結構問題解いたしいけるやろ〜」みたいな油断があり、見事にやられました(一番戦犯なのはD問題が解けなかった僕ですが)。しかし、2011の問題は素数1問、探索(バックトラック)1問、DP2問の計4問が出題されていて、4問解けば突破の可能性が十分あったので、分析部分は通用するものだった、と虚勢を張っておきます。
感想
実験は、単純に問題をいっぱい解けたので俺得でした。コンセプトをはっきりさせたのも、全体がすっきりしてよかったと思います。マニュアルの内容について細かく見ていくと、
- デバッグ部分はふとしたときに見返してみるのがむしろいいかな、という感じで、初心に返れますし良いです。
- 傾向分析はかなり役に立つ知見が得られたと思いますし、今後も使えると思うのでよかったです。
- 対策部分は判別法のところは重要だと思いますが、問題解説はぶっちゃけeditorialとか競技プログラマのblogを見ながらもっと問題数をこなすようにした方がいいと思うので微妙な感じではあります。
- ライブラリ部分はC++に切り替えてSTLを教えた方が効率がいいだろうと(今は)思っているので、あまり価値はないのかなあと思います。
総評としては、マニュアルを作った、ということよりもマニュアルを作ろうとするために必要最低限の知識を得た、プロコンに慣れたことが僕の中では収穫です。
来年までにまた、今度は「チームメイトとの知識共有、およびグラフ・幾何などのライブラリ」を意識してマニュアルを作りたいなと考えています。次こそは必ず国内予選を突破してみせるので、参加資格のある皆さん、お互い頑張りましょう＆アジア地区予選で会いましょう！
以上です。拙文・長文失礼しました。
明日以降もみなさん僕なんかより面白い記事をたくさん書いて下さるので、お楽しみに！
僕もとても楽しみです〜
