初めての競プロ作問(yukicoder)

2020/08/14 に yukicoder さんでコンテストを開かせていただきました.多くの方のご参加 & Fav ありがとうございました!
yukicoder contest 261

writer をするのは初めてでしたが,おかげさまでとても楽しい経験ができたので,その感想を書こうと思います.

記事前半は writer の作業別にまとめています.自分が気をつけた点なども書いているので,これから writer に挑戦する方の参考になれば嬉しいです.

記事後半は問題別にまとめていて,こちらはほぼポエムです.

作業別

原案作成

writer としてのセンスが最も問われる所だと思います.「面白い問題」を作るのが難しいのはもちろんなんですが,そもそも自分が作った問題の「面白さ」を判定するのが難しいと感じました.

そこで,まず「(自分にとって)面白い問題の条件」を考えました.例えば以下のようなものです:

  • 設定がシンプル,問題文が短い
  • 考察量 $\gg$ 実装量
  • 教育的な内容を含む
  • 高度な知識を要求しない(長時間考えることで解ける可能性が高い)

面白さの基準を設定しておくことで,問題の面白さを客観的に評価しやすくなり,良い案も出やすくなりました.

また初作問ということもあり,「想定解が嘘だった」「嘘解法が通ってしまった」という致命的な事故をとても恐れていました.それらを防ぐため,

  • 想定解と愚直解の照合がしやすい
  • 嘘解法を落としやすい

問題にするというのも意識しました.

結果的に,愚直解の $O(N^2)$ を $O(N)$ に落とさせたり,$10^5$ 個オーダーの出力をさせたり,$10^9 + 7$ で割った余りを出力させたりする問題が多くなってしまいましたが,これは仕方ないかなと受け入れました.

問題文作成

シンプルな設定の問題が多かったおかげもあり,特に苦労することはありませんでした.なるべくストーリー性を排し,適度に数学的に記述することを心がけました.

一度書き終えた問題文も,日を空けて何度か読み返しました.これにより改善できる箇所に気づけ,問題文の質を上げることができました.

解説作成

「解説のクオリティは問題の評価にも影響する」と聞いていたので,なるべく丁寧に書きました.もちろん,想定解の正当性の証明も含む形にしました.

解法を言語化することで理解が深まり,より良い別解を思いつくこともありました.言語化大事ですね.

想定解・愚直解作成

自作問題のコードを書くというのは,思った以上に楽しい作業でした.想定解の正当性は既に確認しているとはいえ,愚直解と出力が完全に一致するのを見るのは気持ち良かったです.

2 つ以上の愚直解を書いた問題もありました.また,想定解を書いてみたら想像以上に実装が重く,お蔵入りした問題もありました……(悲しい)

「解説作成」と「想定解・愚直解作成」は,「その作業が終わったらより安心できる方」を先に済ませるのが精神衛生上いいんじゃないかと思います.自分は問題によってどちらの作業を先にやるかを変えていました.

テストケース作成

作問初心者が躓きやすい作業だと思います.主に以下のケースを作りました:

  • 制約の上限・下限(付近)のケース
  • 愚直解がギリギリ通るサイズのケース
  • 一様ランダムなケース
  • 想定愚直解・想定嘘解法を落とすための(一様でない)ランダムなケース

問題によっては,想定嘘解法を落とすために様々なタイプのケースを作る必要があります.今回は上にも書いた通り,この作業が楽になる問題ばかり作ったおかげで,そこまで大変ではありませんでした.

恥ずかしながら Rime 等のツールの導入を面倒臭がってしまい,validation を目視確認と assert で済ませてしまいました.次回作問する機会があれば,ぜひ支援ツールを使ってみようと思います.

問題別

A: Digit Sum Sequence

問題: No.1168 Digit Sum Sequence - yukicoder
Tester: くる (@ningenMe) さん

以前くるさんから「コンテストの参加人数を把握するために,1 問目には簡単な問題を置くといいよ」と教えてもらったので,それに従いました.

★1 で面白い問題を作るのは不可能に近いので諦めて(!),「愚直解とエレガントな解があって,その両方が通る」問題にしてみました.AtCoder Beginner Contest の A,B 問題でよく見るタイプですね.

tester 作業も終わった後に,yukicoder で上位互換の問題が既に出題されていることに気づきましたが,「★1 だし既出は大目に見てもらえるかな」とそのまま出題しちゃいました.
上位互換の問題 → No.933 おまわりさんこいつです - yukicoder

B: Row and Column and Diagonal

問題: No.1169 Row and Column and Diagonal - yukicoder
Tester: さかな (@Enjapma_kyopro) さん

最初,B には他の問題を置いていたのですが,その問題が Codeforces の問題と完全に被ってしまったので,急遽この問題を準備しました.

