GCJ 2013 R1C A.Consonants

問題

アルファベットの文字列Sと整数nが与えられる。
長さLは、0

考え方

dp的に考える。

文字列の0〜iまでの、求めたい個数をdp[i]とする。この値を求めたい。
dp[i-1]がすでに計算されているとして、今考えなければいけない文字列は、
部分文字列0〜i、1〜i、、、、i〜iになる。
この中にn以上子音が連続するものがいくつ含まれるか考えればよい。

例として、子音x、任意文字oとして、n=2とすると、
oooooooxxxoooを考えると、

oooooooxxxooo
 ooooooxxxooo
  ...
        xxooo

が含まれる個数になる。
複数の子音列が含まれる場合でも、一番最後の子音列のところまで数えればいいことは明らか。

最終的に、
dp[i] = dp[i-1] + (一番最後にでた子音列の中でn個になるインデクス+1)
が答え。

考え方2

子音をx、任意の文字をoとし、
oxxo
のようになっているとすると、このxxに注目したとき、n=1ならば、

ox
oxx
oxxo
 x
 xx
 xxo
  x
  xo

が考えられる。
まず「o|xxo」のように区切り位置を考えて、前半部分の組み合わせ数、後半部分の組み合わせ数が出せる。
次に「x|o」のように子音列の最後に区切り位置を持つ場合を考えて組み合わせ数を計算する。(xx|oだと↑でカウントしているので重複するのに注意)
最後に、子音内部だけの部分文字列を考えて、組み合わせ数を計算する。これは、N個連続しているものからn個以上連続しているものの個数なので、長さnはN-(n-1)個、長さn+1はN-n、、、、とｎなり、1+2+3+...+(N-(n-1))なので、公式で求まる。

これらを合計したものが1つの長さがn以上の子音列を持つ場合の答えになる。

次に「oxxoooxxo」のような場合を考える。
前半のxxは上記と同様に計算できるが、後半のxxの時に、前半と重複してカウントしてしまう。
そこで、後半のxxで、その前半部分を考える時に、重複しないようにスタート位置をずらした「oooxxo」で考える。この文字列で1つの時と同様にカウントすればよい。

上記はO(N)で計算していけるので、間に合う。