競プロで作問するときに考えていること

誰かの参考になるかもしれない、と思い。

自分はこれまで比較的多く作問に関わってきました。2010-2014年までの大学生/大学院生時代は topcoder (当時は世界で見て一番活気のあるコンテストでした) で50問以上 writer をやり、以降は ICPC 日本の国内予選と地区予選で、ほぼどの年も少なくとも1問は原案担当をやっていました。自分の思いついたアイデアが色んな人たちに真剣に手にとって考えてもらえる体験は、他ではできないほどの唯一無二の感慨深さがあります。

長く作問に関わっているものの何を考えながらやっているのかあまりダンプしたことがなかったので、少し言葉にしてみたい次第です。

作問は薄い狭間にある輝きを探す試行錯誤

問題づくりは盆栽のようなものだなぁと思っています。何かいいものが天から突然降ってくるというより、アイデアを育てるという感覚が近いように感じます。これについてまず書きます。

競プロの問題としてありうる存在空間のようなものを考えてみたとき、おそらくほとんどは「つまらない」問題になってしまうはずです。つまらないというのは概ね以下のような意味です。

既存のよく知られたアイデア (教科書に載っている手法や典型テク) と同じか、僅かな延長である
単純な方法 (指数時間の全探索など) から計算量オーダーを落とせず、工夫の余地がほとんどない

前者は問題が単純すぎたり基礎的なものを扱っている場合に起きがちで、後者は問題を個性的なものにするための条件設定が複雑すぎたり制約同士の噛み合わせが悪いときに起きがちだと見ています。

しかし面白い問題、独創的な何かのアイデアを必要とするような問題は存在します。かなり大雑把になりますが、空間の一方の側には「よく知られたアイデアの問題」の領域があり、もう一方の側に「工夫の余地がない問題」の領域があり、その間のわずかな隙間に創意工夫の余地のある問題があるようなイメージです。

作問はこの微妙で繊細な領域にある問題を探しに行く旅だと自分は捉えています。

プロセスとしては多くの場合、以下のような道をたどるのではないでしょうか。まずはモチーフを決めます。モチーフというのは、考える対象のことです。グラフや順列を考えたいのか、なにがしかの最適化をしたいのかといった大まかな枠です。モチーフに沿ってとりあえず問題を定式化します。初期の案は、出来がよくないかもしれません。まずは出来が良いのか悪いのかを判断するために問題を注意深く見ることが必要になります。もし改善が必要なら、モチーフは維持しつつも問題設定を変えて何かが変わらないかを繰り返します。これで誰かに見せてもいいと自信を持てるものができたら原案はそこで完成です。

もちろん、モチーフそのものがそれほど良くなく、納得のいくものができないこともあります。その場合は少し時間を置いて再度見直すか、あるいは諦めて他のことを考えるかという択を取ることになります。

自分が問題空間における探索としての作問について持っているイメージは、ライフゲームのようなセル・オートマトンにおけるルール設計が近いです。ライフゲームでは周囲8近傍のセルの状態に応じて次の時刻の状態が決まります。周囲の生きているセルが2とか3なら次も生存して、それ以外なら死滅する、といったものです。ライフゲームは単純なルールから非常に奥深い世界を展開してくれます。一方でこのゲームには変種もありえます。たとえば周囲の生きているセルが4とか5でも生存してもいいことにしても、ルールとしては成立します。しかし、残念ながらそのような変種のほとんどはつまらないと言われています。すぐに盤面が収束してしまったり、でたらめで構造を持たないような動きをするというのです。作問でやりたいことをライフゲームに喩えるなら以下のようになるでしょうか：

2次元のセル・オートマトンというモチーフから、「周囲の生存セル数が2,3なら次も生存」という奇跡的なバランスを持ったルールを見つけ出すこと。

長く興味を持てるモチーフを見つける

上に書いた事情から、作問というタスクは長く対象に向き合わなければ成果が出ないことがしばしばあります。目の前にあるものが実際に解ける保証はありません。解けるかわからないものに自分の時間を費やすことはいくらかのプレッシャーや葛藤もあります。このため、作問では長い間考え続けたくなるようなモチーフを探すのが大事になると思っています。

モチーフを見つける方法は色々あります。自分が取っているのは例えば以下のようなものです。

1. アルゴリズムの有名問題から何かを派生させる

入力を特殊なものに制限することで、通常よりも遥かに効率よく問題を解けるようになることがあります。

部分列マッチを超長い数列に対して行う: ICPC APAC 2024 Bit Counting Sequence
二部グラフ判定を膨張させたグラフで行う: ICPC 2022 国内予選芸術家の苦悩
凸包を特殊な点集合に対して取る: ICPC APAC 2026 L onion

2. 数学やアルゴリズム論にある何かの概念を中心に据える

