大学プログラミングコンテストの開き方
これは、競技プログラミングのアドベントカレンダー(Competitive Programming Advent Calendar Div2012)の10日目の記事です。
2012年、僕は早稲田大学でプログラミングコンテストを2回開催しました。
- 早稲田大学プログラミングコンテスト2012 (以下、WUPC と表記)
- 第2回 早稲田大学プログラミングコンテスト(以下、WUPC2nd と表記)
今回はこれらの経験から、プログラミングコンテストを大学で開催することに関するノウハウをまとめていきたいと思います。若干、半年前の記事と内容がかぶっていたり、取り留めのない内容だったりしますが、ご容赦ください。
コンテンツ
- 開催の準備をする
- 日時を決める
- 先生(教授)を味方につける
- 宣伝をする
- 問題セットを作る
- 問題を作る
- テスターにテストをお願いする
- テストケースを作る
- 難易度、バランスを調整する
- いい問題を作るには
開催の準備をする
【プログラミングコンテストを大学で開催するにあたり必要な根回し等について。】
日時を決める
まず、他の定期開催コンテスト（TopcoderのSRM, Codeforces等）や大学コンテストとは被らないようにしましょう。特に、年1回開催されるようなコンテストの予選には要注意です。はてなグループのTopcoder部には、開催されるコンテストの日時が数ヶ月レベルでまとまっているので、参考にしてみてください。曜日については、社会人にも参加してもらえるよう、土日の開催がベターです。また、後述する教室の確保に向けて、いくつか開催候補日を持っておくといいと思います。
先生(教授)を味方につけよう
オンサイトイベントを開かない場合（オンラインのみ）や、大学以外の会場を使う場合はこの項目は読み飛ばして構いません。
大学を会場に使う場合、
- プログラミングコンテスト開催のため教室は借りれそうか？
- 当日、ネットワーク環境を確保できるか？
- (オプション)外部生は土日に大学に入れるのか？
- (オプション)外部参加者向けのネットワーク環境を確保できるか？
- 当日には大学の他の行事があったりしないか？
といった問題を解決する必要がありますが、正直、学生の立場ではわからないことが多いと思います。そこで、以上の点を解決できるかどうか、先生に相談してみましょう。情報系の学科の場合、「プログラミング」や「アルゴリズム」を教えている先生だとお話には乗ってくれます(要出典)。 先生に直接会えそうにないなら、先生の研究室のウェブページを探すと連絡手段が載っているはずです。
宣伝する
会場が確保でき、晴れて開催が決まったなら宣伝をしましょう。せっかく開催するのだから、たくさんの人に来て欲しいですよね。
コンテストのページを作る
宣伝のために、コンテストのウェブページを作りましょう。やはりウェブを経由した拡散は速いです。特に、ソーシャルメディアを利用すれば競技プログラミング界隈の人たちにはすぐ伝わるでしょう。
WUPCの場合は、ドメイン更新が面倒なのと、更新がhtml等の知識なしでもできるという点で、Google Siteを利用してウェブページを作りました。
学内に宣伝してもらう
内部生に多く参加してもらうため、学内に向けた宣伝をしましょう。一番手っ取り早いのは、やはり先生の力を借りることです。学科生が登録されているメーリングリストや、学内の掲示板に告知をできないか聞いてみましょう。掲示板に告知をするために、ポスター等を用意できるといいと思います。ウェブページの件とあわせて、デザインが強い人や絵が描ける人が運営チームに居ると心強いです。
他にも、大学生協を宣伝に利用するという手もあると考えられますが、僕はやったことがないので（そもそもできるのかどうか）わかりません。
問題セットを作る
【良質な問題セットを作成する方法。これは大学開催コンテストには限らない話です。】
問題セットの構成を考える
まず、コンテスト参加者の対象を考えましょう。時間が短く、初心者のみが参加するコンテストであれば WUPC のようなセットでも問題ないかもしれないですが、長時間(3時間〜)のコンテストでこのようなセットだと経験者は早々に解き終えて、多くの人が数時間退屈（早解きして座るだけ）、ということになりかねません。
逆に、プログラミングコンテスト入門者を対象に含むようなコンテストで 東京大学プログラミングコンテスト2012 のようなセットを出されても最悪5時間座るだけ、ということになってしまいます。
なので、大学に競技プログラミングを広める等の目的で対象を広くとりたい時は、なるべく難易度の幅を大きくしたい（そして、難易度の上昇幅をゆるくしたい）です。また、初心者がコンテストにフルで参加できるように、後半の問題には愚直な解法で部分点を得られるようにしておく、という手法がよく取られており、実際オススメです。
（もちろん、作問者にとって作った問題の客観的な難易度は分からないので、後述するようにテスターに試しに解いてもらいましょう。）
「絶対にこのようにしなければならない」ということは無いのですが、例えば入門者を対象に含む4時間で9〜10問のセットを出す場合、その前半は次のような構成のセットにするといいと思います。
- いわゆる「やるだけゲー、0点阻止」の問題
- 単純な貪欲に気づければ解けるような問題
- 全探索（考えられる場合を全て尽くす）で解けるような問題
- ソートするだけ（or +貪欲）で解けるような問題
- 単純なDPで解けるような問題
- （拡張）ダイクストラ法を用いて解けるような問題（探索ゲー）
実際、WUPC2ndでは最初の6問はほぼ(DP以外)上記のとおりです。また、僕が問題セットを作る場合、上記のような「解かせるために作った問題」はそれ以降の問題より制約をゆるめにつけています。というのも、その段階で大事なのは「アルゴリズムの実装方法」よりも、問題を単純なアルゴリズムに落とすまでの「考え方」だと思うからです。（もちろん、アルゴリズムを効率よく実装することも大事なのですが、初心者に無闇にそういったテクニックを要求するのは酷だと考えます。考えるのは楽しいけどACもらえないとうれしくないし。）
問題を作る
問題については、僕の場合は主に2通りの方法で問題を作っています。
- 日常のネタから問題を思いつき、解法を考え、解けたら問題にする。
- 既存の問題の制約をいじって、簡単に解ける(or難しい)問題にする。
日常ネタ
日常ネタではまず身の回りのものから着想を得ます。この時、「問題を考えよう」と張り切っていると思いつかないものなので、普段の生活の中、事象に出会うごとに（これって問題にできないかな？）と考えてみるようにしています。そうすれば、問題のネタはいくらでも転がっていることに気づくはずです。
- エレベータがなかなか到着しないのを待ちながら、最適なエレベータの移動方法を考えてみたり。
- 雨が降るのを見ながら、屋根を使ってできるだけ濡れずに移動する方法を考えてみたり。
- セ・リーグの順位表を見ながら、ゲームの試合結果からマジックナンバーをシミュレーションするプログラムを考えてみたり。
- 電車で移動している時、最適な乗車位置を考えてみたり。
- ・・・
もちろん、中には効率的に解けない問題も出てきます。そんな時は、素直に諦めるか、二番目の方法で制約をいじって簡単な問題にします。
WUPC2ndだと、G:だるま落とし と H:ダイヤグラム がこの方法で思いついた問題です。
制約をいじる
制約をいじるのにもいくつか方法があるのですが、僕の場合は
- 制約を全探索で解けるようになるまで小さくしてみる。
- 制約の変数が複数ある場合、一方を他方より極端に小さくしてみる。
- 一般のグラフを木や森にしてみたり、閉路の数を制限してみたりする。
- 平面を立体にしてみたり、形を変えてみたりする。
- ゲームの設定をシンプルにしてみたり、ルールを削ったりしてみる。
といった方法をとっています。特にグラフは閉路などの条件を変えるだけで解ける問題が多いので面白いです。
WUPC2ndだと、この方法で E:独立記念日(グラフ分割問題を改造) と I:その味は甘くて(いつかのJOI本戦「釘(NAILS)」を改造) が生まれました。
テスターにテストをお願いする
問題セットができたら、それをまとめてテスターに渡します。自分より多くの問題を解いている経験者に頼むとよいでしょう。更に、違う言語をメインに使っているならなおよしです。（自分がJava使いならC++erに頼むなど）
テスターには、実際のコンテスト（に似た）形式で、時間を決めて解いてもらいます。この時、どの問題を解くのに何分程度かかったか、をメモしてもらいましょう。
テストケースを作る
テスターに問題をテストしてもらってる間は、テストケースを作ります。WUPC2ndでは、サンプルを含めて10個程度、自力で答えが分かる範囲で小さい入力を作り、30〜40個程度はランダムで自動生成したテストケースを作りました。また、想定される誤解法に対して最悪のケースを考え、これも自動生成で何個か作ります。
最悪ケースを考えるのは難しいですが、想定誤解法で実験(様々な入力を与えてみる)を繰り返して頑張って探しましょう。特に、状態を複数持つようなDPや探索系の問題は、うまく全ての状態を辿らせるようにすると計算量通りの時間がかかっていい感じになります。
入力生成器を作る
大きなテストケースを自力で作るのは骨が折れます。そこで、入力条件を満たすような入力をプログラムで自動で作らせるようにしましょう。ただランダムに生成させると、全ての場合をカバーするのには膨大な量のケースが必要になります。僕の場合、テストケース数を圧縮するために次のような工夫をしました。
- ランダムで作るテストケース数をえいやと(40〜50個)決めてしまう。
- そのうちの40%は、入力条件を満たすものを純粋にランダムで生成する。
- 20%は、入力量が最大になるものだけをランダムで生成する。
- 20%は、コーナーケースになりそうな入力最大ケースをランダムで生成する。
- 20%は、別のパターンのコーナーケースになりそうな...(以下略)
たとえば、G:だるま落とし のテストデータは以下のように生成しました。
- 10ケースを手入力で作成。そのうち1つをサンプルに割り当てる。
- 最大ケースを自動生成。全て "add" クエリの場合と、 全て "challenge" で一番下のブロックを叩き、 "go" になるようなクエリの場合、そして "add" と "challenge" が半分ずつのクエリの場合。
- 入力量が最大で、単純にランダムなクエリが与えられるケースを自動生成。
- 入力量が最大で、ブロックの上の方をランダムに叩くような "challenge" クエリと、ブロックの下の方をランダムに叩くような "challenge" クエリを半分ずつ含むようなケースを自動生成。
入力チェッカーを作る
入力をランダムで作ったのなら、入力チェッカーを作ることをオススメします。入力チェッカーは、その名の通り生成された入力が実際に入力条件を満たすかどうかを自動でチェックするプログラムです。
入力の条件が単純ならいいのですが、例えばグラフの問題で「グラフは森になっている」「多重辺を含まない」という条件があったり、幾何の問題で「3点は一直線上に並ばない」という条件になると調べるのが面倒です。自動でテストケースを作っているとはいえ、やはり入力条件を満たしているかは確認しておきたいものです。
以下にチェッカーのサンプルをいくつか示すので参考にしてみてください。
難易度を調整する
ここまで来たらあともう一歩。難易度調整をしましょう。実際のコンテスト環境でテストしながら、時間制限やメモリ制限をいじっていきます。
このとき重要なのは、最も早く動作する言語であるC/C++を基準に実験を行うということです。Javaで実行するとTLEする嘘解法が、C/C++だと通ってしまうということを防ぐためです。もしそのような解法が出てきた場合は、嘘解法を落とすような入力ケースを用意するか、入力を増やして通さないようにする必要があります。
いい問題を作るには
【最後に、「いい問題とは何か」ということについて考えてみます。】
良問とは
僭越ながら、ここでは僕の考える「良問」について述べます。僕の考える良問とは、「アイデアを考えるのが楽しい」or「実装方法を考えるのが楽しい」問題です。
アイデアとは
ここでいう問題に対するアイデアとは、問題について深く観察することで、初めて見えてくるような（問題固有の）性質のことです。こういった性質は問題を実験によって観察したりすることによって、はじめて見えてきます。この「手探り感」が楽しさを生んでいるのではないでしょうか。
例えば、2012年のTopcoderで解法を知って感動した問題を1つ紹介します。SRM531 div1easy/div2mediumのNoRepeatPlaylist(問題詳細・要ログイン)です。この問題の場合、「最後に演奏したM曲が異なる」ことから、それを利用して「あと何曲がまだ演奏されてないか」を状態に持てる(アイデア)ことに気づきます。
ちなみに、アイデアとはプログラミングコンテストでしばしば要求されるテクニック（座標圧縮や、行列累乗法など）のことではありません。テクニックだけを要求する問題は知識ゲー(:その問題の解き方を知っているかどうか)になってしまい、僕は楽しくないと考えます。非常に極端な例(そして、見たこともない)ですが、以下のような問題が知識ゲーの例です。
整数 a, b, c, d が与えられる。以下の2x2行列の n (≦ 10^18) 乗を求めよ。 [a b] [c d]
実装方法を考える
解き方が複数あり、どの方法が見通しが良いか、実装方法を考えさせるような問題も僕は好きです。
例えば、SRM539 div1easy/div2mediumのOver9000Rocks(問題詳細・要ログイン)はシンプルな問題設定ながら、なかなか考えさせられました。各subsetについて区間を考えることによって簡単に解くことができるのですが、僕は当時散々悩んだ挙句、平方分割を用いて無理やり解いてしまいました。Topcoderでは実装の時間はポイントに直結し、差が大きくつくのでこういったタイプの問題はもっと増えて欲しいと思います。
いい問題を作るには
良問をたくさん解くことだと思います。インプットなくしてアウトプットはありえません。精進しましょう。
