プログラミングコンテストを開いたときの話

Competitive Programming Advent Calendar Div2012の12月4日分の記事です。

私はこの1年でいくつかのプログラミングコンテストに主催者寄りの立場で関わって来ました。具体的には、

OUPC
HBPC
SuperCon
Autumn Fest
JAG主催のコンテストのいくつか

などです。今回はコンテストを開催する側としての個人的な経験を中心に書こうと思います。ただしSuperConは色々特殊なので除きます。またOUPCについては既に書いているのでそれとは重ならないようなことを書きます。最初はどうやってコンテストを開くか具体的なマニュアルを作るつもりで書く気でいたのですが、挫折しました。最近はコンテスト開催経験者も増えていますし、文字通りプロであるAtCoderという会社もあるので詳しい手順が知りたい方はその辺りを当たってみるとよいと思います。記事全体は長いですが後半は特に読む必要のないメモを貼り付けただけなので気楽に読んでください。

ジャッジシステム

コンテストを開催するにあたってどこのジャッジシステムを使うか選ぶ必要がありました。とはいえ選択肢はAtCoderかAOJの2択という感じでした。どちらで開催したときもシステムの人に丁寧な対応をしてもらったので、どちらでやっても困ることはありませんでした。AtCoderの方は部分点とか傾斜配点が使えたりhtmlがその場で直接いじれるのが便利でしたね。

時間や配点

5時間のフルセットだと長すぎてダレるとか後半の面白い問題はほとんど見てもらえないとかになりがちなので、2~3時間のコンテストにすることも検討したほうがよいです。
Autumn Festでは配点を好き勝手にいじりました。配点に傾斜を付けた方がより難しい(=面白い)問題に取り組んで貰えるという期待があったからです。

解答や入力の作成

最低限必要になるのがジャッジ解、入力生成器、入力検証器と(必要なら)出力検証器です。前二つは文字通りのもので、入力検証器は生成器よって作られた入力が仕様を満たしているかチェックするプログラムで、出力検証器は出力結果が正答かどうかをdiffで判定できないときにチェックするためのプログラムです。
ジャッジ解をつくるときは、「最大サイズだとTLEするけど愚直にやっているからほぼ確実に合ってるであろう解答」とかを別に用意しておくと便利です。
入力生成器は言うまでもなく重要なものです。嘘解法を確実に落とすのは難しいことですが、しかしやっぱりなるべくならちゃんと撃墜しておきたいものです。数え上げとかは適当に作っても嘘解法は大抵落とせるのですが、最適化系の問題だと撃墜はかなり難しい場合があります。また、テストケースの数はあまり多くなりすぎないように注意します。
入力検証器は、基本的にはtestlib.hとかの信頼できる道具を使うと楽に書けることが多いのですが、時には元の問題よりはるかに難しいものになってしまうこともあります。「ただし入力には矛盾がないことが保証されている」とか「与えられる座標が10^-6変化しても答は変わらない」とかの但し書きがあると大抵元の問題よりも難しい問題を解くことになってしまいます。
出力検証器も、小数の誤差判定くらいならtestlib.hとかに揃っているので楽ですがちゃんと誤解答を用意しておかないと何を投げてもACになってしまうとかの事故が起こるので危険です。
余力があるときは別の言語や解法で解答プログラムを書いたり、想定される嘘解答を作っておいてちゃんと撃墜できるかどうか試したりします。

問題の準備

コンテストの目的に合わせて作る問題の傾向は意識的に変えていました。
OUPCはICPC合宿に提供されるものなので実装量を増やす方向の工夫をちょこちょこ加えました。ICPCの訓練と言うのであれば問題設定もちゃんとダルい感じにしようかとも考えたのですが、ごめんなさい。そこは譲れませんでした。一貫性がないですね。ほぼ全ての作業をふたりだけでやっていたので問題文長くするとチェックが大変になって不具合が起きやすくなるという事情もあったんです…(もちろん後付けの理由です)。
Autumn Festのときは娯楽感を出したかったので修行っぽさを極力排して問題設定も解法もシンプルで実装量の少ない問題を多く選んだつもりです(解答が1行で書けたり、BNFが単純だったり)。
コンテストの最初の方に配置されるeasyな問題は大抵後回しにしていました。不足しているジャンルの調整とかが容易にできるからです。
コンテストの開催日が近づくにつれて自分で作った問題の難易度評価はよく分らなくなっていきます。
あと、アルゴリズムドリブンで問題作るのってそのアルゴリズムに対して理解を深める効果があると思います。物事を人に説明することによって理解が深まるという現象はよく知られていますが、それと似たようなものでしょう。

