書くぞい
今回は原案作成をメインに書きます。
原案を作ったあと、データセットを作ったりテスターをしたりするときにはRimeを使うのが便利です
beet-aizu.hatenablog.com
はじめに
懇親会とかで話を聞いていると作問をしたことがない人が結構いてびっくりしたので書きます。
作問のメリット
- たのしい
- 作問したテーマに関する知見が得られる
たとえば「セグメント木を使った問題」を作ろうと思ったとき、
- セグメント木ではなにができるのか
- それは他の方法では代用できないのか
- より計算量の小さい方法はないか
- 嘘解法で、ぱっと見それっぽいものはないか
みたいなのを考える必要があり、その経験は実際に問題を解くときにも役立ちます。
- 「解けない問題」がわかる
ある問題がNP困難な問題に一般化できるなら、その問題はより強い性質を持っているはずです。
別の問題に帰着したとき、その問題が解けるかどうかを考えたことがあれば考察がスムーズに進みます。
作問をするときは「想定解以外では解けない」方が望ましく、解ける問題と解けない問題を見極める癖がつきます。
最大独立集合や巡回セールスマン問題や最小ハミルトン経路は「解けない問題」の代表例です。
作問の具体的な方法
天啓
なんか生えるのを待つ よくわからんけど生えるときは生える
典型
勉強した内容を組み合わせたりちょっと変えたりする 多分これが一番正統派
例
- 逆から見る
- 全探索
- 二分探索
- 平方分割
- 最短路（Warshall-Floyd、Dijkstra、Bellman-Ford)
- 行列累乗
- DP
- etc.
組み合わせの個数は指数オーダーなので（質を気にしなければ）ほぼ無限に作れる
誤読
誤読したとき、作問は既に終わっている
atcoder.jp
僕は↑の「1 番目の橋から順に全て崩落する」を見逃していて、各橋について「その橋のみがなくなった場合」の問題を解いてしまったんですが、それはもう別の問題なので実質作問みたいなところがある（ちなみにこの誤読をしていた場合は500~600点問題になりそう（あなたは解けますか？））
木
木はとても性質が強いので作問しやすい 既出になりがちなのとその要素いる？が起こりがちなのに注意
↓は木が二部グラフなのを利用して二部マッチングの流し直しをするのが想定だったんですが、冷静に考えると毎回木DPをすれば間に合ってしまうことに合宿の二日前に気づいてうくにきあくんになった（ので位置がおかしい）
judge.u-aizu.ac.jp
木の性質を列挙しておく
ギャグ
データ構造を適当にくっつけるとできる 人をかなり選ぶので問題数が少ないセットに入れると怒られがち
直近だとRUPC2019day2のMがそうで、文字列系でロリハ以外の問題を作ろうとしていたら生えた。
judge.u-aizu.ac.jp
典型との違いはかなり曖昧なので時代とともに日の目を見るかも？
？？？「二重辺連結成分分解してHL分解してセグ木にpriority_queueを載せる問題作ったろ！w」
yukicoder.me
人に投げる
複数人で作問するときは解けるかよくわからないやつをとりあえず強い人に投げるという手があります
RUPC2019day2のKはもともとはじさんが解けるかわからないと言いながら原案を出して、僕が方針と解法の一つ目を出した。
judge.u-aizu.ac.jp
もともと想定解を用意している場合でも、他の人がオーダーを改善して制約を変えたりみたいなことはよくある
これが複数人で作問する醍醐味みたいなところがあっておもしろい
自分語り
僕が最初に問題を作ったのはACPC2016のGで、当時はまだ過激派ではなかったのでO(1)幾何でした。
judge.u-aizu.ac.jp
そのあとも無理やりオンラインクエリの問題を作ったり、本質が定数倍改善の問題を作ったりしました。
（まあそれは†悪魔的コンテスト†を自称していたのでセーフみたいなところがある（は？））
まあ作問をすると必ず解けなかった人やバグらせた人が文句を言うんですが、それはそういうものです。受け入れましょう。
たまに問題文や設定にミスがあります。そのような経験を通して、次から他の人の作った問題に対して優しくなれると思います。
制約が間違っていたり、書いていなかったりしても、そういうこともあるのだと広い心で受け止めることが大切です。
有志コンはいいけどratedでやるのはやめて こどふぉくん 聞いていますか
公開できるbeet問題のリスト
docs.google.com
