AtCoder Grand Contest - C. Range Set (800)
結果
自力 AC
考察 60 分, 実装 30 分
解法
対称性より$ A \leq Bとしてよい.
操作を逆向きに考える.
最後に$ 1を並べたとき
$ 1が$ B個以上連続している箇所が存在する必要がある. 逆にこの条件を満たせばどのような文字列も作れる.
最後に$ 0を並べたとき
$ 1を並べる操作のうち, 最後に行われたものが$ k回目だとする.$ k回目が終わった時点で$ 1が$ B個以上連続している箇所が存在する必要がある. また, $ k回目以降は$ 0を並べる操作しかしていないのだから, これらの操作を行った部分に注目すると必ず$ 0が$ A個以上連続している.
よって, 次のことが文字列を作れることの必要十分条件である.
「操作後の文字列について, $ 0が$ A個以上連続している箇所を全て$ 1に置き換えたものを$ Tとすると, $ Tには$ 1が$ B個以上連続している箇所が存在する」
この条件を満たすものを生成するには, 次のようにする.
まず$ 11...1の塊と$ 00...0の塊を並べる. ただし, 長さ$ B以上の$ 1の塊が存在するようにし, $ 0の塊は全て長さが$ A未満であるようにする.
上のようにして作られた文字列の両端に$ 1を付け足す.
次に, $ 11...1の塊について, $ A以上連続している箇所を$ 0に変えることを任意の回数繰り返す. ただし, 塊の端は選ばない. ($ A = 2のとき$ 10111101を$ 10100101に置き換えるのは許されるが,$ 10001101に置き換えるのは許されない)
よって, 次のような DP を考えることによって解くことができる.
$ dp_{1, i} = 長さ$ iの$ 1の塊に対し, 先ほどのように$ 0に変えることを任意の回数繰り返す方法の総数
$ dp_{2, i} = $ 1の塊と長さ$ A未満の$ 0の塊を$ i番目まで並べて, まだ長さ$ B以上の$ 1の塊が存在していない場合の数
$ dp_{3, i} = $ 1の塊と長さ$ A未満の$ 0の塊を$ i番目まで並べて, すでに長さ$ B以上の$ 1の塊が存在している場合の数
各$ iについて, 次の塊をどこまで伸ばすかという遷移に$ O(N)かかるので, 全体での計算量は$ O(N^2)となる.