ARC223 E - Yin-Yang Two Bits Insertion

考え方

まず、最初の文字が一致しているかどうかチェックする。
異なればこの時点で "No" で問題終了。
これをやっておくことで、以降は「$0$ か $1$ か」を「前の数と同じか」で扱ってもよいことになる。

その上で、問題を考えやすくする。

まず、両数列に対し、$1$ つおきに $0/1$ 反転する。
これにより、操作は $x, y$ のところに $x, x, y, y$ というように値を挿入する話になる。
すると、値の挿入はランレングス圧縮の各ブロックの要素数を増やしていく話になる。
具体的には、以下ができる話になる。

• A 加工後の隣り合う2つのブロックに、両方 $+1$ する
• A 加工後の長さ $2$ 以上のブロックに、$+2$ する

この操作はどちらも、ランレングス圧縮のブロック数が増減しない。
つまり、ブロック数が異なれば、この時点で "No" で問題終了。

さて、隣り合う2つのブロックに、両方 $+1$ するのは、同じ境界線に対して何度でもできる。
しかし、実は $3$ 回以上やることは考えなくてよい。
というのは、左右に両方 $+1$ した時点で双方 $2$ 以上の数になっているから。
左右 $+1$ を $3$ 回やる代わりに、左右 $+1$ を $1$ 回やってからそれぞれ別個に $+2$ すればよい。
あるいは、$+2$ 操作の回数を左右で変えれば、左は $+2$ で右は $+6$ といったことも可能である。

ということで、各境界線は、以下の $3$ 択から選べばよい。

• 左右を一切増やさない
• 左右を奇数個ずつ増設する
• 左右を $2$ 以上の偶数個ずつ増設する

先頭と末尾も左右を一切増やせない境界線とみなすことにする。
すると、各境界線について、そこを指定の種類としてそこまでを作れるか動的計画法で調べられる。

遷移は、前の境界線との間の B 側の値が A 側の値よりどのくらい大きいか調べる。

• 小さい場合、全ての組が不可。
• 等しい場合、両者左右を一切増やさない組み合わせのみ可。
• $1$ 以上の奇数だけ大きい場合、片方だけ奇数増設のパターンが全て可、その他は不可。

- ただし、奇数増設と偶数増設の組は差が $3$ 以上のときだけ可。

• $2$ 以上の偶数だけ大きい場合、両方奇数増設かどちらもそうではないパターンが可、その他は不可。

- ただし、偶数増設同士の組は差が $4$ 以上のときだけ可。
- また、増設なし同士の組は A 側が $2$ 以上のときだけ可。

最初は「増設なし」のみ可から出発して、最後に「増設なし」が可になっていれば、"Yes" である。

入力例1での動作

$1$ つ目のテストケースのみ考える。

入力を受け取る。

n: 3
m: 7
a: {0, 1, 1}
b: {0, 1, 0, 1, 1, 0, 1}

先頭はどちらも 0 なので、処理を続ける。

a と b それぞれについて、$1$ つ飛ばしで 0 と 1 を反転する。

a: {0, 0, 1}
b: {0, 0, 0, 0, 1, 1, 1}

これをランレングス圧縮し、長さだけを取り出す。

a_vec: {2, 1}
b_vec: {4, 3}

a_vec と b_vec の要素数はどちらも $2$ なので、処理を続ける。

DP テーブルの意味は、以下のようにする。

• dp[i][0]: $i$ 番目までを、増設なしの状態で作れるか
• dp[i][1]: $i$ 番目までを、両側奇数増設の状態で作れるか
• dp[i][2]: $i$ 番目までを、両側偶数増設の状態で作れるか

初期状態は以下である。

dp[0]: {true, false, false}

まず、$i=0$ を見る。
a_vec[0]=2、b_vec[0]=4 である。
差は $2$ なので、$2$ 以上の偶数である。
処理後、以下のようになる。

dp[1]: {true, false, true}

次に、$i=1$ を見る。
a_vec[1]=1、b_vec[1]=3 である。
差は $2$ なので、$2$ 以上の偶数である。
処理後、以下のようになる。

dp[2]: {true, false, true}

最後に dp[2][0] を見る。
dp[2][0] は true なので、答えは Yes である。

注意点

特になし。

別解

特になし。