きままにものづくり

日々の気付いたことなんかを書いてます。

SRM654Div1Easy

問題

サイズNの配列が与えられる。各要素は小文字のアルファベット(a-z)か?である。?は小文字のアルファベットに変更することができ、各アルファベットへの変換確率はpで与えられる。
全ての要素が同じ部分配列の数がその配列のスコアとする。与えられた配列のスコアの期待値を求めよ。

解法

?を含む部分配列を全列挙し、各部分配列のスコアを数え上げることで答えが求まる。毎回部分配列の分布を計算すると O(N^3 log N)になる。最初と最後の要素以外の変更はないので、使い回すことができる。このことを利用すれば O(N^2 log N)に削減できる。

計算量

 O(N^2 log N)
 log(N)は指数計算

コード

広告を非表示にする