DEGwer 式作問法

2020年1月15日 22:26

はじめに

初投稿なので一応自己紹介をします。DEGwer です。AtCoder Codeforces Topcoder ともにレッドコーダーで、AtCoder では一時期銀冠をしていました。ICPC は銅 (2017) と金 (2018) で、IOI は銀 (2013) で、IMO は金 (2014) です。AtCoder でよく writer をしています。僕の目視が正しければ、AGC 級 (全員 rated) のコンテストの問題を 49 問書きました。

競技プログラミングでお金を稼ぐ方法を知っていますか？　僕は知っています。

界隈構文を見出しにしただけで驚きの胡散臭さ
これは情報商材や　胡散臭くてナンボや

皆さんは競技プログラミングでお金を稼ぐ方法として何を思い浮かべますか？　賞金？　うーん、それは一介のレッドコーダーにはちょっと敷居が高いですね……　そもそも 1 位取らないとまともな額が来ないことが多いし、そんな手段で稼ごうって言ったって……　そんな宝くじみたいな稼ぎ方じゃありませんよ、もっと安定したやつです。そうです！　作問ですよ作問！ (露骨な導入)

というわけで作問の話です。

コンテストを開きたければ、問題の数が必要です。コンテストを一度開くだけなら偶然思いついた問題をかき集めればどうにかなるかもしれませんが、継続的に開きたい場合はそうもいきません。というわけで、この記事では、問題を量産するためのテクニックについて書いていきます。

この記事は、問題原案を思いつくための方法論についての記事です。問題セットの組み方や、テストケース作成などの問題準備については書かないので、他の記事を参照してください。

考えた設定の個数 × 出題方法のレパートリー = 問題数

言葉を雑に掛け算して等号でつなぐとそれっぽくなるってスタバで外資コンサルマンが言ってた

早速始めていきましょう。ぼくが問題を作るときの手順は、以下の 3 ステップになっています。

1. 設定を考える
2. その設定について考察する
3. その考察を要求するような問い方を考える

この問題を見ると分かりやすいと思います。

まず、設定とは、問題文中で定義されている操作のことです。変なコピー操作が定義されていますね。

設定についての考察とは、この問題の場合、操作を繰り返すことで数列はどのように変化するか、ということです。コンテスト中に解くときにもそういう考察をしますね。

そして、その変化の様子について考察することをコンテスタントに要求するために、「最終的な列に現れる各整数の個数」という少々変わった「問い方」をしています。

おそらく、初めての人が作問をしようとすると、「こういうものを数えたい」「こういうクエリに高速に答えたい」というようなところからスタートすると思います。あるいは、アルゴリズムが先にあって、「このアルゴリズムを使う問題を作りたい」と考えるかもしれません。これらの手法が悪いとは言いませんが、少なくとも問題の量産には向いていないように思います。前者 (問題ドリヴン) は 1-3-2 の順、後者 (アルゴリズムドリヴン) は 2-3-1 の順で作問を行っていると見ることもできます。

1-2-3 の順で作問を行うことの一番の効果は、3 のステップが最後にあるおかげで、「考えた設定を問題完成につなげやすい」ということです。これは、その設定が「問題にしうる何か」をどこかに含んでいればよいことに起因します。

「〇〇を満たすものは存在するか (Yes/No)」
「〇〇の中での△△の最大値 (最小値) を求めよ (最適化)」
「〇〇を満たすものの個数を求めよ (数え上げ)」
「〇〇を満たすものをひとつ構成せよ (構築)」……

などのうちのどれかひとつが、N<=20 と N<=50 と N<=3000 と N<=200000 のいずれかで問題として成立すれば作問成功、という風に考えれば、とりあえず設定を考えたら何らかの問題は作れるような気がしてくるのではないでしょうか。

とはいえ、そう毎回うまくいくわけでもないし、そもそもこれでは抽象的すぎるので、ここからはステップごとに分けて方法を説明していきます。