JunKobayashi https://blog.hatena.ne.jp/JunKobayashi/ JunKobayashi's Diary https://junkobayashi.hatenablog.com/ ABCのF問題 ABC本番で敗北した問題 有理数mod 期待値DP ＜問題のページ＞ ABC412 F - Socks 4 ※特に断らない限り、0-indexedで記載する。 ＜問題概要＞ \(0,1,\dotsc,N - 1\)と番号が付けられた\(N\)色の靴下があり、色が\(i\)番である靴下は\(A_i\)枚存在する。初期状態で、これらとは別に色が\(C\)番である靴下を1枚だけ持っており、終了条件を満たすまで以下の操作を繰り返す。 操作内容：タンスの中から1枚の靴下を一様ランダムに取り出し、手元の靴下と同じ色であれば終了する。異なる色であれば、手元の靴下2枚のうち1枚を任意に選択して手元に残し、もう一方をタンスの中に戻す。ただし、終了条件を満たすまで… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjunkobayashi.hatenablog.com%2Fentry%2F2025%2F07%2F01%2F013123" title="ABC412 F - Socks 4 - JunKobayashi&#39;s Diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2025-07-01 01:31:23 rich https://junkobayashi.hatenablog.com/entry/2025/07/01/013123 1.0 100%