お久しぶりです。この記事を書いた作問アルバイトです。
今回は、自分がTechFULで作問をするにあたって何を考えてどのような問題を目指しているかをブログに書きます。
TechFULに必要な問題の性質
まず、TechFULに並んでいる問題がどのような問題かを説明していきます。TechFULに並んでいる問題は、「先に問いたいものがあって、そこに合わせて教材を作っていく」というコンセプトで作られた問題が多いです。
ここで重要になってくることはいくつもありますが、今回はふたつ取り上げてみたいと思います。
一つ目は、「アルゴリズムの丸写しだけでは解けない問題を目指す」ということです。
読者の皆さんは、「算数ドリル」というものを知っていますか？恐らくは小学生の時にやったことがあると思います。同じ算数ドリルでも、序盤の簡単な問題をずっと同じように手を動かして進めていくだけの作業は、解き方を定着させるのには良い方法であるかもしれませんが、基本的にとても退屈な作業です。
しかし、何人かの読者の方は、同じ算数ドリルでもその終盤の問題なり、今までに受けた数学の授業やテストなりで、面白い問題に出会う、あるいはこれは良い問題だなと思うという体験をしていると思います。結論から言うと、私が求めているのはその感覚です。面白さを感じられる教材の問題は、解き方を知っているだけでは解けず、その解き方に辿り着くまでに考察を要求するというような性質があると思います。
TCBの過去問でわかりやすい具体例を2つ挙げる（過去問のネタバレを含むので、見たくない方はネタバレ終わりの記載まで目を瞑ってください）と、
この問題は僕が作ったものではないのですが、説明したいことが一番分かりやすく伝えられるのでお借りします。
結論から言ってしまうと、この問題は「21XX年に行く前の20XX年の都市X」「21XX年の都市X」「21XX年から帰ってきた後の20XX年の都市X」ということを表す頂点を考えてダイクストラをすると解けます。
このように頂点を増やすという考え方は、特にプログラミングコンテストで頻出の考え方なのですが、初めて理解した時にはある種の感動があると思います。この類の問題が、ダイクストラ法そのままで解ける問題との面白さの差であると思っています。
この問題は、（問題文中から察せる通り） Segment Tree というデータ構造の実装の一部を問題にしたものです。もちろん、Segment Tree の実装を参考にして書けば正解することはできますが、それだけでなく「これで問題文中の『最小の個数の区間を使う』という条件もクリアできるんだな」ということが自分の中で腑に落ちたなら（実装しているうちに気づくことができると思います）、 Segment Tree への理解がかなり深まってくるのではないでしょうか、という期待を込めて作った問題でした。
（ネタバレ終わり）
二つ目は、特にTechFUL最大のコンテストであるTCBやチャレンジ問題においては、新しい発想を含む問題も登場させるということです。
アルゴリズムそのままで解けなくても、よくある考え方だけで全ての問題が解けてしまっては「その場で答えを導き出す」スキルは測定できないのです。
よくある考え方を適用するというだけでもTCBの8問目か9問目（難易度6～7）あたりまでは戦っていけるでしょう。しかし、知識が揃った後で本当の勝負をするのに必要なのは、「その場で答えを導き出す」スキルです。このスキルが必要な問題こそ、例えばTCBの10問目やチャレンジ問題の難易度8に相応しいと思っています。
そのため、個人的に他の方の問題を解いて「新しいと思った考え方」を含む問題は「TCBの後ろの方に使ってみては？」と猛プッシュしたりもしています。
ただ、この類の問題は作るのも難しく、「自分にとっては新しい発想だと思っていたが、実際は良く知られた考え方だった」というようなケースもたくさんあります。なので、実際にここの問題を生み出すことができた時には、かなりの達成感を感じます。
余談ですが、「その場で答えを導き出す」スキルは必ずしも高難易度だけで測定されるものではありません。初級や中級の問題でも、普段ある問題より少し簡単な問題が適正であるような方でも考えれば答えに辿り着ける可能性がそれなりにあるような作りになっている問題は、個人的にはそれもまたいい問題だと考えています。
問題文やテストケース等を作るとき
ここまでは問題の大まかは方向性について書いてきましたが、ここからは実際の作業について示していきます。
まずは問題文です。これに関してはとても大きなテーマがあります。それは「わかりやすさと厳密さのチキンレース」です。もちろん問題文を厳密に書くのは当たり前のことなのですが、厳密に書いたが故に分かりやすさが損なわれてしまっていては、非常に読みづらい問題文となってしまいます。そのために、直感的な理解と精密な議論の両方をできるように問題文を仕上げていく必要があります。他の方の問題文を校正する際にも、この点にはとても気を遣っています。
次にテストケースです。個人的にはTechFULの作問で最も上手く作るのが難しいのはここです。
まず、TechFULのテストケースは基本的に10個で登録しています。そのため10個で考えうる誤答を全て不正解と判別できるケースを考える必要があります。このためには、「どのような誤答が考えられるか」を頭の中で精密に分析する必要があります。もちろん、この作業は百発百中ではありませんが、可能な限りこれが実現するように作る必要があります。ひとつの入力に複数のテストケースを含める形式で作成することもあります。
次に、TechFULではテストケースにいくつか正解すると部分点が入ります。ここで注意するべきことは、「妥当な答案に妥当な点数を与える」ということが必要になってきます。例えば $N=10^5$ という制約の問題で $O(N^3),O(N^2),O(N)$ のアルゴリズムが考えられたとします。すると、この時計算量のオーダーが違わない解法にそう大きな得点差がついてはなりません。なので、 $N=300$ 程度を狙って $2$ ケース、 $N=2000$ 程度を狙って $3$ ケース、 $N=10^5$ 付近で $5$ ケースというように作ると、計算量の悪い方から順にざっくり 20%,50%,100% の得点を与えることになります。（実際は得点計算の方法上、満点の解法に対して一部のテストケースにしか通過しない解法はもう少し得られる得点の割合が落ちます）
今回書いた「考えていること」は、ほんの一部にすぎません。この記事が好評なら、またいろいろと書いてみようと思います。
少し長くなってしまいましたが、最後までお読みいただきありがとうございました！
