GCJ2015 Round1C B.Typewriter Monkey

その他 過去問

問題

猿がK個のキー(同じ文字が存在するかもしれない)をS回押す。同じキーを何回も押すかもしれない。
押した順番に文字を並べた長さSの文字列ができあがるが、この中に、長さLの文字列Tが含まれる個数だけバナナを上げることにしている。
バナナは必要最低限の数だけ持っていくので、猿にバナナを渡した後手元に残っているバナナの数の期待値を求めよ。


T<=100
Small 1<=K<=7, 1<=L<=S<=7
Large 1<=K<=100, a<=L<=S<=100

考え方

small解

全探索する。


K個のキーで生成できる文字列をすべて生成し、Tが含まれる個数の合計と最大値を求めてあげれば、「(Tが含まれる個数の最大値) - (Tが含まれる個数の合計値)/(生成できる文字列の数)」で求まる。
KとSは高々7なので、7^7=823,543個しか文字列がないので全部生成しても時間的に問題ない。

large解

KとSが大きくなり100^100を列挙することはできないので、計算で出してあげることを考える。


求める必要があるのは、
①Tが含まれる個数の最大値
②Tが含まれる個数の合計値
③生成できる文字列の数
の3つ。


①は、Tを最大個含む長さSの文字列なので、Tのoverlapを考慮して何個含めることができるか計算できる。
例えば、S=5,T=ABAならば、

ABA
  ABA

とすることができるので、長さ+2するだけでTを1個追加できる。


②は、生成された文字列の1文字目からTがでているようなもの、2文字目からTがでているもの、・・・をそれぞれ考えればよい。

[文字列T][任意文字列]

のような場合、文字列Tを作ることができる組み合わせ数を求めればよく、任意文字列部分はK^(任意文字列の長さ)で求められるので、その2つを掛け合わせればよい。
次に文字列Tを右に1つずらした場合も求めたいが、これは上の計算と同じになる。
なので、最終的に、(文字列Tを作ることができる組み合わせ数 * K^(任意文字列の長さ))*(S+1-T)になる。


③は、K^S個。pow関数などで求められる。


これで、「① - ②/③」を求めれば答えが得られる。