はじめに
この記事は競プロ Advent Calendar 2021 の15日目の記事として投稿したものです。
こんにちは、milkcoffeeです。
私はよく自作問題で競技プログラミングのコンテストを開いたりしていて、このブログでもよく【コンテスト開催記】を書いています。
問題をいくつか作ってきて、自分なりの作問のアプローチについて列挙したくなったので記事を書いてみました。
今回の記事では、作問作業の行程の中でも「問題の原案を考える」部分に焦点を当てていきます。
問題から考える
初めて作問をするならこのやり方がオススメです。
一番問題を量産しやすい方法だと思います。
問題設定
自分が良くやる方法として、「問題設定」と「求める内容」に分けるというのがあります。
問題設定はおおよそ「何が出てくるか」と「何をするか」で決まります。
【何が出てくるか の例】
- 数列
- グラフ
- 二次元座標
- 二次元グリッド
- 数式
- 文字列
【何をするか の例】
- 要素に数字を加算する
- 要素を選んでいく
- 要素を入れ替える
- (グラフや座標上の点を)移動する
「何をするか」というのは、問題文でいうところの「操作」にあたります。
思いつく操作の例が多いほど、作問がしやすくなります。
(そもそも操作が存在しない問題もあります。)
ABCのC問題くらいをいっぱい解くと引き出しが増えると思います。
実際に問題をテキトーに考えてみましょう。
N個の正整数からなる数列Aがあります。(何が出てくるか)
この数列に対して、「要素を1つ選び、1を加算する」という操作をK回まで行います。(何をするか)
問題文っぽくなりました。
問い
問題設定ができたら、何を求めるかを決めます。
問題文の最後の「問い」ですね。
【何を求めるか の例】
- (和・積などを)計算する
- 最大値・最小値
- 最適解(最短経路、最小操作回数など)
- 場合の数、何通りあるか
- Yes/No 判定
- 期待値
- 条件を満たすもの列挙・構築
さっき考えた問題設定に合わせるとしたら
操作後の数列Aの最大値をXとすると、Xは最大でいくつになりますか。
操作後の数列Aとして考えられるのは何通りですか。
のような文が考えられます。
問題設定と何を求めるかを組み合わせることで、(とりあえず)原案ができます。
ここで、組み合わせ方によって大量の原案を作ることが出来ると思い、以下のような表を作成しました。
名付けて「100マス作問」!!!
100マスではないですが、問題設定×求める内容の掛け算で、作問の土台を大量に作ることが出来ます。
ただ、すべてのマスを埋めることができるわけではありません。
解けない、そもそも問題として成り立たないなどの組み合わせもあるので、そこはうまいことチューニングする必要があります。
解法から考える
使用するアルゴリズム・データ構造や、答えの考え方から問題を組み立てるやり方です。
ただし、このやり方で問題を作ると解法が分かりやすい問題になってしまうことが多いです。ある程度難易度を高くしたい場合は解法をうまく隠す工夫が必要です。
使う解法を考える
まずは、問題の答えの本筋となるものを決めます。
【使う解法の例】
(知識・アルゴリズム系)
(考察系)
- 要素をソートする
- 累積和を取って考える
- 主客転倒
- ポテンシャルを考える
- 答えを決め打つ
- 鳩の巣原理を利用する
解法に合う問題設定を作る
答えに必要な解法が決まったら、それを使うように問題設定を考えます。
しかし、狙った解法で解けるような問題を意図的に作るのはかなり難しいので、それを使うような既存の問題を探して参考にするのがいちばん手っ取り早いです。
AtCoder Tags のカテゴリを見れば、AtCoder の過去問を解法から絞って調べることができます。
参考にする問題が1つだとその問題に似すぎてしまうことがあるので、できれば複数の問題を見るべきです。
解法を隠す
解法から作問をすると、解法が分かりやすい問題になってしまう可能性があります。
例えば、以下のような場合は解法が推測されやすいので気をつけましょう。
【解法がバレやすい問題の例】
- 「お決まり文句」を使っている
例えば「最大値を最小化してください」は二分探索のお決まり文句なので、想定解が二分探索だとバレやすいです。逆に、この文言があれば二分探索に誘導できるので、ミスリードを狙えます。
- 制約が特殊
例えば「1≦N≦16」という制約はbit全探索やbitDP であると気づかれやすいです。
- サンプルが分かりやすい
例えば、想定解が「素数ならばYes、それ以外ならばNo」であるとき、サンプルに素数のものが多いとエスパーされやすいです。
解法を組み合わせる
一つの問題で使用するアルゴリズムなどが複数あることは珍しくありません。
いくつか組み合わせた方が解法をうまく隠すことができます。
【組み合わせやすい例】
- 探索系(二分探索、bit全探索、順列全探索)
特に二分探索は応用が利きやすく、組み合わせやすいです。
- 素数、約数系
素因数分解してから or 約数列挙をしてからもう一つ考察をして解く、という問題は多いです。
- DP
DPを使う問題はABCに山ほど出ているので参考になると思います。
それ以外から考える
問題の本質以外のところから先に考えて、問題に発展させていくやり方です。
ad-hocな問題など、面白い問題が生まれる可能性が高いです。
問題文テーマから考える
以下は問題文に出てくる物と、そこからどう問題に発展させていくかの例です。
- すごろく
サイコロを振ってマスを進める・・・期待値問題など
- チョコレート
チョコレートのマスをグリッドと考える・・・最適に切り分ける問題など
- スライム
くっつけると合体して一つになる・・・操作系の問題など
他の物:調味料、乗り物、ボードゲーム、お金、・・・
その他
問題名から考える、制約から考える、コンテストの構成から考えるなど...
詳しくは以下の「具体的な作問例」のところを見てください。
具体的な作問例
自分が出題したことのある問題について、どのようなアプローチで原案を考えたのかをいくつか紹介します。
(スプレッドシートに今まで公開してきた自作問題のリストをまとめています。)
問題から考えた例
- RGB walking (二次元グリッド & 隣り合うマスに移動 & Yes/No判定)
-
Math MASU (二次元グリッド & 数字書き込み & 構築)
-
XOR Operation (数列 & XOR操作 & 最大化)
-
3 perf Number (数 & オリジナルの設定 & Yes/No判定)
解法から考えた例
-
Making Tree (UnionFind)
-
Prime Stairs (順列全探索 & 素数判定)
-
Polygon Locus (二分探索 & 図形に関する考察)
-
Long Digits Number (倍数判定の応用)
それ以外から考えた例
-
Elevator (出てくる物:エレベーター)
-
RGB Slimes (出てくる物:スライム)
-
MARU Game (問題名、丸亀うどんを食べながら考えました)
-
Rich Primer (制約、変わった制約の問題を作りたかった)
-
Under M (コンテスト構成、ペナルティコンテストのための引っ掛け問題)
さいごに
この記事にあるのが自分の作問のアプローチの全部だと思います。
作問は、問題を解くのとは違った面白さがあります。
特に、コンテストを開催して他の人が自分の問題の感想を言ってくださったり、自分の問題で苦戦してくださるのはかなりの快感です。
問題が思いつかない、作ったことが無いという人も是非1つ作ってみてください!
この記事を見て、作問を始める方が一人でもいてくれたら嬉しいです。
この記事は以上になります。ありがとうございました。