個人的な嗜好の話

私は自分が解いて面白いと感じられる問題を(なるべく)出題したいと思っています。問題を作ってみると自分の好みがよく分かるようになりました。
シンプルな設定やアイデアの問題が好きです。SRMの問題とか綺麗にまとまっていることが多いなーと思います。聞いたこともないような定理とかを使うタイプの知識ゲーも結構好きです。
一方、いたるところで見かけるような典型な問題はあまり考えていてわくわくしません。複雑な設定の問題もあまり好きではありません(解法があまりに鮮やかな場合は別ですが)。
くどいようですが、以上のことはあくまで私個人の嗜好の話でしかありません。新規参加者は増え続けているのだからそちら向けに典型問題を出題するのは真っ当ですし、複雑な設定や長い問題文を正確に読み取って本質を抽出することだって技術が要求されるひとつのジャンルであるし、実装力を問う問題が出題されるのは当然だと思っています。好き嫌いと良し悪しは別問題です。

コンテストを開く目的

コンテストを一度開くことに決めたら折角なので参加者には楽しんでもらいたいしそうなるような努力をしますが、私の場合それ自体がコンテストを開く動機になっているわけではありません。問題を作る作業が面白く、折角作ってみたのだから人に解いてもらいたいというのが主な目的です。
ただしAutumn Festを開いたのには別の目的がありました。uwiさん、tomerunさんという非学生コーダーの方にコンテストの開催を経験してもらいたかったのです。大学毎に主催するコンテストだけではなく、個人や有志による単発コンテストがもっと増えて欲しいという願望がありました。

コンテストを開くデメリット

コンテストを開催するにはもちろん時間と労力がかかります。
また作業する人間が増えるとマネジメントする人の労力も増えてしまいます(私は主に負担を増やしてしまう側です。ごめんなさい)。
問題考えたり入力データ用意したりするのはたしかに実力向上に繋がると思いますが、準備にかけた時間を問題を解くのに充てた方がより実力付いたのでは?と言われると私は反論することができません。

まとめ

コンテストが増えるのは基本的に誰にとっても嬉しいことだと思うので、みなさまぜひコンテストを開きましょう。
最近は全体的にコンテストのレベルが上がっていますが、もっと易しめのコンテストが増えても良いと思います(上位常連な人たちには退屈かもしれませんが、別にそこをターゲットにする必要はないので)。

以下はおまけです。

問題を作るときのネタのメモ

既存の問題の拡張、改変

ネタは山ほどあるけど、良い計算量の解法を探すのは大変。
列の問題をを木に拡張したりするのはお宝いっぱい。
連続と離散を切り替えるとか。

逆問題、復元系、ロシアゲー

ネタはいっぱい。でもやっぱりいい感じの解法を作るのは大変。

幾何

ICPCの訓練っぽいセットにしたいなら必要になる。
双対変換使うのはそんなに多くない。
解き方によって実装量が激しく変わったりするのは非常に良い。

シミュレーションとかの実装ゲー

工夫すれば簡単になる、みたいなのがあって欲しい。

有名な教科書の練習問題

ほぼそのまま出されている例も世の中にはたくさんある。結構参考になる。

貪欲

流行のマトロイドとか?
その方面の知識はないし、なんだかんだで狙って作るのは難しそう。

分割統治

マージする部分が最難であることが多いので、そこから考えるのが楽?
好きなジャンルなので頑張ってひねり出したい。

データ構造、クエリ処理

