More than 3 years have passed since last update.

競技プログラミングのTesterって何をすればいいの?調べてみました!

Last updated at 2021-03-18Posted at 2021-03-18

0. はじめに

この記事では、競技プログラミングにおいて、Tester、すなわち 「他の誰かが作った問題を検証する」 という役割を担ってみたいけどどうすればいいかわからない… という方から、 「よりよいTesterになる方法が知りたい!」 という方まで、幅広い層に向けて 「どのようにすれば、よいテストができるのか」 を説明します。

競技プログラミングにおいて、Writerになるための技術、すなわち「問題をどのように作成すればよいか?」に関しては、yukicoder や有志コンテスト等で、かなり培われています。
しかしながら、Testerになるための技術、すなわち「問題をテストする方の技術」については、恐らくどのようにテストすればいいのかわからない…という方も少なくないでしょう。
そこで、今回の記事では、Testerに求められる作業の一連の流れと、自分がTesterをするときに気を付けていることを、順を追いながら説明していきたいと思います。(ただし、Testerに求められている作業によっては、一部追加の作業が必要であったり、逆に一部の項目について必要がないこともあります。その点は留意願います。)

1. Testerの役割とは?

一言で説明すると、Testerの仕事は、以下のようなものです。

競プロの作問には、以下の 2 つの役割の人が携わります。

役割何をするか

Writer 問題の原案担当者。問題文・テストデータなどの作成を行う。

Tester Writer の問題を解き、AC する。そして問題文やデータが本当に正しいか確認を行う。

(競技プログラミングにおける作問テクニックを総整理！〜初心者から経験者まで〜より)

役割	何をするか
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されてしまいかねません。「この問題どっかで見たぞ…」「なんかすごい見覚えがある」という場合には、解法や問題文の一部を、競プロのサイト名を含めたりしながら日本語や英語で検索する¹と、既出が発覚するかもしれません。「似た問題が存在するが、本質が別のところにある。自分は出しても問題ないと思う」といったような場合には、それはそれで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するか
- 基本的には、実行時間制限/メモリ制限がそれぞれ半分の値だったとして通過するのであれば、十分です。
- 特定の言語について²、実行時間制限/メモリ制限を満たした解を書くのが難しくなる場合もあります。この判定を考えたくなければ、基本的には余裕を持ったリミット設定をおすすめします。
本質的に計算量が大きく変わらない、わずかな定数倍の差によって、判定が覆らないか
計算量の差が際どい解法が存在するかどうか、存在するならそれは 通すべきか/落とすべきか
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しないかどうか)
クエリ数が上限に達した場合など、不正解を検知した場合にそれを正しく報告するかどうか

マラソン³の場合

テストケースの集合に、何らかの特定の偏りがないかどうか
ケースの生成方法に違反していないかどうか(生成法を公言する場合)
Writer、Testerともに、できれば様々なアプローチを試して得点を調べる
得点計算の関数が適当かどうか
ジャッジに加え、得点計算が正しく行えているかどうか
- 特に、出力形式等が不正な場合には注意が必要です。

複数プログラム間でやりとり行う問題(Communication task)⁴の場合

ジャッジの仲介は正しいか
やりとりの中で、不正解にあたるやりとりを、正しく報告するかどうか
何らかの形式で不正なやりとりが行えないかどうか

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. 配点は適切か

問題がいくつかある中で、それを解いた時の価値が違う(すなわち、配点が設定される)ようなコンテストの場合、そこにも気を配りましょう。
例えば、近しい難易度の問題が複数問あったとき、それらにはできるだけ近いか、同じ配点を設定しましょう。片方ともう片方との配点があまりにかけ離れていた場合、参加者に不公平感が残るコンテストになってしまいかねません。
完答⁵と部分点⁶とに同じか近い配点がつけられている場合、部分点の方がやや難易度が高いことが多いです。これは「完答できたこと」をより高く評価するためです。

さらに、「どのような問題の組み合わせで得点したか」の兼ね合いを考慮することも重要です。例えば「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(ひとつのプログラムを複数回起動する問題) ↩
その問題において、最も難しい制約について正解した、完全な解のこと ↩
本来の制約より弱い制約で問題を解けた場合に、一部の得点が得られること ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up