riantkb/ttpc2019-k_circulation_editorial.md

## ttpc2019-k_circulation_editorial.md

      
    Raw
  

              ttpc2019-k_circulation_editorial.md
            
          
    以下では主に証明しかやっていないため、
先に https://img.atcoder.jp/ttpc2019/editorial.pdf を読むことをおすすめします。
        S(0), S(1), ... , S(x-2), S(x-1), S(x), ... , S(n-2), S(n-1)
S(x-1), S(0), S(1), ... , S(x-2), S(n-1), S(x), ... , S(n-2)
^^^^^^                            ^^^^^^                      ^^^^^^

を
S(0), S(1), ... , S(x-2), S(x-1), S(x), ... , S(n-2), S(n-1)
S(0), S(1), ... , S(x-2), S(n-1), S(x), ... , S(n-2), S(x-1)
                          ^^^^^^                      ^^^^^^

と見ると、これは swap(S[x-1], S[n-1]) になっています。
よって、
                    S(0), ... , S(n-1-k), S(n-k), ... , S(n-1)
T(0), ... , T(k-1), T(k), ... , T(n-1  )

を
S(0), ... , S(n-1-k), S(n-k), ... , S(n-1)
T(k), ... , T(n-1  ), T(0  ), ... , T(k-1)

と見ると、k 回の操作で S を T に一致させられるかどうかは、S を以下の操作で T[k:] + T[:k-1] に一致させられるかと同値です。
（以下では、T として T を k 回左ローテートしたものを考えます（つまり操作の結果 S[i] は T[i] にしたいです））
for (int i = n - 1; i >= n - k; --i) {
    int j; // i == j なる j を選ぶことも可能
    swap(S[i], S[j]);
}
S_l = S[0..n-1-k], S_r = S[n-k..n-1], S_l = T[0..n-1-k], S_r = T[n-k..n-1] とおきます。
このとき、ビット列 x と y のハミング距離を d(x, y) とおき、d(S_l, S_l) <= d(S_r, S_r) <-> k 回の操作で一致させられる を示します。
まず、ビット列 x, y に対して、(x[i] == 0) and (y[i] == 1) となるような i の個数を d_0(x, y)、(x[i] == 1) and (y[i] == 0) となるような i の個数を d_1(x, y) とおきます。
-> は簡単です。
なぜなら、d(S_l, S_l) <= d(S_r, S_r) のとき d_0(S_l, S_l) <= d_1(S_r, S_r) and d_1(S_l, S_l) <= d_0(S_r, S_r) が言え、S_l の中でビットが異なる各位置に対して S_r の中にペアが存在するため、swap の直接の対象となりえない S_l に対してもビットを合わせることが可能だからです。
（0の数（1の数）が等しいため d_0(S, T) == d_1(S, T) となるので、d(S_l, S_l) <= d_0(S, T) == d_1(S, T) <= d(S_r, S_r) が言え、ここから
d_0(S_l, S_l)
  = d(S_l, S_l) - d_1(S_l, S_l)
 <= d_1(S, T)   - d_1(S_l, S_l)
  = d_1(S_r, S_r)

が言えます（逆も同様））
<- も示します。
対偶を考えると d(S_l, S_l) > d(S_r, S_r) -> k 回の操作で一致させられない なので、これを示します。
dx を「これ以降 swap 操作の直接の対象にならない（上のコードの i が来ない）位置のハミング距離」、dy を「これ以降に swap 操作の直接の対象になる（上のコードの i が来る）位置のハミング距離」とします。
操作を行う前、dx = d(S_l, S_l), dy = d(S_r, S_r) です。
このとき、dx > dy のときどのように swap 操作をしても dx <= dy の状態にすることができないことを示します。
i 番目の要素を swap するときを考えます。

S[i] == T[i] のとき（対称性よりここでは S[i] = 0 とします）、

swap しない、または S[j] == 0 なる j と swap

dx も dy も変化しないため dx > dy のまま


dx の位置にある S[j] == 1, T[j] == 1 なる j と swap

dx += +1 + +1, dy += -0 より dx > dy


dx の位置にある S[j] == 1, T[j] == 0 なる j と swap

dx += +1 + -1, dy += -0 より dx > dy


dy の位置にある S[j] == 1, T[j] == 1 なる j と swap

dx += +1, dy += -0 + +1 より dx > dy


dy の位置にある S[j] == 1, T[j] == 0 なる j と swap

dx += +1, dy += -0 + -1 より dx > dy


S[i] != T[i] のとき（対称性よりここでは S[i] = 0 とします）、

swap しない、または S[j] == 0 なる j と swap

dx += +1, dy += -1 より dx > dy


dx の位置にある S[j] == 1, T[j] == 1 なる j と swap

dx += +0 + +1, dy += -1 より dx > dy


dx の位置にある S[j] == 1, T[j] == 0 なる j と swap

dx += +0 + -1, dy += -1 より dx > dy


dy の位置にある S[j] == 1, T[j] == 1 なる j と swap

dx += +0, dy += -1 + +1 より dx > dy


dy の位置にある S[j] == 1, T[j] == 0 なる j と swap

dx += +0, dy += -1 + -1 より dx > dy


よって示されました。
ところで、一致させるためには少なくとも dx == 0 となることが必要です。
しかし、どのように操作しても dx > dy >= 0 の状態から抜け出せないため、dx == 0 にはなれません。
よって、<- も示され、必要十分条件であることが示されました。