tsubosaka https://blog.hatena.ne.jp/tsubosaka/ tsubosakaの日記 https://tsubosaka.hatenadiary.org/ TopCoder 250 大きさがn(A[j]となっているペアに対してのみ行う)。たとえば(1,4,3,2)で4と2を交換すると(1,2,3,4)となって一回で終了するが、3と2を交換した場合(1,4,2,3)で終了しない。このとき交換の回数の期待値を求めよという問題。 ここで配列Aに関して交換の回数の期待値をE(A)とおき、またAから一回の妥当な交換でいける配列の集合をN(A)とおくと、E(A)=1 + \sum_{B \in N(A)} E(B) / |N(A)|が成り立ち、また状態数は8!しかないのでメモ化再帰で解ける。 450 .とXからなる文字列が与えられる。列は端点で接触しているとする(円形になって… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftsubosaka.hatenadiary.org%2Fentry%2F20080524%2F1211654058" title="SRM402 - tsubosakaの日記" 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 2008-05-24 03:34:18 rich https://tsubosaka.hatenadiary.org/entry/20080524/1211654058 1.0 100%