yukicoder で単独コンテストをやった話
前回
（前回よりも作問の腕は上がっている……はず）
作った問題の一覧
これまでの傾向
数え上げ: 5
構築: 3
その他数学: 1
最適化: 1
はじめに（ここから本題）
yukicoder contest 326 で単独 writer を務めさせていただきました、NatsubiSogan です。ご参加ありがとうございました。
単独回はいつかやってみたいなあと思っていたので、非常に嬉しいです。お楽しみいただけたのであれば、こちらとしても嬉しい限りです。
テスターを引き受けてくださった SugSugar さん、Cyanmond さん、first_vil さん、Forested さん、nok0 さん ならびに、全体テスターとして問題文や難易度のチェックをしてくださった penguinman さんに、心より感謝申し上げます。本当にありがとうございました。
以下、ポエムです。読む価値はないので、読みたいところを目次からお読みください。
目次
コンテスト開催まで
まず、コンテスト開催までの振り返りをします。
単独回を開きたい！（技術室奥コン終了後）
前々から思ってはいましたが、本格的に単独回のための作問を始めたのは技術室奥コンが終わった後（つまり、9 月以降）です。
問題を作ろう！（9 月～10 月初頭 / 11 月～）
あの手この手で問題を作りました。
前回（すべて「問題設定から生やして解いた」）とは作問方法を変えました。具体的には、設定から生やすのに加えて、解法から生やす、「このアルゴリズムをもとに考察を進める問題が作れないか？」と考える、いい性質を見つけたのでどう問うか考える…などの手法を取りました。
没になったやつもいくつかあります。
10 月の間作問に時間が取れていないのは、文化祭準備のためです。（本校生には、私含め文化祭に命を懸けているような人が多くいるので、これは仕方ないです）
準備！（生え次第）
社畜なので 正直この作業はかなり楽しいです。
- 分かりやすそうでよさげな問題文（制約などを含めて）を書き、
- 想定解を書いて、提出し、
- ケースと想定出力を生成し、
- バリデータを書き、入力をチェックする
これだけなので、頑張れば一問あたり 30 分でできました。
問題文についてですが、基本的には、自分の読みやすいように書けば問題ないと思います。ただ、それでも分かりづらくなってしまう場合はあるので、いったん頭を真っ新にして問題文を読んでみる、テスターさんの意見を仰ぐ、といったプロセスは必要不可欠です。
想定解はバグらせないようにしましょう（今回、一度やらかしました。Forested、ごめん）
ケース生成に関して、今回はだいぶサボってしまいました。具体的には、
- ケース生成が楽な数え上げを置く
- 面倒そうなやつは、複数ケース形式にして誤魔化す
- あとはランダム
みたいな感じです。大体はこれで何とかなったんですが、Yes/No とか最適化だとちゃんと作らないとまずいことになると思います。強いケースの作り方、誰か教えてくれ～
バリデーションについては、yukicoder だと testlib.h が簡単に使えるので、積極的に利用してきましょう。入力チェックをするだけなら仕様もだいぶ簡単です。
あと、難易度は過大評価気味の方がいいです。（過去に何度も過小評価でやらかしています）
テスターさんを呼ぼう！（準備終了次第）
今回は、準備が終わり次第テスターさんを募集しました。
基本的には、Twitter で「募集します！」と呟けば、（yukicoder 公式さんもリツイートしてくれるので）数日以内には見つかると思います。yukicoder Slack で募集するのもアリです。
テスターさんには本当にお世話になりました。A では、ケースが弱かったのを修正してもらいました。
全体テスターさんを呼ぼう！（12 月末 / 問題が出揃った後）
出題する問題が出揃ったところで、前項と同じように、全体テスターさんを募集しました。
全体テスターの penguinman さんにも色々なアドバイスを頂きました。具体的には、全体テスターさんの指摘で C, E の難易度が 0.5 上がり、C の問題文の赤字部分を強調することになりました。
テスターさんの指摘は、受け入れた方がクオリティの向上につながると思います。
問題ごとの講評など
A: Summer Day (★1)
tester: SugSugar さん
FA: SSRS さん
私は夏日です。（それだけ）
暑すぎる夏って嫌ですよね。
一問目には簡単なのを置いた方がいいと思っているので、本当に簡単なのを作りました。
さっきも言ったんですが、めちゃくちゃ適当にケースを作ったせいで、テスターさんに「ケースめちゃくちゃ弱いと思います」みたいなことを言われてしまいました。すぐさん、ごめん……
B: Random XOR (★2)
tester: Cyanmond さん
FA: heno239 さん
数え上げ / 期待値 枠が一つはないとアイデンティティを喪失しそうだったので入れました。
「夏日さんコンだし一個は期待値が出そう」みたいな言及があったんですが、はい。
XOR を見て「ビットごとに考える」という方針に走ってみるのは割と典型だと思います。二項係数の公式を知らないと辛そうです。そういう意味では、割と「典型+知識」に寄っている問題かも……
C: Segment Game (★2.5)
tester: first_vil さん
FA: 沙耶花 さん
ゲームです。初めて出しました。複数テストケースで、生成をサボりました
とは言っても、慣れている人からしたらだいぶ典型寄りの問題だと思います。そもそもこの問題自体、「対称性に注目する」という手法に感動して、解法から作った問題なので……
Nim の必勝法の話が分かっていれば発想は難しくない……かも？
D: Range Score Query for Bracket Sequence (★3)
tester: Forested さん
FA: hitonanode さん
クエリ処理です。これも初めて出しました。「NatsubiSogan ってクエリとか出す writer だっけ……」と驚かれた方もいるかもしれません。
括弧列をいじっていたら生えました。「操作回数」をうまく特徴づけてやるのが本質で、あとは実装を頑張るだけです（ここは典型）。
幅を持ったものを数えるので、実装が（セット内の他の問題と比較して）重くなってしまっていますが、お許しください。
想定解をバグらせたのはこれです。些細なミスではあったんですが、Forested、ごめん……（2 回目）
E: Remainder of Sum (★3.5)
tester: nok0 さん
FA: hitonanode さん
最適化です。出すのは二回目ですが今回は $\mathrm{O}(1)$ です。最適化系って生やすの難しくないですか？
「特殊なグラフの最小全域木を求める問題が作りたいなあ」と思って、まず最小全域木の問題として作ったものを、適当な操作に言い換えました。ちょっとしたカムフラージュなので一瞬で見破った方もそれなりにいそうですね……
基本的にはクラスカル法の要領で考察を進めていくだけなんですが、割と頭が壊れます。解説はかなりごちゃごちゃしているので、とりあえずいろんなパターンで実験をしてみてください。言いたいことが伝わる……かもしれません。
頭が壊れるので、こどふぉにありそうな算数パズルみたいな感触になってしまいました。楽しいとは思うんですが、もうちょっと後味の悪くない最適化の問題を生やしたいです……
F: Intersection of LIS (★3.5)
tester: nok0 さん
FA: tute7627 さん
割と特殊な見た目の問題です。実は、このセットの中で一番最初に作った問題にして、一番の自信作です。これを出すために他を作ったまであります（流石にない）
完全に問題設定から生やしました。「すべての○○に含まれる要素を列挙せよ」みたいな問題を作りたいとは前々から思っていたので、かなり綺麗な形になって嬉しい限りです。
「取り得る最小値と最大値を求め、比較する」というのは、かなりの発想力を要求すると思います。私自身、この解法が降ってくるまでに数日間を要したので……
あと、LIS の復元を書いたことがない人がそれなりにいるんじゃないかなあと思いました。頑張ってググると出てくるので、覚えておいて損はないと思います（説明箒🧹）
penguinman さんに「Yutori に似ている」という指摘を受け、「たしかに」となりました。
このテクって意外と典型だったりするんですかね……
おわりに
- 構築がねーじゃん！→ ごめんなさい、普通に作れませんでした
- 過去の自分、ごめん
過去の自分 - 4 問目までの問題名の頭文字を
SSRSにする案があったんですが、やめました。SSRS さん、本当にごめんなさい - ごめんなさいしか言ってない
- 次回はパ研合宿のコンテストでお会いすることになる……かもしれません
