日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 412）

　Eまで五完。

　久しぶりのRatedなABCだったが、レートを落とした。

　30分あってFが解けなかったのは問題だけど、Eでミラーラビンを使う方法しか思いつかなかった方が罪は大きいかも。

コンテストへのリンク

コンテスト後のツイート

日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 412） Eまで。
C ソートして尺取り
D 再帰全探索を頑張る。
E 素数と素数のベキ。ミラーラビンを使わない方法が分からず、ChatGPTにC++に翻訳してもらってAC。
F Aが大きい順に決めようとしたが、答えが合わぬまま終了。

— titia (@titia_til) June 28, 2025

E - LCM Sequence

　ミラーラビンを使わずにACした。

　Rの最大値が10^14であることに着目すれば、10^7までの素数を列挙し、エラトステネスの篩のようなことを行うことで、区間[L, R]での素数を見つけることができる。

　ミラーラビンを使わずに解けるんじゃないの？　とは思ったし、Rの最大値に着目した時間もあったはずなのに、どうして思いつかなかったんだろう。これをさっと通せていたらFも解けていた気がするなぁ。

F - Socks 4

　自力AC。

　ソックスの個数が多いものが出たらそっちへ移動する方がいいのは明らかで、あとはいつもの期待値DPの式を立てるだけ。

　結構すんなり立式でき、Sample1の値があったから実装し始めたのだけど、結局間に合わなかった。

　もっと一般的な形で立式していれば実装で詰まらなかっただろう……とはいえるけど、Sample１と一般の形でそれほど違いはないので、残り時間を考えればここで実装を始めたのは悪くなかったはず。

　なので、ここをこうすれば良かったという点はあまりなくて、期待値DPの立式や実装が遅かったことを敗因として良さそう。

　Fに時間を残せなかったのが不味かった。