3/1(金)21:20~23:50に、yukicoderでコンテストを開催しました。それに関するあれこれを書きました。
コンテスト： yukicoder contest 419 https://yukicoder.me/contests/485
開催までのいきさつ
3年前くらいから作問してみたいと思っていましたが、ちっともアイデアが浮かばずほとんど作れませんでした。 半年ほど前に初めて、自分でも面白い！と思える問題を作ることができ、 それをきっかけに… かどうか分かりませんが急にアイデアが湧いてくるようになりました。
風呂につかっている時間が作問時間になっていて、コンスタントに問題数が増えていき、 年末ごろに15問くらいたまったので、年末年始の休み中にyukicoderに登録しようと一念発起し、今回の開催に至ります。
作問作業は思っていたよりずっと大変でした。年末年始で6問登録しようと思っていたら1問しかできず、 以降週1問ペースでちょっとずつ作業していました。問題文と解説を書くのが特に大変でした…
しかし、testerさんに解いてもらえるだけでめちゃくちゃ嬉しいもので、頑張った甲斐があったなあと思いました。 この文はコンテスト開催前に書いてますが、コンテストでたくさんの人に解いてもらえたらもう大変なことになりそうです。
各問題について
A問題 Increasing Strides
tester: p-adicさん
風呂につかりながらふと、1メートルずつ増やしながら直角に曲がったら元に戻れるだろうかと思い浮かび、 うまいこと解けたのでほぼそのまま問題になりました。 当初はNが偶数限定でしたが、全体テスターのてんぷらさんに奇数でも解けると言われて急遽奇数もありにしました。 不可能の判定が、奇数集合と偶数集合で補い合ってて面白いなあと思っています。
個別テスターのp-adicさんには何度も相談させてもらい、大変お世話になりました。
B問題 XOR Slimes
tester: p-adicさん
XORは和より必ず小さいのがミソで、隣と合体するかどうかだけ考えれば良さそうな気がしつつ、ほんとにそれでいいのかすぐには分からない、 という問題です。考察部分面白いなと思い、6問のうちまずはじめに出題を決めた問題でした。
C問題 Falling Block Game
tester: AngrySadEightさん
この問題は3年前に原案を考えたもので、当時はスタート地点1カ所で、想定解は「答固定して下に到達できるか判定、にぶたん」でした。 最近その問題を久しぶりに思い出して、logが落とせそうだなあと考えているうちに、 多点スタートにすればそれを効果的に問えると気付いて完成しました。 にぶたん解法に誤誘導するために問題文に「最大値を最小化」の決まり文句を入れておきました。
ちなみに私は問題文のとおり本当に腱鞘炎で、3年前の時点でそれをネタにしようとしてました。そして未だに治らずです…
D問題 L-R Nim
tester: Nachiaさん
Nimで、自由に山を選んだらどうなるだろうというところからあれこれ設定を考えて、 かなり紆余曲折してできた問題です。最終的に「どこか一か所に±1」で出題しようとしてましたが、 それを±xにしてもそれほど候補が増えないことに気が付いて「これだー！」となりました。
当初N=1000にしていましたが、NachiaさんにきれいなO(N^2)解で通されてしまい、 それを落とすための制約調整＆テストケース作成が難しくてめちゃくちゃ大変でした。 普通にテストケースを作ると解なしか解だらけになってしまうので、工夫がいります。 テストケース生成関数のバージョンが18までいきました。
E問題 Manga App
tester: nok0さん
某漫画アプリそのものに近い設定の問題です。 実際、寝る時間と時短アイテムを使うタイミングの関係によく悩んでいたので、 これ問題にならないかなあと思って考え始めました。ただの貪欲かなと思っていたら、じわじわと反例が出てきて、思っていた以上に難しい問題になりました。
解説に書いた「O(N^3)のDP」が当初の解法で、それをO(N^2)だと思っていました。 解説を厳密に書いていくうちに、あれ、きっとO(N^2)だろうけど、なかなか絶対と言い切れないな…となり、 2日くらい考えた結果、逆にO(N^3)のテストケースができあがってしまいました。
しかし残念ながら、nok0さんにはマラソン解法で、 全体テスターのてんぷらさんには普通の高速化？でO(N^3)解を通されてしまっています。 マラソン解法は追加テストケースで防げましたが、てんぷらさんのは高速化なので防げなさそうです…
F問題 Sweep Cards (Easy)
tester: chineristACさん
当初は、Nマスのマス目にカードの山が置かれる問題でした。つまり空いたマスもあって、空き方も数える問題でした。 解き方も、解説で触れたO(N^2)のDPでした。
ふと、昔noya2さんのtesterをしたときの鬼ムズ問題（https://yukicoder.me/problems/no/1939） と雰囲気が似ていることに気付き、ラグランジュ反転で解けることに気付いて飛び上がりました。
更にびっくりなことに、マス目をなくして空いたら詰めるような問題設定にすると、 最近勉強したラグランジュ反転のk乗のついたやつまで適用出来て直接解が求まってしまうことが分かり、脳汁ドバドバになりました。
そのときのツイート：https://x.com/hamamu_kyopro/status/1745437789553086882?s=20
控え目に書いてますが、実際はもう、手が震えたりして興奮すごかったです。
だいぶ背伸びした問題だったので、 テスターのchineristACさんにとてもお世話になって何とか形になりました。 畳込むとO(NlogN)になる式がOEISに載っているのを教えてもらい、Nの上限を10^7にしました。O(N)にする高速化を想定にするのはマニアックすぎるかなとはじめ思いましたが、既にラグランジュ反転を要求してるし、ゆきこだし、OEISを避けるという大義名分もあるし(?)でまあいいかなとなりました。
G問題 Sweep Cards (Hard)
tester: いやもはや writer: chineristACさん
chineristACさんより、F問題のOEIS回避にこうするのはどうでしょうと提案された問題です。 軽い感じで書いてあったのでちょっとした変更なのかなと思っていたら、 じっくり見れば見るほど意味不明（式は追えるが何でそんな事するのか分からないの意）で、 でも何か解けていて、鳩に豆鉄砲状態でした。 何故この式変形をしようと思ったのか質問したら、 「僕もびっくりしました」とのことだったので、きっと神が降臨しているのだと思います。 （すみません、ちょっとおもしろおかしく切り取りしました）
だいぶ元の問題と違う解き方になるので、別問題に分けることにして、G問題が生まれました。 ぜひ数え上げ達人の方々に考えてみて欲しい問題です。
おわりに
準備が大変だったのでしばらく休みたいですが、 問題はだいぶたまっているのでそのうちまたやりたいなと思っています。
