この記事は「競プロ Advent Calendar 2022」の記事です。
競技プログラミングといえば問題を解くことが注目されがちですが、問題を作ることも楽しいよということを布教する記事となっています。
作問は難しそう…と思っている方も、この記事を読んで作問に挑戦してみてもらえると嬉しいです。
最後には筆者がおススメする作問の方法も伝授します。
自己紹介
(自称) 青コーダーです。自称とついているのは最後に Rated 参加をしてからそろそろ 2 年が経つからです。
yukicoder で 30 問ほど作問しました。
関連記事
競技プログラミングの作問に関連した記事は多くあります。ここでは 2 つ紹介します。
作問例
作問は大きく分けて「問題から作る」「解法から作る」の 2 つがあります。また「他の問題を参考にして作る」ということもあり得ます。筆者が具体的にどのように作問したのかを紹介します。
問題から作る
石切りのことをぼんやり考えていたら生まれました。実際に解いてみると作った段階では想定していなかった解法が出てきて面白かったです。
数列に操作を行う問題は競技プログラミングでよく登場します。スワップを使う操作を扱いたかったので作りました。
解法から作る
ACL を使った問題を作りたくて作りました。
調和数の布教問題でした。
他の問題を参考にして作る
AtCoder Beginner Contest 162 F - Select Half の感想ツイートを見て、多くの人が誤解していたところを切り出して問題にしました。
AtCoder Grand Contest 054 D - (ox) の問題文に出てくる操作が面白いと思ったので応用してみました。
Codeforces Round #630 (Div. 2) F. Independent Set が面白かったので、似たような問題を作りました。簡単に書いてしまっていますが、難しすぎて解けない問題や簡単すぎる問題などが途中で生まれています。
その他
問題名から作りました。グルーヴコースターというゲームを知っている人は、Got で始まる曲名が Groove ○○のアナグラムになっていることを知っていると思います。そこで問題名を先に作り、それに合った問題を後から作りました。OR をカバーするということで、OR の値を一部隠した問題になりました。
これも問題名から作りました。アドベコンとかけています。
働きすぎると心身を壊しやすく、回復には時間がかかるというメッセージを伝えたくて作りました。
おススメ作問方法
お待たせしました。ここからは競技プログラミングのおススメの作問方法を紹介します。
それはズバリ…。
数学の本や論文を読むことです！
以下で具体例を挙げていきます。
はじめて群論をテーマにして作った問題です。このように数列に操作を行う問題は対称群と相性が良かったりします。
交代群の共役類がテーマの問題です。
組合せ論に lozenge tiling と呼ばれる有名な問題があり、そこの一番簡単な部分を競プロ用にアレンジしました。
これも群論です。2 つの位数 2 の元で生成される群が二面体群になると知って、位数 2 の操作が 2 つ出てくる問題を作れば面白い問題になるのではないかと思い作りました。
ヤング図形を勉強したので出題してみました。ロビンソン・シェンステッド対応と最長増加部分列の関係は組合せ論では有名ですが競プロ界隈ではまだ浸透していないように感じます。そこで布教問題を作りました。
また、論文を作問に活かすこともできます。
この問題は論文を読んで得た知識をもとに作問した問題です。詳しい話は 1 月号の月刊組合せ論 Natori にて扱う予定です。
とはいえ、こういった方法は敷居が高く感じられるかもしれません。そういったときは競技数学の問題を参考にしてみるのもよいです。実際、No.1659 Product of Divisors や No.1748 Parking Lot は競技数学の問題が元ネタだったように記憶しています。(競技数学をやっていたのは遠い昔なので記憶は定かではありませんが…)
勿論この方法で作問すると数学に偏ってしまいます。筆者ももっと作問の幅を広げたいと思っていますが、なかなか難しいところです…。
最後に、いくつかおススメの数学書を紹介します。
- 雪江明彦, 代数学1 (有名な群論の入門書です。No.1425 Yet Another Cyclic Shifts Sorting の元ネタもこの本の中にあります。)
- Wilson, The Finite Simple Groups. (No.1428 PeRmutation Question はこの本を読んで出題しました。有限単純群は対称群のほかにも行列や符号・格子ともかかわる面白い話題の宝庫です。この本は少し難しいかもしれません)
- 高崎金久, 線形代数と数え上げ (LGV 公式や行列木定理など、競技プログラミングにおいても有用な知識が扱われている楽しい本です)
- フルトン, ヤング・タブロー (ヤング図形関連の作問をする際に役立ちました)
- Stanley, Enumerative Combinatorics. (数え上げ組合せ論についてかなりいろいろ書いてある本です。競プロerで読んでいる人も多いので、数え上げで差をつけたい人はぜひ)
他にも役立つ本はあると思います。もちろん競技プログラミング対策本やデータ構造・アルゴリズムの本の方が役に立つと思うので、初心者の方はこちらを最初に読んだほうがよいと思います。
データ構造・アルゴリズムの論文は読んだことがないので、競技プログラミングに使えるものがどれくらいあるのか気になっています。
お読みいただきありがとうございました。ぜひ作問に挑戦してみてください！
