マラソンマッチで最初の12時間にすべきこと
Competitive Programming Advent Calendar 2015 14日目の記事です。
マラソンマッチ関連の記事を書くに当たって、マラソンしてる時の感覚を思い出すため一昨日 マラソンマッチの過去問 を12時間やってみました。 その結果改めて気づいたことと、普段マラソンマッチに取り組む際に気をつけていることをまとめたのが以下の文章です。読者に何かしらの気付きが与えられれば幸いです。
また、偶然にも TCO15 Marathon Finalist である takapt氏 の記事も本日発表(Topcoderマラソンマッチの探索問題で重要なこと) なので、合わせてご覧ください（多少のネタ被りがあるかもしれませんが、ご容赦ください。）
続きを読むRubyで実装して楽しむ古典データ構造再入門（平衡木編）
Competitive Programming Advent Calendar 2014 7日目です。
今回は古典的なデータ構造をRubyで実装してみます。 まず通常の木、二分木からはじめ、その次に二分探索木、そして二分探索木に少し機能を加え高性能にした平衡二分探索木を扱います。
冒険の地図
- 木
- 二分木
- 二分探索木
- 平衡二分探索木
- ランダム挿入二分探索木
- Treap
- 平衡二分探索木
- 二分探索木
- 二分木
プログラミングが苦手な人向けの課題
ことのあらまし
研究室内にてプログラミングが苦手な人向けの課題を出してみたところ、思いの外好評だったので、ここでも公開してみます。
対象者
授業や課題以外でプログラミングに触れたことがない人。プログラミング自体にはある程度慣れてきたけど、プログラムの規模が少しでも大きくなると、どのように書いたらいいのか分からなくなってしまう人。
注意
- プログラミング言語は何を使ってもOKです。
- 課題は複数の小課題から成ります。
- ひとつの小課題をクリアしてから、次に進んでください。
- 小課題ができたら、先輩などにコードを見せてフィードバックをもらいましょう。
小課題1
問題1
2つの手を標準入力から受け取って、じゃんけんの結果を標準出力に出力せよ。入力は次の形式で与えられる。
aの手 bの手
aの手とbの手が半角スペース区切りで一行に与えられる。また aの手, bの手 は {R, S, P} のどれかであり、それぞれ R : グー, S : チョキ, P : パー を表す。aが勝つなら 1, bが勝つなら -1, 引き分けなら 0 を出力せよ。
問題2
はじめに、勝負数 m が与えられる。続くm行には、aと同様にプレイヤの手が2個ずつ与えられる。その回数だけじゃんけんが続くようにせよ。入力は次の形式で与えられる。
m 1回目のaの手 1回目のbの手 2回目のaの手 2回目のbの手 ... m回目のaの手 m回目のbの手
各じゃんけんごとに、aが勝つなら 1, bが勝つなら -1, 引き分けなら 0 を出力せよ。
問題3
m 回のじゃんけん後に、各プレイヤの勝利数、敗北数、引き分け数を出力するようにせよ。入力形式は 問題2 と同様である。ただし、一回一回のじゃんけんの結果を出力する必要はない。（最後に各プレイヤの勝利数・敗北数・引き分け数が分かれば良い）
小課題2
問題4
今度は、はじめにプレイヤ数 n (>= 2) を受け取ることにする。勝負の数 m はその次の行に与えられる。続く m 行には、プレイヤの手が n 個ずつ与えられる。じゃんけんを多人数で行えるようにプログラムを改良せよ。ただし、一回一回のじゃんけんの結果を出力する必要はない。（最後に各プレイヤの勝利数・敗北数・引き分け数が分かれば良い）
入力は次の形式で与えられる。
n m 1回目のプレイヤ1の手 1回目のプレイヤ2の手 ... 1回目のプレイヤnの手 2回目のプレイヤ1の手 2回目のプレイヤ2の手 ... 2回目のプレイヤnの手 ... m回目のプレイヤ1の手 m回目のプレイヤ2の手 ... m回目のプレイヤnの手
問題5
次は、たまにじゃんけんに参加しない人も出てくるとする。その人の出した手は - で表す。その時、じゃんけんは残りの人で行うこと。ただし、各じゃんけんには必ず2人以上参加するような入力が与えられる（つまり、1行あたりの - の数は n - 2を超えない）ものとする。入出力の形式は問題4と同じである。
小課題3
問題6
入力をファイルからも行えるようにプログラムを変更せよ。そのファイルパスはコマンドライン引数(1番目)から与えられるものとする。
問題7
出力をファイルからも行えるようにプログラムを変更せよ。そのファイルパスはコマンドライン引数(2番目)から与えられるものとする。
大学プログラミングコンテストの開き方
これは、競技プログラミングのアドベントカレンダー(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では実装の時間はポイントに直結し、差が大きくつくのでこういったタイプの問題はもっと増えて欲しいと思います。
いい問題を作るには
良問をたくさん解くことだと思います。インプットなくしてアウトプットはありえません。精進しましょう。
用語集が作れるアプリ、「たまてま」を作った
Ruby on Railsの練習を兼ねて、ふと思いついたアプリを作ってみました。用語集が作れるアプリです。主に見せ方にこだわりました。
はじめてのテスト駆動開発に戸惑いつつも、行き当たりばったりしながらの一ヶ月の突貫工事でした。
サービスの内容について
まとめWikiなどを見ていると、よく「用語集」というのがあるのですが、特定のワードを見るのにわざわざ別のリンクに飛ばなきゃいけなかったり、あるいは用語集を作る側も言葉を辞書順にソートするのはめんどくさいんじゃないか、というわけで作ろうと思い立ちました。
でもそういった用語集って、「分かる人には分かる」といった、いわゆる「内輪向き」の要素が強く、外に広がっていかないので「ああこのサービス流行らないな」と作ってる途中で思ってしまいました。それに普通に考えてまとめWikiからこちらのサービスにわざわざURL貼ってくれないよね。
個人的サービス開発お役立ち三種の神器
- Railsのチュートリアル
- 英語だがおすすめ。テストの書き方、herokuへのプッシュの仕方等込みで丁寧に書いてある。
- Twitter Bootstrap
- とりあえずこれ使っておけば「らしい」デザインにはできる。便利なJavascriptのライブラリもついてくる。
- Heroku
- 自前でサーバ管理しなくて良いので楽。
テストについて思ったこと
テストを網羅的に書くのって結構しんどいなと思いつつも、本当に全部書く必要あるのかな、とも考えたり。特に表示(View)に関するテスト。「この部分を少し変えたいな」と思ったら、場合によってはテストを書きなおす必要があってめんどい。
一方、モデルやバリデーションのテストはあったほうが便利だったし、必要とも感じた。少なくともこちらは今後も使っていこうと思う。
また、本アプリではjQueryでAjaxをしてる部分があるが、その部分のテスト（これこれこういうレスポンスがあったらエラー表示する、など）はどう書けばいいのか分からなかったです。
プログラミングコンテスト(WUPC2012)開催にあたり、僕が考えたことのだいたい全て
内容はタイトルのとおり。プログラミングコンテストWUPC2012の開催記です。
コンテンツ
- はじまり
- メンバー募集・会場手配
- 企画の詰め
- 作問・難易度調整
- コンテスト準備・当日
- 謝辞
はじまり
2011年6月。ICPC国内予選において、早稲田は1チームも地区予選に進出できなかった(2011年国内予選の順位表)。 僕自身は周り(研究室内)にプロコンに興味がある人が見つけられなかったのと、「一緒に出よう」といっていた人も休学をしてしまったので、チームが作れず、不参加だった。当時僕は修士1年だったが、国内予選の参加資格を勘違いしており、「まぁ来年僕が出て予選突破してやるか」などと気楽に考えていた。（実際は、早生まれの人でない限り修士2年生は参加できないのだ。）
それがICPCに参加できる最後のチャンスだったことは就活中(11月ぐらい)に他の人と話して初めて知った。絶望。この時からコンテストを早稲田で開くことをなんとなく考え始めた。大学プロコンにおいては僕はもう現役の選手ではなく、後輩を育てていく立場にならなければならないのだと。
また、他大学の学生有志主催のプロコン(RUPC2011, KUPC2011など)も開催を後押しした。早稲田でもぜひやろうと。入学して以来、早稲田でのプログラミングコンテストなんて金輪際聞いたことがない（僕のアンテナが低かっただけかもしれないが）ので、「僕がやらなきゃ誰がやるんだ」的な感じではあった。
コンテスト開催の目的は、2012年のICPC国内予選で早稲田から予選突破チームを出すこと、そして、早稲田におけるプロコンのコミュニティを作ることだ。その趣旨から、例年6月に行われる国内予選までには開催したい。
メンバー募集・会場手配
4月。ある程度作問作業が進んだので、開催の目処は全然立っていないのだがTwitterで運営のお手伝いの募集をかけた。すると3〜4人が集まってくれた。ありがたいことだ。あとは、開催にあたり教室と、協力してくださる先生が必要だった。
早稲田の情報理工の先生の中で、「アルゴリズムとデータ構造」の授業を担当されている筧捷彦先生に相談をした。先生は担当授業でICPCの宣伝をよくされていたし、まず協力は得られるだろうと踏んでいた。（あとで知ったことだが、筧先生はコンテストを主催するACMの日本支部長で、高校生向けのプロコン、情報オリンピックの理事長だった）そして、快く協力してくださり、開催は6月2日(土)と決まった。先生は学内向けにコンテストの宣伝をしてくださることになった。
企画詰め
正式に開催が決まったので、メンバーを集めて運営者会議をした。この時はコンテスト運営の具体的な内容(コンテストの時間、問題の難易度、コンテスト終わったらどうするのか、宣伝のことなど)が全く決まってなかったので、意見を募った。
対象はコンテスト初心者〜中級者と決まり、「長すぎるとダレるよね」という話から、2時間5〜6問のコンテストになった。また、コンテスト後に懇談会をやることになった。「誰をターゲットにするのか」というのはコンテストにおいて大事な命題で、これが運営チームのお陰で早めに決まったことは幸運だった。
また、学内に向けた宣伝は大きな課題の一つだった。筧先生は宣伝に協力してくださることになったが、宣伝するにも媒体がないとどうしようもないので、登録ができる公式ウェブサイトを作ろうという話になった。ウェブサイトを作っていくに連れ、決めなきゃいけないことがどんどん浮き彫りになってきた。（賞品はどうしようか、会場には外部生も入れるのか、登録のフローはどうしようか、など。）やがてウェブページは完成したが、絵がなにもないのは寂しいので運営スタッフの知り合いに描いてもらえることになった。ここら辺が個人的に苦しい時だったが、企画が前に進んでいるので充実感はあった。
登録フォームを公開すると、応募がぽつぽつ来て、一週間で10人を超えた。一安心。そして、大学のウェブサイトにお知らせが乗ったあたりから登録数が加速した。宣伝の力ぱない。
作問・難易度調整
難易度調整はコンテスト開催において一番苦労した。難産。問題数や難易度が決まったので、当時考えていた問題プールのうち6個をとって問題セットにした。そして、適当にストーリーをつけて仮公開。
没だった問題で、D問題として幾何の問題を考えていた。内容は本番で出した最後の問題の三角形版（内部に点を含まないような三角形を求めよ）で、Nが小さくて全探索で解けるというもの。これはあまりにも安直すぎるし、ライブラリゲー（三角形に点を含む判定があったらそれを貼り付けるだけ）になってしまう気がしたので没になった。内部生向けにもコンテストの趣旨的によろしくない。またもうひとつ没にした問題があって、内容について詳しくは述べないがこれは自分で作っておいて自分で解けなかった。
結局、F問題(最後の問題)とC問題(自宅からの脱出)を追加して現在の形になった。C問題は「初心者にも解ける迷路問題があった方がいい」という意見から、F問題は複雑な幾何が要求されない四角形の問題を考えた。全体的にTopcoderのdiv2で出てくるような難易度になった。改めて見れば典型問題ばっかりだな、と完成してから感じたが、今思えばこの難易度設定が少なくとも内部生向けにはベストだった。D問題(三角パズル)はテストプレイ時に同じ問題を指摘してもらえたが、DPを説明するのに良い題材だと思ったのでそのまま出した。F問題は最初の思いつきでは N ≦ 5000 で座標圧縮が必要だったが、2時間6問のコンテストとしては実装量が多くなってしまうのでやめた。杞憂だったが。
そして、AtCoder運営チームと連絡を取り、問題とテストケースを送ってコンテストページを公開してくれることになった。AtCoderで実際にACがもらえるかどうかをテストしたところ、B問題やF問題のテストケースにミスが見つかり冷や汗モノだった。コンテスト中、B問題では辞書順ソートしてから先頭2つをくっつけるという誤解法が多かったが、想定解を作るときに僕も同じミスを犯していた。
また、コンテスト後に思ったことだがC問題の制約がきつすぎた。迷路の大きさは N, M ≦ 500 だったが、これはキューを使うなどしてうまい実装をしないとTLEしてしまう。プログラミングコンテストに慣れている人たちにとってはこれは当たり前で、楽勝なのかもしれないが、今回の参加者たちは必ずしもそうではないので、N, M ≦ 50 でもよかったなと。
コンテスト準備・当日
当日は11時から準備を始めた。黒板に案内の文字を書いたり、教室の前に張り紙をしたり、インターネットへの接続テストをしたり、スタッフがほとんどすべてやってくれて、この時点で僕の作業は殆ど無かった。強いて言えば、コンテスト開始前のスライドができてなかったので急いで作った。でもやったことといえばそれだけだ。
また、開催日の少し前に入賞者に賞品だけでなく賞状を配ろうという意見が出た。これはスタッフが準備してくれた。また、コンテストの様子をリアルタイムに更新してはどうか、という提案があった。更新作業は提案した人におまかせすることにした。僕はコンテスト中何をしていたか、というと、順位表を眺めつつ質問に対応していた。内部生用と外部生用の両方を見なきゃいけなかったので割りと忙しかった。
そしてコンテストが終わり、休憩後解説タイム。解説はSlideshareにアップしたものを使った。A〜Fまで淡々と説明。1時間しゃべるのは結構辛い。先生の大変さを理解した。
懇談会は大いに盛り上がった。ひたすらHaskellの話をしていた人、ICPCに出ると言ってくれた人、情報基礎教育のTAがひどいという話。また、早稲田でかつてICPCに出たことのある先輩方も急遽参加。うんにゃ、コンテストやってよかった。
謝辞
- コンテスト運営を手伝って下さったスタッフの皆様
- 会場提供や宣伝にご尽力いただいた筧先生
- @chokudaiさんをはじめとするAtCoder運営チームの皆様
- 事前に問題をテストプレイして下さった@drken1215さんと@tomerunさん
- コンテストに参加して下さった皆様
ありがとうございました。特に、運営スタッフの方々には助けられました。
プログラミングコンテストはいいものです。またやりたいね。
次回
年内に第2回を開催するべく現在作問中です。前回ほど大々的にはやらないかもしれないけど。
