水銀メモ_________φ

外部記憶装置として再開

CodeForces #289_Div2 : E. Pretty Song

CodeForces

問題

Problem - E - Codeforces

解法

与えられる文字列長をnと置く。
2重ループを回し全ての部分文字列を調べれば解が求まるが、nのとる値の範囲が
1<=n<=10^5と大きいため、 $O(n^2)$ では間に合わない。

考察すると、各文字は最終的な解に対し独立してスコアが決まる事が分かる。
例えば、文字列xxxAxx のAの独立したスコアは以下のようになる。
$(1/1 + 1/2 + 1/3)$ $+(1/2 + 1/3 + 1/4)$ $+(1/3+ 1/4 + 1/5)$ $+(1/4+ 1/5 + 1/6)$
この部分を効率良く求めたい。

これは $1/i$ の累積和Aと、さらにその累積和Bを事前に求めておくことで、
Bから $O(1)$ で計算する事ができる。
$A_n = \sum_{i=1}^{n} 1/i ,\;B_n = \sum_{i=1}^{n} A_i$

よって全体の計算量は $O(n)$ となる。

コード