初投稿につき5秒で自己紹介
AtCoderを中心に競技プログラミングをしている23歳。
プログラミング初経験で競技プログラミングに入って、競技歴は1年4か月。
レートはAtC-A 2188(Highest 2213) AtC-H 1313 Codeforces 2278
趣旨
先日、yuki4869杯 Programming Contest vol.1という自作コンテストを開きました。
作問初めて。コンテストの運営側初めて。Markdown記法すらよくわかってない。という非常に怪しい状態から、3週間の突貫工事で、開催までこぎつけるに成功。
こんな非常に怪しげなコンテストでしたが、結果として筆者の想定の倍となる65人(コンテスト中に1問でも正解した人)に参加を頂くことができました。
今回は忘備録も兼ねて、コンテストに向かうまでの話を書き連ねていきたいと思います。
もしかしたら、今後コンテストを開きたい人の助けになるかも？
コンテスト開催を決意
事の発端は、3週間前の日曜日。
今回お借りしたMojacoder様で、第5回湖風祭コンテスト情報という有志コンテストがやっており、そこのWriterと絡みがあったので、参戦しに行ってました。
個人的に有志コンテストというものに参加することが初めてでどんなもんかなと思って参戦したのですが、問題設定が独創的で、言い方を変えれば自我を出せているという印象を受けました。
（ちなみにコンテストは惨敗）
自分も好きなものや、思いついたアルゴリズムを使ったオリジナルな問題を作ってみたい。
そしてその夜には、コンテストの開催を決意したのでした。
問題作成期間
コンテストを開くならば、必要なのは問題。
でもその前にある程度のコンセプトを決めておかねば。
どういう参加者が来てほしくて、どういう問題群にするのか。
一番参考になるのはみんな大好きAtCoder Beginner Contestでしょう。
一応ABC卒業というレートには到達しているので、下手なG問題以外の難易度帯はアルゴリズムを網羅しているはずなので、自分で作れる可能性が高いし、確かめられる。
けどABCをそのままコピーするのも面白みに欠けるということで、今回のフォーマットは9問120分。難易度帯でいえば ACCDDEEFF という形にしようと決めました。
その後、一問構築の問題を入れようと思っていたところに、ARCチックな問題ができて、その下位互換ならABCで出してもよさげかな、という問題が一つ。
元々のボス問をうちのChatGPT（当時は5.5)に投げて改善案ある？と聞いたところ、面白いアレンジ案を出してくれたのがもう一つ。
最初のフォーマットを決めた段階で告知を始めていたのですが、黄色以上の方も反応してくれていました。
ただ9問だと黄色以上の方だと時間を余らせてしまう可能性が高そうだなと思ったので、この上位互換2問を追加し、合計11問コンテストとなったのでした。
話は前後しますが、問題自体は案外早々と固まっていて、4日でひとまずの9問セットが埋まっていたと記憶しています。
この辺体調を崩し、熱を出しながら、AWTFを見ながら、作業していたのが懐かしい。
問題固まったから、日程確定させていいやろ。
いろんなものと被らないようにしながら、けどみんな来てくれそうな時間帯だと、日曜日の21:00やろなぁ。
ARCもAHCもない週にしようとしたら......、2週間後か更に1か月後しかない。
コンテストやりたい欲が強かった自分は迷わず2週間後に決定。
この選択がなかなか厳しいスケジュールになったと気づくのには少し時間がかかりました。
テストケース作成
正直一番きつかった作業がこれ。
なんせやり方わからないですからね。
randomケースを作るくらいなら、適当にコード書くだけでできますが、意図的にそして確実にロジックの間違っているコードを叩き落とすのが非常に難しい。
ここではChatGPT(5.6にヴァージョンアップ)に活躍していただき、どういう嘘解法がありそうなのかをラリーして、その解法を元に落とすテストケースを作ってもらい、自分はちょこちょこ確認する。
特に今回はPythonでもストレスなく通せるような制約を裏コンセプトにしていたため、自分の書けないPythonのコードを何回も書いてもらい、ランダムケースをひたすら作って速度を確認し、調整することが多かったです。
結局テストケース作成＆解説作成には2週間かかり、作業が完全に終わったのは前日の朝4時（それは当日やん）
それも一抹の不安を抱えながらのコンテスト開催でした。
各問題の話
Total Victory
特に語ることはないですね。
筆者がとにかくSASUKE好きなので、その宣伝をしたかっただけなのです。
そのためか、参加者の感想にはだるめ、コピペしにくいなど散々な言われよう。
でもAtCでは絶対できない書き出しなわけじゃないですか。有志コンテストくらいやらせてよ。
ちなみに次回のA問題もSASUKE関連問題です。対戦よろしくお願いします。
Best Broadcast Budget
問題の中身について話す前に、問題タイトルについての話をしておきたいと思います。
今回の問題のタイトルは(A問題を除き)すべてが頭文字統一3単語(EX問題は4単語)になっていました。
あんまり気づかれてなさそうだったので悲しいところですが、正直自分も問題タイトルなど一切見てないので、文句を言う資格はなさそう。
閑話休題。この問題の話に戻りましょう。
ABC-C問題のテンプレと言えばソートか貪欲かの2択というざっくりとしすぎなイメージを持っているのですが、この問題はソートの方です。
シンプルだけど、SASUKE要素を取り入れようと思ったので大トリ、SASUKEでいうところのゼッケン100は絶対に放送するという要素を一つまみしてみました。
初案では88番目を必ず放送しなければならないだったのですが、それはSASUKEブラックネタすぎるということで没に。
Two-Three Transformation
よくある隣接する項に同じ数を足す系の問題です。ABC-Cの貪欲の方です。
初案では+2だったのですが、流石に味気なさ過ぎたのと、頭文字同じ3単語縛りを途中から始めたもので、タイトルもなぁという悩みを抱えていました。
そんなときふとTwo ThreeってTやん。しかも既存の問題とアルファベット被りしてない。
ということで、このちょい捻りの問題ができました。
ABC-CというよりはARC-Aという印象の問題にはなってしまいましたが、いい感じだったのでは？
隣接追加で1だけできないという部分をコードに起こそうとしたら、なぜか0もできないことにしてしまった人を、何人か目撃して、かわいそうに（他人事）などと思っていました。
Hop Hop Hamstring
ABC-DのDは DPのD ということで、ド典型のDPを一本投げてみました。
元ネタは政治ネタなので気になる方は調べてみてください。
制約から見えるDP臭に、状態数が４で遷移も7本だけというところで、気持ちよくDPできた人が多かったのではないでしょうか。
ド典型 DP D-400 綺麗でしょ。
ちなみに自分は肉離れの経験はないです。骨折ならあります。
Clipped Collatz Cost
ダントツでお気に入り問題です。
これはいい問題ちゃいます？
コラッツ予想という奇数なら3倍して1を足す、偶数なら2で割るという操作を繰り返すと、どんな整数から始めても1になるという未解決問題が元ネタです。
今回の問題では、上限としてKを作ることで、高々K頂点のグラフの距離を求める問題に帰着しています。
実はこの問題を作ったのはすべての問題の中で一番早く、コンテストなど開催することすら考えていない2月の頃でした。
ABC446-E問題ではMで割った余りという、上限Mというキャップを掛けることで頂点数をM*M個に抑える問題なのですが、この問題が結構お気に入りでして、その時にコラッツ予想を元ネタにして上限を制限したらDFSできそうだなと思っていたのでした。
この時は上限Kにして、通常のコラッツ操作を繰り返して１に到達するまでの回数を求めよ。という問題でした。
この時点で頂点１から逆辺を辿って最短距離という解法を考えていたのですが、いざ実装すると普通にメモ化再帰でいい。
問題としての面白みが正直ないことに気付いてしまったわけです。
でもコンセプトとしては面白いし、どうにか成立させたい。
次に考えたのは、正規の操作ならコスト０、そうでない方をやるならコスト１という01-BFSの問題でした。
ただこれはせっかくO(N)でできる01-BFSの特徴を生かした制約にしようとすると、(つまりダイクストラを許さない制約にしようとすると)、Pythonが厳しいことになってしまいました。
つまりC++でダイクストラを潰し、かつPythonが余裕をもって通るような制約のポイントを見つけられなかったのです。
ということでこちらも没に。
最終的には今の制約である、コスト1-2の2^18≒2*10^5になったのでした。
ちなみになぜMAX2^18で、全N項ではなく、コスト別の個数37項を出力せよだったかの理由ですが、コストを上から押さえつける説明をするのがめんどくさくて、2^18で2で割り続けたら18回で1になる。
つまり高々コストは36だろっていう暗黙の押し付けをしたかったのと、2^18は提示しておかないと不親切かなと思い、サンプルに2^18を入れたかった結果、サンプルに並ぶ2^18個の整数を見せるわけにはいけなかったという話でした。
この問題まじGood Point高めですが、結果的にE問題相当の問題となってしまい、看板に偽りありということで申し訳ございませんでした。
Kimariji Key Keeper
実は百人一首の経験があります。地元の都道府県の代表にもなったことがあります。
ということで、百人一首も一つ入れたいなと思ってなんとなくNovistepsの文字列かなんかの問題集を開いたところ、一番上がKaruta。
それ俺がやりたいことやねん。
ということで少し別のアプローチを模索していたところ、徐々に追加してくことで決まり字を変化させていくのはどうだろうという発想に至りました。
問題文中には使ってませんが、この問題は実質LCPを求めなさいという意図であり、特に集合中の最大LCP(って言い方合ってる？)は前後の2つを見ることで求めることができるという、まぁまぁ有名テクが使えるように問題設計をしました。
という書きぶりから予想されるように、この問題の想定解法はTrie木ではなく、setだったんですね。
これは筆者がTrie木を未だにまともに使えてない（アルゴリズムの理解はしているけど、実装がまだあまりよくわかってない）ことに起因しまして、普通にsetで来るやろと思ってたのですが、ふたを開けるとTrie木しかいないと。
まぁTrie木の方が簡単か。
ちなみに集めた文字列の最後の文字が常に０になっていた理由は、それがないと決まり字が存在しないパターンができてしまうからですね。
例えばapとappだとapの決まり字が存在しないことになってしまいます。これがLCP+1と見せかけておいて、明確なLCPとの定義の違いです。
この事象を回避したいが、決まり字が存在しないことはないですよ～って問題文で説明するのも難しかったため、制約で回避することとしました。
これはちょっと問題文が悪い気もしますが、しょうがないかなぁ。他の解決策が思いつきませんでした。
Maximum Merit Move
1問飛ばして8問目です。
一見後戻りができないことで、解くのが難しそうですが、筆者が勝手に2nd-DPと呼んでいる、2番目までの値を持っておくDPをすることで簡単に解くことができます。（実装が簡単とは言ってない）
この問題は元々1ターンに2マス以上動いて最後に止まったマスの数字を加算。引き返せないのはターン中だけで、ターンとターンの切れ目はOKという制約で原案を作っていたのですが、もっと言えば、1ターンに動けるマスの数をK面さいころにして、期待値DPまで難易度を上げて作っていました。
流石に要素盛りすぎだったのと、Pythonさんのせいで制約が難しくて削っていったところ、筆者的にはシンプルな2nd-DPの問題に落ち着きました。
今見てもT<=150って制約ちいさいな……
元ネタは自分が小さいころからやっていたすごろくゲーム桃鉄だったのですが、元ネタ要素完全に消えたな。
まぁそういうこともある。
Sequence Scoring System / Super Sequence Scoring System
今回の第1ボス問。
Super Sequence Scoring Systemって名前かっこよくない？
自分が勝手に思うABC-Fの花形アルゴリズムといえば、やはり遅延セグ木であろうということで、最初からボス問は遅延セグ木にしようと決めていました。
どうやってこの問題を思いついたかは覚えていないのですが、遅延セグ木は遅延セグ木でも、変なstructを作らないといけない問題にしようと思っていて、その結果出てきたのが巡回クエリでした。
組み合わせを愚直に持ってしまい、それを巡回するのを自分は見たことが無かったのでこれでいこうと。
あまりにも見た目が遅延セグ木すぎますけどね。ボス問としてはいいところに落ちたのではないでしょうか。
というこの問題について、うちの相方のSol君(ChatGPT-5.6 Solのことです)と壁当てしていたところ、巡回ではなくそのまま変換則を列として持つと拡張できることに気付きました。
これは面白いと思い、いくつかクエリの候補を上げてもらって、その中から今回の掛け算と入れ替えのクエリを登場させました。
掛け算は全単射ではなくするために入れたクエリで、ちゃんと加算してあげないと正しい答えが出なくなりますよ要員。
入れ替えは見た目いかつい要員でした。
そしてこの問題のタイトルどうしようかなと考えていて、元々Periodic Sequence ScoreというタイトルだったところにSuperを付けようと。（ここにも元ネタがあるのですが、どうでもよさ過ぎるので省略）
Super Periodic Sequence Scoreという文字列を眺めていたところ、SSSSにした方が見た目良くね？となり、ここから頭文字固定の問題タイトルにすべて変更したのでした。
頭文字固定がありながらここにSystemという単語を持ってくるSol君恐るべし。
Exact Error Engineering / Earliest Exact Error Engineering
裏ボス問にして、ABCにまさかの構築問題という地雷要素もあるこの問題。
まず懺悔をしなければならないことがあります。
簡単verの方、既出でした。すいませんでした。
まずこのセットに構築を入れようと思ったのは、とあるよく絡んでもらってる子が構築大好きマンでして、その子のためonlyという不純な動機でした。
いくつか問題を作っていたのですが、その中で今回のボス問の方が完成し、自分で作っておいて解くのに2日かかる始末。
その中の部分問題として簡単の方が浮かび上がってきて、これくらいなら出せるかなという感じで採用に至りました。
構築としてシンプルで、最大値は逆順にするだけ、狙ったコストにするのも入れ替えをしていくだけという感じだったのでE問題相当として置いておきましたが、普通にF問題相当。というかABCに出すな枠でしたね。
ボス問の方はARC-800相当と思っていましたが、そこまででもなさそうでしたね。
自分は解説を書くことを考えて証明まで完璧にすることを考えていたので、難しく捉え過ぎていたようです。実験で思ったより簡単に解けるようで。悔しい。
既出であったのに気づいたのはコンテストの1日前で、差し替える余裕がなかった。CF953をざっと見た感じ、このコンテストに参加してくれそうな人で触ってる人はいなさそうだったので、そのままにしましたが良くないですねぇ。
一応既出チェックは3回やっていたのですが、1回目と2回目には引っかからなかったので、3回やってよかったというか、Sol君もっと頑張れというか。
コンテスト後の反省
山ほどあるのですが、まず一番最初に出てくるのはTesterを呼ばなかったことです。
呼ばなかったというより、呼べるタイムスケジュールではなかったのですが、やはり自分とSol君だけではちょっと足りないかなというところが多かったですね。
問題文の日本語の読みやすさとかは、人間じゃないとわからないですからね。
ということで、次回vol.2のTesterを募集しています。
問題文を清書したりざっとテストケース作ったりにまだ時間がかかりますが、問題はもう既にできているので1,2週間後くらいからでしょうか。
ぜひお助けしても良いよ、という心優しき方が居ましたらご連絡いただけると幸いです。
そして次に大きいのはテストケースの作り方ですね。
現在確認しているだけでも、2つの非完璧なコードがACになったことを確認していまして、どうやって今後その穴を塞ぐことができるかを考えておく必要がありそうです。
どうやって作ってるんだろうか。参考になりそうな記事がありましたら教えていただきたいです。
その他にも、難易度調整とか、問題文の調整とか、制約が実は不正確だったりとか、準備中には見えていなかった粗がちょこちょこ見えてきたなというのがコンテスト後の感想です。
とはいえ、初回としてたまたまかもしれませんがこれだけの人数を集め、感想では問題セットに満足されているというのをかなりいただきましたので、自信と、なにより今後のやる気をいただきました。
文中に書いた通り、yuki4869杯 Programming Contest vol.2の問題案は出揃っております。第2回やります。
ARCなどの動向にもよりますが、シルバーウィーク中の開催を目指しております。第1候補は9/21(月) 21:00~です。
今回はたっぷり2か月準備に充てさせてもらいますので、vol.1より3段階クオリティアップしたコンテストにして戻ってきたいと思いますので、その際はぜひまたの参加を/初めての参加をよろしくお願いいたします。