作問の失敗判例集 - tozangezan's diary

これはこれの2日目の記事です。

今回は、作問時についついやってしまいがちだが、ちょっとした改善によって問題の質をあげることができるような状況をむやみやたらと並べます。コンテストを開こうとしている人とかは確認してみてください。これらを逆に利用してへんなコンテストを開催する人も期待しています。
なお、それぞれの例では、マズさを★の数で表しています。以下のように対応しています。
★★★：コンテストとして謝罪級。Ratedコンテストだったらunratedにするか議論になるレベル。
★★☆：だいぶまずいことをしているけど、コンテストの存在意義が問われるほどひどいわけではない。
★☆☆：「こう改善するともっとよくなるよ」程度のもの

問題の「中身」や問題文に関する失敗

ここは問題の本質です。ですから大概ここで失敗するとコンテストとして成立しなくなります。一番気をつけましょう。

解法が間違っていた① (★★★)

G: リサイクル - Japan Alumni Group Summer Camp 2014 Day 4 | AtCoder
「解法が間違っていた」に該当する問題の多くは、一見考慮しなくてよさそうなケースを考慮しない想定解を作ったが、実はそのケースは考慮する必要があった、という場合に該当します。
こういうときはwriterはもちろんtesterも気がつかないことが多く、そこまで簡単に防げるようなものではありません。
testerの中に超上級者を入れる、くらいの対処法しかないかもしれません。

解法が間違っていた② (★★★)

Problem - A - Codeforces
http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2015/all_problems.pdf Problem K
まれに、「解法が間違っていた」とされる問題に正しい解法が見つかることもあります。

問題文がおかしい (★★★)

E: Optimal alpha beta pruning - Japan Alumni Group Summer Camp 2013 Day 4 | AtCoder 度重なる修正後の状態です
この問題は本来全く別のアルゴリズムを実装させるような問題文でした。数回問題文が修正されましたが、それでもなおWikipediaのリンク先を読ませるような問題文となっています。
この程度にまでおかしいのは、問題文を最後に確認するだけでも間違いが発覚すると思うのですが、英語だとおろそかになりがちです。

問題文が非数学的すぎる (★★★)

パソコン甲子園本戦６「ダジャレ」 - Algorithmer’s note
「不正な審査を行った可能性のある審査員が複数いる場合は、不正を行ったと想定される事象の数が一番多い審査員を不正な審査を行った可能性が一番高い審査員とします。」不正は1回しか起きていないと問題文に書いてあります。ですが、いったいこれは何が言いたいのでしょう……。
「高校生を対象」「初心者を対象」などと銘打ったコンテストはついつい難しげな数学的表現を避けようとしがちですが、そうするとかえって意味不明になることも多いので、適切に数学用語を使いましょう。

参加者に求める前提知識の問題 (★★☆)

White Bird | Aizu Online Judge
数学や情報科学と関係ない知識が必要な問題は、どのくらい説明するべきか、これは要議論だと思います。また、僕の経験則から言うと、「数学や情報科学と関係ない知識」のうち90%は英語の知識で、残り10%は物理の知識です。
こういう問題では、せめて公式とその説明程度は書くべきだとは思います。(例えば僕はこういう物理計算は蟻本のこの問題の解説を読んでもよく分かりません。)

実際、物理の知識が必要な問題がICPCに出題されたときは、公式の説明がなされています。
http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2014/D.pdf

英語が無駄に難しい (★☆☆)

Sun and Moon | Aizu Online Judge
問題文が英語となるコンテストにあまりに複雑な事象(問題の本質と関係ないもので)を出すのは控えたほうがよいです。USACOの問題文が非英語圏の人には読みにくいのと同じような感じです。

フォーマットとして足りない項目がある (★★★)

F: 設備移転 - 九州大学プログラミングコンテスト2014 | AtCoder
Clarifications - 九州大学プログラミングコンテスト2014 | AtCoder
コンテストに参加するのに慣れている人や、出題するのに慣れている人はさすがにしないと思いますが、たまにこういうこともあります。
(ストーリー)、問題概要、制約、(部分点)、入力形式、出力形式、入力例、出力例で1セットです。コンテストに出題してみたい人も、まずは問題を数多く解いてこのフォーマットを目に焼き付けましょう。

制約が足りない・ない (★★★)

Ropeway | Aizu Online Judge
ここまで潔いものは珍しいですが、制約を一つ忘れてしまうことは誰でもよくあります。また、コンテストに慣れていないと気にせず忘れてしまう制約もあります。例えばグラフで言うと、重複辺の有無、自己ループの有無などです。これらがもし何も触れられていなかったら参加者は存在するかもしれないと思って解くので、もしそういったケースが存在しないなら制約の場に書いたほうが自然です。

