挨拶
にゃ～ん
趣旨
yukicoder contest 462 を開催しました。
Aから難しすぎたのは反省ですが、致命的なミスなく終われました。
頑張って産んだ問題たちなので楽しんでいただけたならとても嬉しいです。
作問の紆余曲折とかいろいろを語りたい。
ChatGPT o3-mini に問題文と制約を投げて正しい解法を思いつくか試します（実装できるかまでは見ません）。
特に頼まれたわけではないですが……
yukicoderにはサイトサポーター👑という仕組みがあります。作問をしない場合大きなメリットはありませんが、年間1000円ポッキリで競プロ界隈を支えられます！
収支報告などは見当たりませんが、サーバー利用料も決して安くないと思います。
懐に余裕のある方はどうか支援してあげてほしいです。m(__)m
全体
終了2分後にスクショしたので少しズレてるかも。writer/testerの3から4人を引いてください。
前回の私の単独コンでB問題(Calculation of Exponentiation)を難しくしてしまった反省から前半は取り組みやすい問題を増やそうとしましたが、悪化しました。そんな……
A. Divide Points Fairly
・1問目には70-80人くらい解く★2想定の問題を置きたかったのですが
①見たことない設定でwriterもtesterも難易度想定をしにくい
②各問テスターをしていただいたp進大好きbotさんが乱択に強い人（過去に乱択想定をたくさん出題）
で難易度を過小評価してしまい簡単枠が消滅してしまいました……申し訳ない。
僕は直前まで★2を付けていました。((+_+))
・AtCoderであんまり乱択想定の問題あまり見ないよね、ってことでアルゴリズム知識不要な乱択を出題したかった。逆に競プロ経験や知識があまり役に立たなくて結果的に難しい問題になってしまった。
・タイトルはこの問題のオマージュ
・誤答傾向
① $(a,b) = (1,1), (1,2), (1,3), \cdots$ を全探索
② $(a,b) = (10^5,1), (10^5 - 1,1), (10^5 - 2,1), \cdots$ を全探索
などの決定解を投げた人は大体撃墜されてると思います。
・ $1$ 回の乱択あたりの成功確率がほぼ $1$ なので、つまり適当にデカめの傾きを投げれば通りはします。
・ChatGPTは解けませんでした。
B. Mex Recurrence Formula
・解けるのかなと思って作問したらN+1項でループに入って面白かったので出題。今回のセットの中では典型寄り。
（grundy数を求める気持ちになるといかにもループに入りそうな遷移なので、人によっては自明と感じるかも？）
・あまりサンプルを易しくしなかったけど、自然と実験に移行して周期を見つけて解けた人が多い模様。A問題に人を吸われていたにも関わらず通してくれた人が多くて嬉しい。感謝。
・mex典型(std::setやセグ木などでうまく管理して $O(log(N))$ でmexを取得するやつ)を知らなくても実は $O(N)$ で解けます。
・誤答傾向
① $A_i$ が $N$ より大きいときにバグってる
② ループ部分と非ループ部分の接続でバグってる
が多かったです。
・ChatGPTは正当な $O(N)$ 解法を提示してくれました。賢い。
C, D. Goodstuff Deck Builder(Easy, Hard)
・「クロノアーク」という神ゲーがあります。slay the spireと同じジャンルでデッキ構築ローグライクです。スレスパにハマった人なら絶対後悔させないからプレイしてみて！
ループ封じのため、カードをプレイする毎にそのキャラクターのカードのコストがそのターン中 $+1$ されます。この発想を競プロの問題に落とし込めないか考えていたら問題が生えました。
・Easyでは
①コスト降順が最適
②プレイできる枚数は実質10枚くらい
に気づく必要があるのですが、これ40人も気づけてるのすごい。
writerはHard制約 $O(NM)$ で解けることはわかっていたのですがEasy解を軸にした汚いプログラムしか思いつきませんでした。各問テスターのp進大好きbotさんが上手な言い換え「エネルギーを半分にすればよい」を思いついてくれたので出題しました。今見返してもやはり鮮やかですね。
・想定計算回数 $2\times 10^8$ なのevilじゃないか？ MLEが発生しがちなの不快じゃないか？
とかちょっと胃痛でしたが杞憂で済みました。
・誤答傾向はバラバラで $0$ コスの処理が甘い提出が少しあったくらい。
・Hardでうまくやるとハッシュマップ等で通ってしまうらしい(2件)
テストケースがザルかもしれん。
・ChatGPTはEasyの想定解法を返しました。Hardは解けませんでした。
E. Difference Sum Query
・一番ABCに出てきそうな見た目。というか作問過程でほぼ同値な問題ABC339-Gの存在に気づいてしまった。
パッと見で何をすればいいのか少し難しめなのでそこに新規性を見出していただければ嬉しい。あと問題文の見た目綺麗だよねということで許して。今回のセットの中では典型寄り。
・誤答傾向
制約はだいぶゆるゆるにしましたが重めのデータ構造はTLEしちゃうのが見受けられました。
緩めた結果 $N,Q$ の制約がいかにもMo's algorithmに誘導する形になってしまったのでそっちをトライしてTLEも数件。
・愚直はしっかり落としたつもりでしたが
クエリの幅がN/2以下なら愚直。N/2以上なら(全体)-(両端部分)。
をすると間に合ってしまいます。(1件)
そんな……
・ChatGPTはほぼ無思考でマージソートツリーを提案しました。高度な有名アルゴリズムに滅茶苦茶強いのよなちゃっぴーくん。
F. Unite Japanese Prefectures
・「辺をランダムに選んで色を塗り、色を塗った辺だけで全体が連結になるまでの操作回数の期待値は？」みたいなのをうまく改題してまともな問題にできないか考えていたところ、割と形になりました。
実は制約をいじっていたら $N=50$ あたりで丁度良さそうだっただけで、都道府県要素はあとから付け加えました。
・戦略が無数にあるので「最小全域木でいけるんじゃね？」という直感を信じるしかなさそう。理詰めで最適戦略に至るのは苦しそう。
・解説にはそれなりに説得力のある証明を書いたつもりなのですが、厳密に任意の戦略より強い戦略だと証明できていません。より厳密な証明募集。
・writer解は100msec以上かかっているのですがなんか13msecで通されて困惑
・ChatGPTはMSTを作ればいいという発想はあってるけどそれ以外は壊滅。
G. Colonies on Line
・DPをFPSで高速化 → ぼすたん☆もり
・これ $N \leq 2 \times 10^5$ とかでEasy出せばよかったとかなり後悔してます。
G単体で見たら母関数ガチャガチャしてひたすら頑張る問題になってしまう。僕も多分そうやって解きます。Easyを出して半強制的にDP書かせればよかった。
・ChatGPT壊滅。
H. Make Palindromic Multiple
・温泉に浸かりながら丸一日以上かけて思いついた解法なのですが、なぜコンテスト時間中に通せる人がいるのでしょうか。
・分量が多すぎてここまでたどり着けなかった人が多いと思いますが、かなり面白い問題に仕上がったと思うのでぜひ時間をかけて悩んでほしい。
・ざっくり「並べる方法（writer解）」と「内側をいじる方法（tester解）」があります。
僕は内側をいじる方法はちょっと無理そう、と思ったのですがhamamuさんが生やしてくれました。すごい。
・ChatGPT壊滅。
I. Make Palindromic Multiple(Judge)
・上の問題のJudgeを書いていたら意外と非自明で出題する価値あるなと思って出題。
・解説にも書きましたが法が知られている場合撃墜されます。
安全で爆速な～で有名な法 $2^{61} - 1$ は殺しました。
「ローリングハッシュ ライブラリ」と調べて1ページ目に出てくるものは全て殺しました。（除）
すぬけ先生のABCの解説動画のロリハも殺しました。
特定の法を殺す為だけに存在するケースが合計30個くらいあります。
ついでに位数が小さい基数(1500以下くらい)を取った場合も殺しました。
・two-pointer法はTLEするはず。工夫したり変なケースがないことを仮定すれば通るかも？
・コンテスト終了後も固定の法で通している輩がいれば容赦なくチャレンジを投げましょう( ｀ー´)ノ
・ChatGPTはロリハの級数和の方針を思いついてました。賢いね。