yukicoder No.852 連続部分文字列

yukicoder.me
本番では解けず。dpっぽいなと思ったし実際dpで解けるようだけど、公式解説の4番めがわかりやすかったので、こういうのを自分でも思いつけるようになりたいと思ってメモを残すことにした。

問題概要

文字列の空でない連続な部分文字列における、文字の種類数の平均を求める。

制約

Sの長さは10^6以下

解法

まず、Sの全ての空でない連続な部分文字列（以下、単に部分文字列と呼ぶ）が、アルファベット全種を含んでいると仮定して総数を計算する。
これはSの長さをnとして、(アルファベットの種類の数)*(部分文字列の選び方) = 26*n*(n+1)/2　で求まる。
（部分文字列は長さ1のものがn個、長さ2のがn-1個、…長さnのが1個で1+2+...+n = n*(n+1)/2 個）

そして、各アルファベットについて、それを含まないものを計算して、求めた総数から引いていく。
例えば文字列がabcdaだったら、aを含まないものは、bcdから選べる1+2+3=6通り。
同様にしてaとaの間がk個あるならば、1+2+...+k = k*(k+1)/2個が、aを含まないものとして選べる。
これを全てのアルファベットについて計算していけば答えが求まる。

# yukicoder 852

A = "abcdefghijklmnopqrstuvwxyz"
S = input()
l = len(S)

def f(n):
    return (n*(n+1))//2

ans = 26*f(l)

for e in A:
    t = 0
    for k in range(l):
        if S[k] == e:
            ans -= f(k-t)
            t = k+1
    ans -= f(l-t)

print(ans/f(l))