Hatena::Grouptopcoder

Hiro180の日記

 | 

2016-06-12最近解いた問題

SRM692 Div1 Med 23:48

<問題概要>

長さSの文字列が与えられる。(length(S)<=100)

以下の条件を満たす文字列は何通りあるか.

・non-intersectなSの個数の最大値はK個 (K<=10^9)

・長さはK*length(S)以上K*length(S)+N以下 (N<=1000)

・文字はすべて英小文字

<解法>

貪欲に取っていったときの出現箇所を考える。

1つ目の出現箇所までに無駄な部分がi文字になるような場合の数は、愚直なDPで計算できる。

一つ前の出現箇所から無駄な部分がi文字になるような場合の数も、愚直なDPで計算できる。

ここで、dp[i][j] = 2^i個文字列が出現するときに無駄な部分がj文字になるような場合の数

とすると、O(N*N*log K)くらいで計算できる。

最後の出現箇所から無駄な部分がi文字あるような場合の数も、愚直なDPで計算できる。

以上で求めた値を掛け合わせて足せば答が出る。

 |