列に対して、区間へ一様に何かしたり質問を飛ばしたりするsegment treeな問題はお腹いっぱいな感がある。
正直この手の問題はよほど工夫しないと目新しい部分が出せない。今や遅延更新すら常識となりつつあるので(言い過ぎ)。
巡回シフトや反転とかが加わると平衡二分木になってよい?
リアクティブでクエリ先読みを防ぐことができるようになったので出す側の自由度は広まった。
meldable priority queue使う問題出したい…。→つい先日UTPCで出た。
連結リストとかも滅多に見ない。
queue(幅優先探索以外)
stack(all nearest smaller values以外)
永続データ構造。

グラフ

差分制約とかmaximum closureとかのLP/IPの双対とる問題。
メンガーの定理、ホールの結婚定理、ディルワースの定理とかその周辺。
行列式を使うタイプの数え上げ。
ただのDijkstraはちょっと抵抗あるけど最短経路木作ってどうこうは許せる気がする。
実は二部グラフ！な問題出したい。
安定結婚問題。

探索

結構何でもあり。
BBとか反復深化とか両側探索とか。
- 推定値をちゃんと考えないと通らないようにするとか。
ゲーム木探索ならαβとか。

数学

畳み込みとかいもす法みたいに同型写像使って別の世界で処理してくるのとか。
単位元+結合法則でバイナリ法。線型でない写像とかは狙い目。
素数関連は苦手…。
鳩ノ巣原理はこれまで2問出題したけどなぜか両方ネタ問題っぽくなってしまった。
順列以外の最小完全ハッシュとか。

数え上げ

ネタの宝庫。ただし数学ゲーか動的計画法になりやすい。
組み合わせ最適化な問題と組み合わせて最適解の個数を数え上げさせるとか。DPやるだけ、みたいになることもしばしばだけど。
一時期特殊なDAG上でのトポロジカル順序の数え上げ問題をよく考えていた。
剰余をとらない数え上げも出してみたい(出力は対数使うとかして)。できればモンテカルロ以外の解法があると嬉しい。

動的計画法

適当に問題作ったらよくでてくる。
状態の取り方が面白ければ何でもOK。
変な半順序が入ると希少性アップ。
ただのビットDPだと希少性ないけど、計算量や状態数が3^nなのはそこそこ希少。
- そこから高速ゼータ変換まで発展すれば素晴らしい。
自然に状態考えて、自然に漸化式がでてきたのを自然に実装したら解けたみたいなのはちょっと抵抗がある。
累積和や(RMQ|スライド最小値)で計算量落とすのももはや作業感が強い。
Monge性とかあると嬉しい。
期待値の線形性は使い古されたネタで典型だとは思うけれどなぜか許せてしまう。完全にえこひいきです。

構文解析

構文解析パート自体が面白い問題を自分が経験したことないので、例えばLL以外のとかCYKとか一度やっておこう。
大抵構文解析パートっておまけにしかならなくて、その割に作業感強いので悩ましい。

確率的アルゴリズム

ハッシュ(ハッシュテーブルやハッシュ値の一致で等価判定を代用したりとか)使うのはよく出ている。
確率は直感が効きにくい分野なので、出すならある程度ちゃんと数値的に見積もってから出したい。
誕生日のパラドックス使って解を1個出力とかなら作れそう? →UTPCに出た。鮮やかな使い方だった。
モンテカルロ法は許容誤差の甘さをどうやって誤魔化す?

output sensitive

有名なのは平面走査で線分の交点を列挙するのとか。
コンテストであまり見かけないの何でだろう?
制約の与え方が綺麗ではない、というのは多少感じられるけど気になるほどのことではない気が。

埋め込み、圧縮

ソースコード長やコンパイル時間、バイナリのサイズも制約(=利用してよいもの)のひとつ！
埋め込みデータを圧縮しないと制限に引っかかるようなのとか。
- ただし埋め込むものは圧縮可能なデータじゃなきゃダメ。何かのmodとった値とかだとバラバラすぎてあまり圧縮できない。
コンパイル時計算は是非やってみたいけど、実際にやってみたら遅くて役に立たず辛かった。