inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ https://atcoder.jp/contests/abc360/tasks/abc360_e例えばN=3で考えると、1から2に移動する確率は2/9で、1から1に移動する確率は1-2/9*2=5/9です。一般には、ある位置から他に移動する確率は、で、同じところにとどまる確率はとなります。なので、1回での状態遷移行列は、 と書けます。ここで、Aは全ての要素が1の行列、Iは単位行列、、です。K回の状態遷移確率はです。また、Tが与えられたときの期待値Eは、となります。 ですが、だから、を考慮すると、 ここで、aN+b=1だから、 また、、だから、結局、 となります。 // Random Swap… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F2024%2F07%2F02%2F214403" title="AtCoder Beginner Contest 360 E - inamori’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 2024-07-02 21:44:03 rich https://inamori.hateblo.jp/entry/2024/07/02/214403 1.0 100%