yukicoder #562: 超高速一人かるた small

p(T)を

読み上げられたカードの集合がTであるときのパターン数とする。

p(Φ) = 1

p(T(!=Φ)) = Σ[i ∊ T] ( p(T-{i}) )

で簡単に求まる。

e(T)を読み上げられたカードの集合がTであるときの

期待値 と パターン数の積とする。

E[K] * P[N,K] = Σ[T⊆読み札, |T|=K](e(T))

が成り立つ。

これらは、すべてのパターンについて、読み上げられた文字の数の和をとったもの。

なので、

e(T)

= Σ[j∊T](e[T-{j}] + p[T-{j}] * (T-{j}の後でjの読み札を見たときの読み上げる文字数)

で求まる。

T-{j}の次がjとして、そのとき読み上げられた文字数を求めるには、事前に

f[i][j] = iをjと区別するのに必要な最低の読み上げ文字数

を計算しておけば楽。これは愚直に求められる。

 

L = max(|S[i]|)として

事前計算でO(LN^2), DPの計算にO(2^N * N^2)の時間で間に合う。