wikipedia に載っているような枯れたもので構わないので、何かしらの概念を中心に置いてそれを発展させることで何かが生まれることがあります。自分はどうもこのパターンが一番多いようです。意外にも、真新しいことはよく知られていることの割と近くに色々転がっているような気がします。

継子立ての変種: ICPC Yokohama 2023 Fortune Telling
有限体上の行列ランク: ICPC Yokohama 2018 Ranks
ミンコフスキー和: ICPC 国内予選 2023 紋章の形の別荘
風変わりな文脈自由文法: ICPC APAC 2026 Deformed Balance
文法から謎のものを生成: ICPC Yokohama 2024 Tree Generators

3. オブジェクトの操作を考える

プログラミングコンテストではある定まった対象を操作して何かを最適化したり、最終形としてあり得る場合の数を考える問題が度々出ますが、これを自分の興味の出る範囲でやってみると何かが生まれることがあります。

入力は数列、グリッド、グラフ、多項式… 何か興味の持てる物が良いです。

文脈自由文法で定義される式に対する操作: ICPC 国内予選 2022 じわじわ削れ
数列の uniqueness, 行列, 要素の変更操作: ICPC APAC 2025 Duplicates

4. 現実のものや課題から着想を得る

有名な方法です。ただ、自分は試みてあまりうまくいかず、原案まで昇華できなかったことが多いです。

だんじり祭りが周囲の建物を破壊しながら進むことに着想を受けたもの: ICPC Tsukuba 2015 Routing a Marathon Race
JAG 合宿での宿泊: JAG 2013 Tokyo Olympics Center
ハードウェアの本を読んでいたときに思いついたもの: ICPC 国内予選 2018 浮動小数点数

5. インタラクティブ問題をどうにか作る

インタラクティブ問題は最初からそれを作る気持ちで挑まないとできないようです。バッチ形式をインタラクティブにするのは、普通はほとんどできないように見えます。何か秘密のオブジェクトを推測する類の問題では、必要となる情報量から質問回数の下限を見積もっておくと、それを達成するにはどうすればいいのか？という方向で進めやすい気がします。

逆に自分がほぼやったことがないのは、課題設定や概念ではなく解法からスタートするアプローチです。解法からスタートすると考えの幅が狭くなりがちで思いがけないアイデアと出会いにくい気がします。問題づくりが進んで、面白いアイデアがある程度見えてきたらそれに沿うように問題設定を微調整する、程度のことはあります。

作問する上で便利な道具

作問は解けるかわからないものと向き合うことになるので以下があると便利に進むことがあります。

レーティング: 単純に、分析力が高ければ問題が解けるかどうかを見分けたり、別解の可能性に思いを馳せやすくなってよいです。とはいえレーティングはそんなにすぐ伸びるものでもないのと、特定の問題を解くだけなら関連しない分野に対する知見は活きてこないので、なにか作りたいものがあったらそれに向き合い続けるのも大事だと感じます。世界にある知見は限りなくありそれを限られた時間で追いかけるのは難しいことです
解けない問題たち: NP困難, #P-Hard (数え上げにおけるNP困難みたいな概念) である有名問題は一通り抑えておくと、自分が不可能なものに突っ走っていることがわかり便利です。計算理論の知識としては問題の還元くらいを抑えておけば十分に思います

出題先のコンテストについて知る

ここまでは単一の問題を作ることを念頭に置いていましたが、最終的には作った問題は誰かに手にとって向かい合ってもらうことで花開く存在となります。作問に手を付けるときに、どんなところで披露できるか考えておくことは作問の意欲を高めるものになると見ています。

小規模にやるなら例えば学内サークルなどの身内でコンテストをやるというのがあるでしょう。今の世の中で新規なものを作り出すのは容易ではありませんが、受け手側が新規性をそれほど気にしないなら心理的なハードルも低いはずです。

オンラインの不特定多数が参加するものでも国内なら yukicoder のような脈々と継がれているコミュニティがあり、そこに入るのも良いことだと見ています。自分は yukicoder で作問したことがないのであまり定かでないのですが、テスターから意見をもらえたりするのは刺激になりそうです。大学コンテストはもし学内に有志が揃っていたらチームで何かを運営する経験になるように見えます。JAG で模擬コンテストを開くのも同様です。

高みを目指すなら AtCoder や Codeforces のような数千人が参加する規模のオンラインコンテストが対象になるのでしょう。採用されれば喜びは大きいと思います。

締め

なんだか書いてみると具体的な方法論よりもメンタルモデルっぽい話が中心になりました。実際のところ「これをやればいい」というものはあまり無いように感じます。問題空間は広大で、そこをどう歩くかは作問者の感性や欲求次第であり、万人に共通するものはそう多くはないのではないでしょうか。赤ん坊が本能的な欲求で息をして身体を動かしたがるのと同じように、自分の感性を信じて問題空間をぶらぶらと歩いてみるのが良いのではないでしょうか。