yukicoder contest 218 B - 連続部分文字列 - 情報妖精の競プロ日記

B問題の解説です。

問題

問題文(要約)

問題文

文字列 $S$ が与えられます。
$S$ の空でない連続な部分文字列における、文字の種類数の平均を求めてください。
絶対誤差は $10^{-5}$ まで許容されます。

制約

$1≤|S|≤10^6$
$S$ はアルファベット小文字のみで構成される

典型問題ですね！
連続な部分文字列と言われているので、まずは左から決め打っていくDPを考えましょう！
また、連続な部分文字列の個数が $\frac{|S|(|S|+1)}{2}$ 個あるのは自明なので、平均ではなく総和で考えて最後に割ることにしましょう！

さて、左から考えるときに必要な情報はなんでしょうか？
やはり、ある文字 $S_i$ まで見た時に、 $S_i$ を右端とする連続部分文字列の文字の種類数の総和が求められると楽そうです。
まず、 $S_i$ を右端とする連続部分文字列は明らかに $S_{i-1}$ を右端とする連続部分文字列(と空文字列)の右に $S_i$ をくっつけたものなので、直前の計算結果を利用できそうです。
直前の部分文字列と比べて、答えがどのくらい増えるか考えてみましょう。
すると、下の図のように増えることが分かります。
f:id:CuriousFairy315:20190726222337p:plain
つまり、1個前の同じ文字との距離だけ増えた値が入ることが分かりますね。
これが分かれば後はそのまま実装するだけで答えが分かりますね。

感想

ei1333という答えになる問題が作りたくて作りました。
1.333=4/3なので、なんかそれっぽいのにならないかなーって思ったら思いついた問題です。
正直まぁやるだけなので、個人的には★2だと思っていました。★2.5らしいですね、難易度分からない
ちなみに当初は絶対誤差を $10^{-3}$ まで許容していましたが、テスターに乱択を通されてどうやっても落ちなさそうだったので変えました。
流石にマラソン解法が通るのは……うん……。