AtCoder Beginner Contest 126 F XOR Matching - kamojirobrothersのブログ

AtCoder Beginner Contest 126 で苦手な構築系がでたけど、解けたので記念に記事にしておく。
実験が初めてうまくいったので。

解説

実験する。
次のようなコードを書いた。

実験プログラム

from itertools import permutations
M = int( input())
for m in range(M):
V = [i for i in range(2**m)]
V = V+V
for k in range(2**M):
check = True
for P in permutations(V):
check = True
C = [-1]*(2**m)
A = [0]*(2**(m+1))
A[0] = P[0]
C[P[0]] = P[0]
for i in range(1, 2**(m+1)):
A[i] = A[i-1]^P[i]
if C[P[i]] == -1:
C[P[i]] = A[i]
else:
if A[i]^C[P[i]]^P[i] == k:
C[P[i]] = -2
continue
check = False
break
if check == True:
# print(P,A,C)
break
if check == True:
print(m,k,P)

$N = 3$ くらいまでが限界。
次みたいな結果が出る。

0 0 (0, 0)
1 0 (0, 1, 1, 0)
2 0 (0, 1, 2, 3, 0, 3, 2, 1)
2 1 (0, 1, 2, 3, 1, 0, 3, 2)
2 2 (0, 1, 2, 1, 0, 3, 2, 3)
2 3 (0, 1, 2, 3, 2, 1, 0, 3)
3 0 (0, 1, 2, 3, 4, 5, 6, 7, 0, 3, 2, 1, 7, 6, 5, 4)
3 1 (0, 1, 2, 3, 4, 5, 6, 7, 1, 0, 3, 2, 5, 4, 7, 6)
3 2 (0, 1, 2, 3, 4, 5, 7, 4, 6, 7, 1, 0, 3, 2, 5, 6)
3 3 (0, 1, 2, 3, 4, 5, 6, 7, 2, 1, 0, 7, 6, 5, 4, 3)
3 4 (0, 1, 2, 3, 4, 5, 6, 7, 4, 0, 3, 2, 1, 7, 6, 5)
3 5 (0, 1, 2, 3, 4, 5, 7, 2, 1, 6, 7, 5, 4, 0, 3, 6)
3 6 (0, 1, 2, 3, 4, 5, 6, 1, 7, 6, 5, 4, 0, 3, 2, 7)
3 7 (0, 1, 2, 3, 4, 5, 6, 7, 6, 1, 0, 3, 2, 5, 4, 7)

$M=0$ は例外で、それ以外は、 $0$ から $2^M-1$ までの好きな値にできる気がする。
$M=2$ の場合を見ると、構成の仕方が分かった。

解答

M, K = map( int, input().split())
ANS = []
ans = 0
if M == 0:
    if  K == 0:
        ans = 0
        ANS = [0,0]
    else:
        ans = -1
elif M == 1:
    if  K == 0:
        ans = 0
        ANS = [0,0,1,1]
    else:
        ans = -1
elif M >= 2:
    if K >= 2**M:
        ans = -1
if M >= 2 and ans == 0:
    ANS = list( range(K+1)) + list( range(K))[::-1] + list( range(K,2**M))[::-1] + list(range(K+1,2**M))
if ans == -1:
    print(ans)
else:
    print(" ".join( map( str, ANS)))