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