Long Common Subsequence(AGC052)

問題

A - Long Common Subsequence

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

解けず。解説を読んで再考

まず、「$2N+1$の$01$文字列であって$S_1+S_1$、$S_2+S_2$、$S_3+S_3$いずれの部分列であるもの」は「$S_1+S_1$、$S_2+S_2$、$S_3+S_3$のそれぞれの文字の前の方から$2N+1$個の文字を選びとる」ことで作ることができる。
例えば「$2N$個の文字を選び取る」問題だとすると、0がN個と1がN個にすれば良い。
なぜなら、前半部分の$S_i$には0がN個含まれており、後半部分の$S_i$には1がN個含まれているからである。
つまり、ある範囲に0がN個含まれていて、ある範囲に1がN個含まれているかわかれば、$”0″*N+”1″*N$が答えになる。

この状況を$2N+1$に当てはめてみると、ある範囲に0がいくつ含まれていて、ある範囲に1がいくつ含まれていれば分かれば答えることができそう。
$2N$の時と同じように重要になるのは$S_i$の中には、0と1がN個ずつ含まれているということ。
これをもう少し深く考えてみる。
例えば前半の$S_i$の2文字目から後半の$S_i$の2文字目までを考えてみると、これも0と1がN個ずつ含まれている。
2文字目が3文字目でも同じこと。
ある場所から$2N$の範囲には0と1がN個ずつ含まれている。
一番初めの0から$2N$の範囲にも1がN個ずつ含まれている。
一番初めの0から$2N$の範囲には0がN個ずつ含まれているので、ここまでの0の数はN個のはず。
よって、一番初めの0から$2N$の範囲の後ろにある0の数もN個になる。
なので、$0+”1″*N+”0″*N$が答えになる。