Let's Play the Words? - #606 div2 d

#ふつうの文字列

解法

1.
0...1, 1...0の文字列の数の差が1以下
多い方から始めて交代交代にすればいい

0...1, 1...1, 1...0
のように間に1...1や0...0を挟むことも考えられるが
これは後で挿入するとしたらよい

後で挿入できないのは
0...1, 1...0が1つもなくて, 0...0, 1...1が両方あるとき
渡れない

2.
0...1, 1...0の文字列の数の差が1より大きい
1以下にできる

0...1の文字列の数をk, 1...0の文字列の数をlとする
k - l > 1としても一般性を失わない
0...1で, k - l文字は反転しても1...0の文字列に被らない
ただし, 制約より同じ文字は入力にない

(k + l) / 2 + 1文字まで0...1を減らす
k - {(k + l) / 2 + 1}
= (k - l) / 2 + 1

減らす文字数が(k - l)以下ならいい
(k - l) - {(k - l) / 2 + 1}
= (k - l - 2) / 2
≥ 0(k - l > 1より)