問題概要
長さ の文字列に対して、
文字選んで 0 にする、
文字選んで 1 にするという操作を好きなだけ行って生成できる文字列の個数を求めよ。
考察
10秒くらい考えると、 文字選ぶ、というのは
文字以上選ぶ、というふうに言い換えられる。
でも同様である。
また、
としても一般性を失わない。
ここで、「もしかして必要十分条件は 文字連続した 0, または
文字連続した 1 があることではないか？」と思うので、プログラムを書いて調べてみる。
テストケース 2 で少し答えより多いので、目視して調べると「
文字未満の 1 の連続している場所と両端について、どこか間に
文字以上の間隔がある場所が存在する」という条件が加わる。
これをDPして調べたいが、結局コンテスト中にはできなかった。
「 文字以上連続する 1 をすべて 0 に置き換えたとき、
文字以上 0 が連続している場所がある」と言い換えると多少見通しがよくなる。（文字列を頭の中でイメージすればそんなに変わらないが）
まず、 を、
文字目までで 0 が連続している長さが
の通り数、と定義してみる。
重複を避けるために、
となったら即座に答えに加えて遷移しない、また、1 の
連続についてはまとめて加える、という方針でやるが、これではうまくいかない。
理由は、1 を順番に加えても 連続になってしまうことがあり、重複が生まれるからである。
ここで、
: このあと 1 にしてよいか というパラメータを作り、1 を
個以上
個未満加えるパートを、累積和を利用した貰うDPにする。
ただ、これだとこのあと 1 を加えるとき、 に加えずに進んでしまい、またDPがバグる。そこで、
:
を前提として、このあと 1 を使うとき
を加算してよいか というパラメータも加える。これでDPができる。
感想
コンテスト中に必要十分条件への言い換えまではできていたので悔しい。penguinmanさんに負けたのがめちゃくちゃ悔しい