制約が間違っている (★★★)

もう忘れたんですがPOJにはたまに制約が間違っている(問題文中のNの最大値より大きいNが与えられることがある)問題がありました。ほとんどの参加者は出題者を信用しています。そういう参加者の期待を裏切らないためにもちゃんと確認しましょう。

既出問題 (★★★)

http://www.ioi-jp.org/camp/2014/2014-sp-tasks/2014-sp-d1.pdf
Dashboard - Round 2 2014 - Google Code Jam
C: 積み木 - AtCoder Regular Contest 031 | AtCoder
既出問題は興ざめですが、知らないと防ぎようがないです。日ごろから沢山問題を解くか、問題が目に入る人を増やしましょう。

データ、制約やTL,ML設定に関する失敗

最も多いミスです。ほとんどの場合は軽傷ですみますが、対応を間違えたりすると取り返しのつかないことにもなります。

問題の条件的にありえない入力ファイルが入っている (★★★)

JOI 2008-2009 予選問題・データ
このコンテストでは、2つのファイルにミスが存在しましたが、どちらもなぜ起きたのか分からないほど明確なミスであり、手抜きといわれても仕方ありません。
TopCoderやCodeforcesのコンテストでは、(challenge phaseやhackが存在することもあり)入力チェッカーを必ず作ることになっているので、仮に間違った入力が混入してもこのチェッカーを走らせることで(いずれにおいても走らせてくれます)おかしいケースを見つけることができます。
ただし、この入力チェッカーを作るときにバグが存在することもあるので、複雑な問題のときは注意深くテストケースやチェッカーを作りましょう。

定数倍がきつすぎる (★★☆)

F: 魔法の糸 - 東京大学プログラミングコンテスト2013 | AtCoder
この問題はそこまで酷いわけでもないですが、それなりに定数倍がきびしめでした。(POJ Monthlyの問題は9割定数倍がきつすぎるので、気になる人は見てみましょう…)
よく言われるものとして正解プログラムの実行時間の2倍程度をTime Limitにしましょうというのがありますが、あくまでもそれは目安なので、想定されるアルゴリズムに応じて柔軟な設定をするべきだと思います。例えば再帰Segment Treeは非再帰Segment Treeに比べて結構重いですし、バケット法の問題はバケットサイズで定数倍なんて軽く変わってしまうので定数倍をゆるめにするべきですし、modを沢山取る問題は想定解のコードでどのくらいmod計算をしたのかも考慮すべきですし、単純解法が速過ぎる場合は少しTime Limitを短くすべきですし、さらに言えばO(N log^3 N)やらO(N^1.5 log N)みたいなものを想定解にしてO(N^2)を落としたいときは、この時間設定の厳しさに相当な覚悟が必要だと思われます。
あと忘れてはいけないのがMemory Limitの定数倍のきつさです。少し実装の方針が違ったりするとか、念のためlong longにするとか、そういった少しの違いだけで欲しいメモリサイズは2倍にも4倍にもなります。メモリ制限は特に何もなければ想定解の4倍はあったほうが望ましいと思われます。

TLE解があっさり通ってしまう (★★☆)

G: スタンプラリー - CODE FESTIVAL 2015 決勝（オープンコンテスト） | AtCoder
大量に定数倍改善が施されたコードが通ってしまうのはもはや仕方が無いのですが、普通に実装したTLEコードがあっさり通ってしまうのはさすがに公平さを欠きます。
これはちょっと速く動きそうな想定TLEコードを書いて、それが通ることのないようにTime Limitを調整することで簡単に回避できます。

テストケースが弱い(WAが通ってしまう) (★★☆)

途中で弱いテストケースをカバーするためにテストケースを追加してしまう (★★★)

C: Fox Observation - Japan Alumni Group Summer Camp 2013 Day 4 | AtCoder
コーナーケースが独立して何種類かある問題でそのうちの一部を入れ忘れた、みたいなことがたまにあります。また、たまたま重要なif文がなくても通ってしまうようなテストデータセットになっていた、みたいなこともあります。後者を回避するのは結構難しいです。ただし、ランダムケースの数の暴力で誤魔化すという手段もあります。
尚、テストケースを修正でなく新たに追加するというのはマナー違反的に扱われている慣習があるように思われます。

嘘解法でWAのはずが、部分点になってしまう (★★☆)

↑の派生です。今年のIOIでもあったようです。

テストケースが弱い(最大ケース埋め込みで通ってしまう) (★★☆)

