B - Adjacent Replace Editorial
by
toam
数列は 0-indexed とします.
まず,\(A=(2^0,2^1,2^2,\ldots,2^{N-1})\) のときに作れる数を考えます.明らかに \(2^N\) 未満です.
実は,\(2^N\) 未満の非負整数のうち \(2^0\oplus 2^2\oplus 2^4\oplus\ldots\) と \(2^1\oplus 2^3\oplus 2^5\oplus\ldots\) 以外の数を作ることができます.
(証明)
作る数 \(K\) を \(2\) 進数で表した長さ \(N\) の 01 列を \(s\) とします(\(K=\sum_{i=0}^{N-1} s_i2^i\)).
[1] \(s_i=s_{i+1}=0\) となる \(i\) が存在するとき
最初に \(i\) で \(2\) 回操作することで \(A_i=A_{i+1}=0\) とします.まず,\(i\) より左側にあって \(s_j=1\) となるようなものをすべて \(i+1\) に集めることを目指します.すなわち,\(A_{i+1}=\sum_{j=0}^{i-1}s_j2^j\) となるように操作します.これは \(j\) の降順に見ていったとき,以下のように操作すればよいです.
- \(s_j=0\) ならなにもしない.
- \(s_j=1\) なら \(A_{j+1},A_{j+2},\ldots,A_i\) がすべて \(0\) になるように \(j+1,j+1,j+2,j+2,\ldots,i-1,i-1\) と操作したうえで,\(j,j+1,\ldots,i\) と操作することで \(A_{i+1}\leftarrow A_{i+1}\oplus A_j(=A_{i+1}\oplus 2^j)\) とする.
同様のことを \(i+1\) の右側に対しても行います.まず,作った \(A_{i+1}\) を適当な操作によって \(A_0\) に移動します.その後,上と同じことをすることで \(i+1\) の右側にあるものをすべて \(A_0\) に移動することができます.これで \(A_0=K\) とすることができました.
[2] \(s_i=s_{i+1}=1\) となる \(i\) が存在するとき
\(s_{i+2}=1\) のとき
\(i,i+1\) と操作することで \(A_{i+2}\leftarrow A_i\oplus A_{i+1}\oplus A_{i+2}\) とすることができ,\(s_i=s_{i+1}=0\) に帰着します.\(s_{i+2}=0\) のとき
\(i\) と操作することで \(A_{i}\leftarrow A_i\oplus A_{i+1}\) とすることができ,\(s_{i+1}=s_{i+2}=0\) に帰着します.
(\(i+2=N\) のときは,\(i-1,i,i+1\) に対して同様のことをします.)
[3] 上記以外のとき
\(s\) は 010101... または 101010... のいずれかです.初手でどのように操作を行っても \(K\) に含まれる bit と含まれない bit が常に共存することになるので不可能です.
以上より,\(A=(2^0,2^1,2^2,\ldots,2^{N-1})\) の場合が解けました.操作回数は \(O(N^2)\) 回であり,操作回数上限に余裕をもって操作できます.
\(A\) が一般の場合,次の集合 \(S\subset \lbrace0,1,\ldots,N-1\rbrace\) が存在するか分かればよいです.
- \(\displaystyle\bigoplus_{i\in S}A_i=K\)
- \(S\neq \lbrace 0,2,4,\ldots\rbrace\wedge S\neq \lbrace 1,3,5,\ldots\rbrace\)
\(2\) つ目の条件が無かった場合は,このような \(S\) は掃き出し法で求められます.
\(2\) つ目の条件を考慮する場合の求め方について,例えば以下の \(2\) 通りがあります.
- \(j\in S\land j+1\in S\) または \(j\notin S\land j+1\notin S\) を満たすような \(j\) が必ず存在するため,そのような \(j\) をすべて決め打って調べればよいです.計算量は \(O(N^2\log(\max A))\) です.
- まず \(2\) つ目の条件を一旦無視して,XOR が \(K\) になる \(S'\) を一つ見つけます.これが \(2\) つ目の条件を満たせばそれで ok です.そうでないとき,解空間のベクトルを選んで \(S'\) との XOR を取ることを高々 \(2\) 個試せば \(2\) つ目の条件を満たす \(S\) が見つけられます.計算量は \(O(N\log(\max A))\) です.
def find(N, K, A):
no_base = [0]
base = []
def calc(v):
bit = 0
for x, y in base:
if v ^ x < v:
v ^= x
bit ^= y
return (v, bit)
for i in range(N):
v, bit = calc(A[i])
if v > 0:
base.append((v, bit ^ (1 << i)))
else:
no_base.append(bit ^ (1 << i))
v, bit1 = calc(K)
if v != 0:
return []
ng0, ng1 = sum(1 << i for i in range(0, N, 2)), sum(1 << i for i in range(1, N, 2))
for bit2 in no_base:
bit = bit1 ^ bit2
if bit not in [ng0, ng1]:
return [(bit >> i) & 1 for i in range(N)]
return []
def solve():
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = find(N, K, A)
if len(S) == 0:
return print("No")
p = -1
for i in range(N - 2, -1, -1):
if S[i] == S[i + 1]:
p = i
if S[p] == S[p + 1] == 0:
op = [p, p]
else:
if p != N - 2:
if S[p + 2] == 1:
op = [p, p + 1, p, p]
else:
op = [p, p + 1, p + 1]
p += 1
else:
op = [p, p - 1, p - 1]
p -= 1
for i in range(p - 1, -1, -1):
if S[i]:
for j in range(i + 1, p):
op += [j, j, j - 1]
op += [p - 1, p]
for i in range(p - 1, -1, -1):
op += [i, i, i + 1, i]
for i in range(p + 2, N):
if S[i]:
for j in range(i - 2, 0, -1):
op += [j, j, j + 1]
op += [1, 0]
print("Yes")
print(len(op))
print(*[i + 1 for i in op])
T = int(input())
for _ in range(T):
solve()
posted:
last update:
