SRM402

250

大きさがn(<=8)の配列Aが与えられた時に、ランダムに2つ数を選んで交換することを繰り返してソートすることを考える(このため数の交換はiA[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からなる文字列が与えられる。列は端点で接触しているとする(円形になっている)。いま.の連続している部分をギャップと呼び、Xの連続している部分をブロックと呼ぶ。一つのブロックを取り除くことを許した時に最大のギャップ(最大となる場合が複数あるならば再帰的に比較する)を与えるようなブロックのインデックスを出力しなさいという問題。
文字列の長さは高々2500なので実際にブロックを一個ずつ削除して試せばいいのだが、ブロックのインデックスのルールを勘違いしていてシステムテストで落ちた。

1000

今"3235236"のような数が与えられた時に{"32" , "35" , "236"}のように単調に増加する列に分解することにする。このとき分割の仕方が複数ある場合は最後の値が最小になるようにする。最後の値も同じ分け方が複数ある場合は1番初めのものが最大となるもの、それも同じならば2番目のもの...を返す。(正確には分割した数の積を返す)
DPで解けるらしい。