Submission #228676 - Japan Alumni Group Summer Camp 2014 Day 2 | AtCoder
Submission #228683 - Japan Alumni Group Summer Camp 2014 Day 2 | AtCoder
テストケース数が少ないとたまに起こることですが、最大ケースが1つしかなくそれが自明なとき、それに対する答えを埋め込むだけで通ってしまうことがあります。「最大ケースが1つしかなくそれが自明なとき、それに対する答えを埋め込むだけでACを目論む人」がいることを忘れないようにしましょう。最大ケースに近いケースを複数用意すれば安心です。(また、参加者としてコンテストに参加するときは、「このwriterはテストケース数を減らそうと努力している」みたいなことを知識に入れておくとこういう戦略が使えることもある、と伝えておきます)

テストケースが強すぎる (☆☆☆)

Cave Explorer | Aizu Online Judge
大量に存在する厄介ケースがちゃんとカバーされてると心が折れそうになる……

サンプルが弱すぎる (★☆☆)

Ant Nest | Aizu Online Judge
こんな誰でも思いつくようなサンプルが1個置かれているだけでは、「サンプルは自分で作ってください」と言っているようなものです。特に幾何問題のサンプルを手で作るのはそこまで容易ではありません。意図的にサンプルを弱くしているのではないならば、ある程度親切にしましょう。
あと、初心者向けコンテストにコーナーケースのある問題を出題するときは、コーナーケースをしっかり(できれば説明文つきで)サンプルに入れるべきだと思います。

pretestが弱すぎる (★★☆)

Problem - 461D - Codeforces
ごめんなさいこのテストケース作ったの僕です。言い訳をさせてください。
当時この問題のテストケースを作ったとき、「小さいケースを手で打ったもの」「大きいケースのうち、ランダムにoxを置いたもの(ほとんど答えは0になる)」「ちゃんと組み合わせが存在するように(想定解プログラムで計算しながら)oxを置いたもの」の3パターンでデータを作っており、pretestもしっかりと作って置いておきました。
その後、想定解プログラムが酷すぎる挙動をしていたことが発覚します。もちろんまずは想定解を直しますが、間違っていた想定解によって作られたテストデータは正しく動かすと答えが0ばかりになるので、新たに3つ目のパターンで作成したデータを追加したのです。
が、pretestの場所にそれを追加するのを忘れてました！！！　コンテストが終わってからやけに沢山の人がSystem Testで落としているのを見て、ケースを開いてみるとpretestゾーンの答えが0やら1やら4くらいの数ばかりなのに気がつきました……。(まるっきり違うコードでpretest通した人ごめん)
チェックリスト的なものが欲しかったです(言い訳再開)。
とはいってもCodeforcesのpretestの存在意義はどうなんだよ、という意見もあります。

「問題セット」として見たときの失敗

個々の問題がよくできていてデータに不備がなくても、問題のチョイスがおかしかったりすると、微妙なコンテストになってしまうことがあります。この項目は優先度はそれほど高くないですが、よいコンテストにしたい人や、大事なコンテスト(賞金つきコンテスト決勝とか)を作る時には気にするべきだと思います。

問題ジャンルが偏りすぎている (★☆☆)

SRM 644 (いろいろあったためArenaにしか問題が残っていない…)
Div1が全問数え上げ問題です。ジャンル被りが絶対悪というわけではないですが、さすがに全問同じジャンルの問題は避けたほうがいいかもしれません。
このときも僕はEasy, Mediumのwriterだったのですが、コンテスト前にHardの問題をみてびっくり、ジャンルの重複は気にしないんですか……。

コンテスト時間に対して実装量が多すぎる (★☆☆)

TopCoder Statistics - Problem Statement
75分コンテストの3問目に重い平方分割と木の問題です。しかも定数倍も厳しく、バケットの値を上手く選ばないとTLEするのに、一発ACを要求されています。
やるだけ問題を実装の多さと時間の少なさでDiv1Hard級の超難問にしているのだろう、と思いきや解き終わる人は実際に存在するので、そんなに問題が無いのかもしれません。

同じような問題を連続して出す (★★☆)

TopCoder Statistics - Problem Statement
TopCoder Statistics - Problem Statement
ほとんど同じ方針で解ける問題2問が同じコンテストで立て続けに出て、しかも両方同じwriterだったら、あなたはどうしますか？
前者は「コンテスト時間に対して実装量が多すぎる」にも当てはまり、なんともいえない残念さを誇っています。

多分他にもいろんな作問の失敗はあります。参加者として参加しても感じるものはときどきあるし、writerとして参加したらもっと高頻度で感じます。何度も経験を積む事が、いい出題者になるために大事だと考えています。