発想一発で解けるパズル枠でした.緑 diff 中位想定でしたが,想像以上に多くの人に通されて驚きました.解説にある解が最もシンプルだと思っていますが,同じ解の人はそれほど多くなさそうだったのが少し嬉しかったです.

ジャッジコードも書かないといけない問題だったので,6 問の中で一番不備が心配な問題でもありました.ジャッジの書き方がよく分からず我流で書いてしまったのですが,これで良かったのでしょうか……?(未だに分かっておらず)

C: Never Want to Walk

問題: No.1170 Never Want to Walk - yukicoder
Tester: 37zigen (@___n___z) さん

たくさんの Fav ありがとうございました.正直かなり嬉しいです……!

解説にもある通り,「張る辺の数を減らす」「区間の union は累積和」という 2 つの典型を組み合わせて作りました.典型を組み合わせるというのは王道の作問方法のようで,そうしてできた問題は多くの人に好かれやすいのかもしれません(?)

想定解を 2 つ準備していましたが,それ以外にも 2 つほど別解を観測しました.作問側としても勉強になり楽しかったです.

D: Runs in Subsequences

問題: No.1171 Runs in Subsequences - yukicoder
Tester: きり (@kiri8128) さん

いかにも AtCoder Beginner Contest の F 問題あたりで出そうな数え上げの問題を目指しました.

tester 解が writer 解よりもずっときれいだったので,解説ページでは tester 解を全面に押し出すべきでしたね(後悔ポイント 1).

tester 解にもある通り,アルファベットサイズを $M$ として $O(N+M)$ でも解けるのですが,$O(N+M)$ を要求するのか $O(NM)$ を許容するのかなり迷った上で,$O(NM)$ を許容することにしました.$O(N+M)$ だと DP の in-place 化が必須になり,これも面白いので,$O(N+M)$ を要求してもよかったなと思っています(後悔ポイント 2).

E: Add Recursive Sequence

問題: No.1172 Add Recursive Sequence - yukicoder
Tester: 熨斗袋 (@noshi91) さん

いわゆる「imos 法」,一般化できるのちょっと面白いと思うけどあんまり知られてなさそう,ということで問題形式にしてみました.

つる (@theory_and_me) さんにとても気合いの入った解説記事を書いてもらえて嬉しいです.まだ読まれていない方はぜひ.

当初の writer 解は $O(K(MK+N))$ でしたが,これを tester さんに $O(K(N+M))$ に改善していただけたので,こちらで出題することにしました.

この問題は制約・TL の調節にかなり苦労しました.$O(K(MK+N))$ を落としつつ $O(K(N+M))$ を確実に通るようにしたかったのですが,結果的に 2 人の方に $O(N(M+K))$ の愚直解を通されてしまいました.

定数倍高速化すれば $10^{10}$ も通りうるということで,制約の上限が $10^5$ ではなく $2 \times 10^5$ になっていることが多い理由がよく分かりました.よく覚えておきます.悔しい〜〜〜

F: Endangered Species

問題: No.1173 Endangered Species - yukicoder
Tester: ほげほげ算数@競プロ (@hogehogesansuu) さん

これが一番最初に作った問題でした.小数型の競プロ問題が少ないので,ある程度面白い小数型の問題を出題したいという気持ちがありました.

最初,誤差の評価を雑にしていて,想定解が正しい答えを返していないという大惨事に気づいていませんでした.tester さんに指摘され,もうちょっと真面目に評価したところ,想定解破綻に気づけて制約を変更することにしました.本当に助かりました…… これに懲りて,次に小数型の問題を作るのはずっと先のことになりそうです.

解説には書きませんでしたが,実は絶滅確率はすぐに収束するので,$50$ 日後くらいの絶滅確率を出力しても AC となります.

全体の振り返り

上で書いたように tester のみなさんにかなり助けて頂き,E 問題以外では事故もなくコンテストを終えることができました.本当にありがとうございました.E 問題も影響はそれほど大きくなかったので許容範囲内かな,と思っています(甘い?)

苦労もありましたが,やはり自分たちの問題を数百人の方に解いていただくというのはとても楽しい経験でした.コンテストに出るのとはまた違った面白さがあります.作問をしてみようかと迷っている方には自信を持ってお薦めできます.

一方で,力不足も実感させられました.(自分のような凡人が)面白い問題を作るためには,多くの問題を知り,多くの典型を学ばなければなりませんが,自分は解いた問題の数がまだまだ足りていません.より多くの問題を解き,アイデアを溜め,1 〜 2 年後くらいにまたセットが組めたらなと考えています.

最後に,問題を解いてくださったみなさんと,このような貴重な場を提供してくださった yuki さんに改めて感謝します.ありがとうございました!

タイトルとURLをコピーしました