#0. はじめに
この記事では、競技プログラミングにおいて、Tester、すなわち 「他の誰かが作った問題を検証する」 という役割を担ってみたいけどどうすればいいかわからない… という方から、 「よりよいTesterになる方法が知りたい!」 という方まで、幅広い層に向けて 「どのようにすれば、よいテストができるのか」 を説明します。
競技プログラミングにおいて、Writerになるための技術、すなわち「問題をどのように作成すればよいか?」に関しては、yukicoder や有志コンテスト等で、かなり培われています。
しかしながら、__Testerになるための技術、すなわち「問題をテストする方の技術」については、恐らくどのようにテストすればいいのかわからない…という方も少なくない__でしょう。
そこで、今回の記事では、__Testerに求められる作業の一連の流れと、自分がTesterをするときに気を付けていること__を、順を追いながら説明していきたいと思います。(ただし、Testerに求められている作業によっては、一部追加の作業が必要であったり、逆に一部の項目について必要がないこともあります。その点は留意願います。)
#1. Testerの役割とは?
一言で説明すると、Testerの仕事は、以下のようなものです。
競プロの作問には、以下の 2 つの役割の人が携わります。
| 役割 | 何をするか |
|---|---|
| Writer | 問題の原案担当者。問題文・テストデータなどの作成を行う。 |
| Tester | Writer の問題を解き、AC する。そして問題文やデータが本当に正しいか確認を行う。 |
| (競技プログラミングにおける作問テクニックを総整理！ 〜初心者から経験者まで〜 より) |
具体的なTesterの作業手順は、おおよそこのような流れです。
###目次
以下は、この図に対応する、この記事の目次です。
| 見出し | 内容 |
|---|---|
| 2-1. 問題を実際に解いてみる | まずはテストする問題を解きましょう! このときいくつか把握するべきことがあります。 |
| 2-2. Writerの想定解の確認 | Writerがどのような解法を想定しているか確認しましょう。 |
| 2-3. 問題文のチェック / 校正 | 問題文を、より正確かつ分かりやすいものに校正しましょう。 |
| 2-4. テストケース / ジャッジの確認 | テストケースやジャッジが、「正しくて、強い」かどうか確認しましょう。 |
| 3. Writerへのフィードバックの送り方 | Writerとのコミュニケーションは、テストの質のカギを握ります! |
| 4. コンテスト全体をテストする場合 | コンテスト全体に関する調整を行いましょう。 |
| 5. 実は、Tester作業はWriter作業と表裏一体 | Writer側にも立ってみることで、よりよいテストができます。 |
##2-1. 問題を実際に解いてみる
まずは自分で、テストする問題を解いてみましょう。おおよそ、以下の項目を把握するとよいです。
- __自力で解けたか__どうか
- __発想__の難易度はどのくらいか
- __実装__の難易度はどのくらいか
- 自分は__どんな解法で解いたか__
- 自分が__つまづいた、難しく感じたポイント__はどこか
- その__自分の解法に怪しい点が残ったか__どうか
- 問題文に__読みづらい点__はなかったかどうか
- サンプルの説明などに、__理解しづらい点__はなかったかどうか
既出チェックも重要!
既出チェック に関連する項目です。既に存在している問題を再び生産するのは、教育目的等を除けば、基本的には望ましいことではありません。
- 問題やその解法に__見覚えはないか__
- 過去に__同じような問題が出題されていないか__
この場合、その問題が既出である__可能性があります。最悪コピペでACされてしまいかねません。「この問題どっかで見たぞ…」「なんかすごい見覚えがある」という場合には、解法や問題文の一部を、競プロのサイト名を含めたりしながら日本語や英語で__検索する1と、既出が発覚するかもしれません。「似た問題が存在するが、本質が別のところにある。自分は出しても問題ないと思う」といったような場合には、それはそれで__Writerに相談__しましょう。
####よりよい改題を検討してみよう!
以下のような、 より質の高い問題への改題 を検討できるケースもあります。
- 実は、少し変えれば面白い問題にならないか
- 実は、__さらに大きな制約__でも解けないか
- 実は、制約の一部が取り除けて、そのことによってよい問題にならないか
例えば、「$N \le 5000$」のような問題サイズの制約について「$N \le 2 \times 10^5$」に引き上げても解けたり、「$p$が素数である」という入力値の性質の制約についてこのような制限が不要であったりすることに気づけたり、__少し問題を改題すると一気に面白い問題になる場合があったりします。__この場合は、Writerに是非連絡してみましょう。より質の高い問題になることもあります。
##2-2. Writerの想定解の確認
次に、Writerが、どのような解法を想定しているか確認しておきましょう。Writerが書いたコード、簡単な説明、解説といったものに目を通しましょう。把握すべき項目は以下です。
- Writerの__解法__は正しいか
- 問題が破綻している場合もあります。 丁寧に確認しましょう。
- Writerの__解法の証明__は正しいか
- これは、解説が書かれている場合にチェックしやすいです。
- Writerの__計算量評価__は正しいか
- Writerの__コード__は正しいか
- これは、TesterのコードがACすることである程度確認可能です。
- Writerのコードは、__実行時間制限/メモリ制限__ともに余裕をもってACするか
- 基本的には、実行時間制限/メモリ制限がそれぞれ半分の値だったとして通過するのであれば、十分です。
- 特定の言語について2、実行時間制限/メモリ制限を満たした解を書くのが難しくなる場合もあります。この判定を考えたくなければ、基本的には余裕を持ったリミット設定をおすすめします。
- 本質的に計算量が大きく変わらない、わずかな__定数倍の差によって、判定が覆らないか__
- __計算量の差が際どい解法が存在するか__どうか、存在するならそれは 通すべきか/落とすべきか
- Writerの__解説__は正しいか
- Writerと自分で、__解法に著しいズレ__がないか
- 双方が別解として成り立つなら、それはそれで構いません。
- Writerと自分で、__難易度評価に著しいズレ__がないか
- 別解が生じたときは、お互いがお互いの解法を理解して難易度を再評価しましょう。
##2-3. 問題文のチェック / 校正
問題文をチェックします。競技プログラミングにおける問題文は、__問題の意図を取り違えないように厳密に書かれていることが最優先__で、そのうえで__可能な限り分かりやすく書かれている__ことがポイントです。
実際の作業をなぞるようにして、どのように問題文をチェックするかを見ていきましょう。
まず、破局的に駄目な__問題文の例を見ていきましょう。(修正例は例の最後に示します)
たくさんの問題を抱えるこの問題文について、問題点がどこか考えてみてください。問題発見のコツは「難癖つけてこの問題を破壊するぞ」というくらい、問題文に敵意を持った目で問題文を読む__ことです。
####校正前の問題文例
$N$ 個の自然数の配列 $A$ があります。
$A$ をソートしたとき、 $k$ 番目の値を出力してください。
制約
- $1 \le k \le N \le 100$
- $S_i \le 100$
####校正の過程
#####1文目
$N$ 個の自然数の配列 $A$ があります。
まず、「自然数」という表現。基本的には、これは $1$ 以上のことを指しますが、 $0$ を自然数に含める流儀もあります。__複数通りの受け取り方があるので、避けた方が好ましい表現__です。 $0$ を含めないなら「正整数」「正の整数」、含めるなら「非負整数」といった表現にしましょう。単に「整数 $x$ 」とだけ記して、制約で $1 \le x$ のように規定してもよいです。
次に「配列」。文脈にも依存しますが、これまた非常に__微妙(厳密でない)な表現__です。基本的には「数列」が無難です。なお、数列を問題文中で定義するときに添え字がついていると便利な場合は、 $A=(A_1,A_2,...,A_N)$ というように定義すると楽です。
最後に、「 $N$ 個の自然数の配列」の【の】。これでは「自然数の配列」が $N$ 個あるのか、「配列」が $N$ 個の自然数からなるのか、分かりません。このように、__複数通りの解釈が可能な問題文は避けましょう。__前者であれば「各要素が正整数である、 $N$ 個の数列～」、後者であれば「$N$ 個の正整数からなる数列～」と修正します。
#####2文目
$A$ をソートしたとき、 $k$ 番目の値を出力してください。
まず「ソート」。ソートと一口に言っても「数値比較」「辞書順比較」/「昇順」「降順」等、様々な種類があります。(この場合では、「ソート」が数値の小さい方から大きい方に並べる行為、であるという)__暗黙の了解に近い考えの問題文を修正する__のも役目です。
「$k$ 番目の値」にも問題は潜んでいます。そもそも「$k$ 番目に大きい」なのか「$k$ 番目に小さい」なのかわからない、というのもありますが、 $k$ 番目というのが、「同じ要素の重複を許して $k$ 番目」「重複を許さず $k$ 番目」の複数通り考えられてしまいます。
#####制約部分
$S_i \le 100$
まず、__問題文中で変数が食い違っています。__本来 $A$ という名前で定義した数列を $S$ として表記してしまっています。長い問題文となるとこれがよく生じるので、気を付けてチェックしましょう。
次に、この $i$ という変数が何か分かりません。最近はこれで「全ての正しい添え字 $i$ について条件を満たす」の意で認める場合も多いようですが、せめて数列 $A$ とだけ示して、制約で $A_i$ という謎の添え字 $i$ を登場させる、つまり、未定義な変数や用語を突然持ち出すのはやめましょう(入出力の説明で添え字が定義される…というケースではギリギリ問題ないですが)。できれば、 $(1 \le i \le N)$ というようにつけてやると吉です。
これも文脈によりますが、__制約が下限だけ/上限だけ もあまり望ましくありません。__ただし、制約全体を見渡せば下限と上限の両方が理解できる、という場合は問題ないです。
問題ない書き方の例として、例えば $A$ が長さ $N$ の非負整数の数列だとして、
$A_i \le 50$
$0 \le A_1+A_2+...+A_N \le 5000$
といったようなものは大丈夫です。
####校正後の問題文
$N$ 個の整数からなる数列 $A=(A_1,A_2,...,A_N)$ があります。
この $A$ の各要素を、値の小さい方から順に(値の昇順に)並べた数列を $B=(B_1,B_2,...,B_N)$ とします。
$B_k$ を出力してください。
制約
- $1 \le k \le N \le 100$
- $1 \le A_i \le 100$ $(1 \le i \le N)$
このように、__問題文の曖昧な表現を取り除き、より理解しやすい問題文へと修正する__のもTesterの役目のひとつです。
####その他の注意
その他にも、例に込めきれなかった気を付けるべき点がいくつかあります。
- 「重さ $W$」「価値 $V$」といった、(それだけでは必ず整数とは言い切れない)パラメータを整数で与える__際は、制約欄に「入力に含まれる値は全て整数」「入力はすべて整数」__といった表現が入っている必要があります。
- __実数を入力で与える問題__の場合は、「小数点以下第 $4$ 位まで与えられる」「全ての入力について、小数点以下の部分は高々 $3$ 桁である」というように、__フォーマットが定義されているか__確認しましょう。
- __一見正しく見える文章でも、よく読むとおかしい__といったケースも存在します。少しでも違和感を感じたら、その正体を探って検証しましょう。
- __折角問題文は正しいのに、サンプルの説明に誤りがある__というのはザラにあります。国語の文章を読むかのように丁寧に内容を手で実験・検証していきながら追ってみるのもよいでしょう。
##2-4. テストケース / ジャッジの確認
Writerが作ったテスト(ケース)に、不備がないか確認しましょう。
基本方針として、テストケースが__「正しくて、強いか?」__というところを確認するのが肝要です。
おおよそ、以下のチェックリストに従えばいい感じに確認できます。
###2-4-1. 「そのケースはテストケースとして正しいか?」
- Writerの作ったテストケースは、__すべての制約を満たす__か
- __Writer・Tester双方のコードでACが得られる__かどうか
- Writerが作ったテストケースの「スペース」「(末尾を含めて)改行」等の__フォーマットは正しいか__
- Writerが作ったテストケースに__文字化けや過剰な入力等が混入していないか__
- Writerが作ったテストケースについて、正常に入出力できるサイズであるか
入力のフォーマットや、入力が制約を満たすかどうかなどの確認といったものは、 testlib.h を使うことによってより正確にテストできます。
###2-4-2. 「そのケースはテストケースとして強いか?」
- テストケースの__数は十分か__
- 各パラメータが、__制約の中の最大値や最小値をとる__ようなケースが含まれるか
- 入力サイズや、時間/空間計算量といった、__暗示的なパラメータが最大/最小になる__ようなケースが含まれるか
- __コーナーケース__が存在するなら、それらは十分含まれるか
- 同じテストケースがたくさん__ダブってしまってはいないか__
- 出力が特定の値ばかりになってしまっていないか
- __愚直な解法__でも通ってしまわないか
- __通したくない解法__が通ってしまわないか
- 考えうる__嘘解法に対する撃墜ケース__が含まれるか
- __特定の処理__をすると破綻するようなケースが考えられる場合、それが含まれるか
- __特定の条件を満たす数列__を入れると、さらにケースが強くなる場合がある
- (グラフが入力の問題について)__特定の形状のグラフ__を加えると、さらにケースが強くなる場合がある
- ($mod$をとる問題について) $mod-1,0,1$ のような、実際の解と $mod$ をとった後で解がかけ離れていたりミスが発生したりしやすいようなケースを加えると、さらにケースが強くなる場合がある
###2-4-3. ジャッジにもチェックが必要な(特殊ジャッジ)場合
以下は、一部の問題ジャンル(構築、インタラクティブ等…)について、(特にジャッジについて)追加で確認するべき事項です。
__構築問題__の場合
- ジャッジの__判定は正しいか__
- 出力形式に違反したり、過剰な出力が行われていたりする場合にも、ジャッジが正常に動作するかどうか注意しましょう。
- ジャッジは__十分高速に動作するか__どうか(ジャッジがTLEしないかどうか)
- __複数通りの解__に対して__どちらにも正解の判定が下るか__どうか
__インタラクティブ問題__の場合
- コンテスト参加者側のプログラムとジャッジとが__正しいやりとり__を行えているかどうか
- ジャッジの__返答は十分高速に行えているか__どうか(ジャッジが原因でTLEしないかどうか)
- クエリ数が上限に達した場合など、__不正解を検知した場合にそれを正しく報告するか__どうか
マラソン3の場合
- テストケースの集合に、何らかの__特定の偏りがないか__どうか
- __ケースの生成方法に違反していないか__どうか(生成法を公言する場合)
- Writer、Testerともに、できれば__様々なアプローチ__を試して得点を調べる
- __得点計算の関数が適当か__どうか
- ジャッジに加え、__得点計算が正しく行えているか__どうか
- 特に、出力形式等が不正な場合には注意が必要です。
複数プログラム間でやりとり行う問題(Communication task)4の場合
- ジャッジの__仲介は正しいか__
- やりとりの中で、__不正解にあたるやりとりを、正しく報告するか__どうか
- 何らかの形式で__不正なやりとりが行えないか__どうか
#3. Writerへのフィードバックの送り方
ここでは、人によっては最大の難関にもなりそうな、WriterとTesterとのやりとりをどのようにすればいいのかを説明していきます。
##3-1. いい問題は、褒める
__いい問題だと思った場合は、素直に褒めましょう。ふざけてるように見えてもこれはめちゃくちゃ大事で、両者の良好な関係を築けるとともに、「いい問題だと思う基準」がずれてないかどうかの確認__にもなったりします。逆に、愚問だと思っても頭ごなしに否定はせず、できるだけ問題をいい方向にもっていけるように問題を再調整できないか試してみましょう。ただし、問題のセットを何人かで組んでいる場合で、選問の権利が自分に(ある程度)ある場合、思い切って「この問題はイマイチかもしれない」と突き返す勇気も必要です。
##3-2. 何か指摘する場合、論点を明確にする
フィードバックを送るときには、できるだけ「こういう点に気づいたが、どうしたい/どうするべきか」というように、__論点を明確に__しましょう。基本的には、__判断の主権はWriterにある__ので、判断の主権者が判断を正しく下せるようにするための努力を惜しんではなりません。例えば、
「この問題のここが読みづらい」
「この問題のこの部分が読みにくい/分かりにくい」
「解法のここが怪しい気がするが、厳密に示すにはどうすればいいのか」
「このような別解はどうか」
「こういうケースは想定の範疇にちゃんと入っているか」
「こういう解法が際どいが通りそう / 落ちそう。どうしたいか」
というような感じでフィードバックを送りましょう。
##3-3. 問題文を修正した場合、Writerに再読を依頼する
問題文を修正したときに、__問題文の意味がWriterの想定と異なってしまう__場合があります。このようなことを避けるため、問題文を修正した場合は必ずWriterに「問題文の意味は変わっていませんか?」と確認をとるようにしましょう。WriterとTesterで問題文の認識が異なってしまっていた場合、重篤な破綻が生じることすら考えられます。
#4. コンテスト全体をテストする場合
コンテスト全体をテストするようなTesterになった場合、__コンテスト全体を見渡した調整や提案__をすることもまたTesterの仕事です。
##4-1. コンテスト時間は十分か
コンテスト時間を決定するときに、コンテスト時間の最終的な調整の提案を、コンテスト全体を客観的に見据えたTesterが行っておくとよいでしょう。例えば、実装中心の問題が多いコンテストでコンテストが従来より短い、ひらめき一発の問題が中心なのにコンテストがあまりに長い…といった、__問題に対して不釣り合いなコンテスト時間になってしまっていないか__確認しましょう。ただし、基本コンテストが長い分には困りません。逆に短い時には強めに突っ込みを入れましょう。
##4-2. 問題の並び順や難易度は適切か
問題の並び順や難易度についても注意が必要です。特に、「問題は(おおよそ)難易度順に並んでいることを想定されている」ようなコンテストのフォーマットについて、__逆転(後ろの問題の方が多く解かれてしまう現象)が起きるのはあまり望ましくありません。__テストしていて客観的に感じ取った難易度をあてに、__できるだけよい並び順を提案したり、感じ取った難易度の序列を積極的に共有したり__しましょう。
さらに、__隣り合う難易度の問題に大きな差異(通称:崖)が生じないように__気をつけなければなりません。その崖を超えられない参加者にとって、過度な速解き勝負になったりコンテストが早い段階で興ざめなものになってしまったりする原因になります。
これら難易度関連の指摘は、問題を作った側からでは気づきにくく、Testerの鋭い指摘眼が必要になる項目です。
##4-3. 配点は適切か
__問題がいくつかある中で、それを解いた時の価値が違う(すなわち、配点が設定される)__ようなコンテストの場合、そこにも気を配りましょう。
例えば、近しい難易度の問題が複数問あったとき、それらには__できるだけ近いか、同じ配点を設定しましょう。__片方ともう片方との配点があまりにかけ離れていた場合、参加者に不公平感が残るコンテストになってしまいかねません。
完答5と部分点6とに同じか近い配点がつけられている場合、__部分点の方がやや難易度が高いことが多い__です。これは「完答できたこと」をより高く評価するためです。
さらに、__「どのような問題の組み合わせで得点したか」の兼ね合いを考慮する__ことも重要です。例えば 「200-300-600-1000-1500」のような配点を設定した場合、AB2完よりC1完の方が、D1完よりABC3完の方が高く評価されます。このような組み合わせをいくつか考えて、それができるだけ望ましい配点になるように調整を提案するなどしましょう。
##4-4. ひとつのコンテストにたくさんのTesterがつく場合
例えば、 Codeforces では、Ratedなコンテストに対して、10人程度か、それ以上のTesterがつくこともあります。一部の有志コンテストで、Writer同士が相互にテストする…というような場合もこれに近い状況になります。
この場合、 「ほかにTesterがたくさんいるから…」と慢心するのは非常に危険です。 Testerがたくさんいる場合、誰が何を検証したかが分かりにくくなります。最悪、Tester全員がただACすることだけを確認した、非常に脆いテストになります。Testerが何人いようと、実際には自分ひとりしかいないと思って、 少しでも気になるところがあれば丁寧に検証し、しっかりとフィードバックを送る とよいでしょう。
#5. 実は、Tester作業はWriter作業と表裏一体
実は、Testerが行うことは、「Writerが気を付けるべきことが満たされているかどうかの検証」という意味で__Writer作業と表裏一体__です。ここに、いくつか作問テクニックやチェックリストをまとめた記事を紹介しておきます。ここで気を付けるべきことを踏まえれば、Writerとしてだけでなく、Testerとしても技術が向上すると思います。
ちなみに、本文中いくつかの項目について、これらの記事を見て思い出したものも少なくないです。「ほかに何かすることあったっけ…」と思った時には、Writer作業側の視点に立ち返ってみてもいいかもしれません。
#6. まとめ
ここまでかなりいろいろと書いてきましたが、Testerをするにあたって一番重要なことは、__多角的な視点から、問題やコンテストをよりよいものにする__ことです。もちろん、はじめはうまくテストできないかもしれませんが、何度も問題やコンテストをテストする経験を通して、自分なりにTesterとしてよりよいやり方を見つけられると、僕はそう思います。
最後になりましたが、校正、アドバイスに協力して頂いた @e869120 さんに、この場を借りて感謝申し上げます。
では、よいTesterライフを!
-
英語での検索はかなり強力です。例えば、「ダイクストラ 競プロ」と検索してもヒット件数は $14,000$ 件程度ですが、同じ検索を「dijkstra competitive programming」と英語で行うと、ヒット件数は $311,000$ 件まで跳ね上がります。 ↩
-
例えば、Java は C++ の 2 倍程度の実行時間となる場合が多いです。競技プログラミングでは Java 程度の実行速度を持つプログラミング言語では AC 出来た方がよいという暗黙の了解が存在します。 ↩
-
2021年3月に開催された AHC001 や、Topcoder Marathon Match (参考) のような、最適解を出すのが難しい問題に対し、できるだけよい解を作成するコンテストの総称です。 ↩
-
通常のプログラミングコンテストでは滅多に出題されませんが、主に 情報オリンピック の春合宿(代表選抜競技)では頻出です。 例題1(複数のプログラムを書く問題)(ジャッジ) / 例題2(ひとつのプログラムを複数回起動する問題) ↩
-
その問題において、最も難しい制約について正解した、完全な解のこと ↩
-
本来の制約より弱い制約で問題を解けた場合に、一部の得点が得られること ↩