Problem p03097 (python)

Fixed submission:

"""
ハミング距離がちょうど1
絶対不可能なのは、AとBの1の数の偶奇が違うとき
それ以外は可能か？

可能と仮定して構成法を考えてみる
ハミング距離を1だけ変化させる方法
→2**xを xorする

AとBが1桁だけ違う場合は可能、それ以外は不可能？
→1回だけ選ぶ桁は1つしかないのでおｋそう

根本的に違う？
→最初と最後のハミング距離が1以外も可能？
→いやー無理やろ

N=1 → 必ずハミング1になる
N=2 → 必ずハミング1になる
N=3 →

ある桁にxorするのを考える
1,0良い感じに分配→2個セットで分配してく
1個小さいの奴より2倍以上になってはダメ

差が2以下になるように分配可能
→分配したらどう取るか分かれば解ける

残り数が最大に奴から見ていく→未出ならやっちゃえばいい
たぶん行ける…たぶん…

→むりだった()

========ちょっとだけ解説を見た==========
ハミング距離が偶数なら無理、奇数なら可能

証明しよう
N = 1,2 の時　全列挙で自明
N >= 3のとき、そのN-1以下で全て成立すると仮定すると

0(0*(N-1))→0(ハミング奇数ALL)→1(ハミング奇数ALL)→1(ハミング偶数ALL)
となるので、ハミング奇数の奴をすべて構成できる(1の位置を途中に入れればすべて可能)

この考え方をどうやって構成に応用する？
→再帰っぽい
→またはdp?

小さい桁から合わせていく？

=========解説を見ました=============

再帰かぁ
やることは→始点と終点で違うbitを見つける
→そこで分割→始点未確定から1bitずらしたやつを前半終点・後半始点に据えて問題を2分割
必要なのは？→確定したbitを保持する変数
"""
import sys
d2lis = {}
for i in range(20):
    d2lis[2**i] = i

def f(start,goal,usedbit):

    #異なるbitかつ未使用を見つけよう
    nuse = 0
    for i in range(N):
        if ( ( (2**i) & usedbit == 0) and (start&(2**i) != goal&(2**i)) ):
            usedbit |= 2**i
            nuse = 2**i
            break

    #もう一つ未使用bitを見つけよう→見つからなかった時の処理も書く

    flag = False
    for i in range(N):
        if ((2**i) & usedbit == 0):
            flag = True
            mids = start ^ (2**i)
            midg = mids  ^ nuse
            break

    if not flag:
        return [start,goal]
    else:
        ret = f(start,mids,usedbit) + f(midg,goal,usedbit)
        return ret #答えのリスト

N,A,B = map(int,input().split())

#print (format(A,"b").zfill(N))
#print (format(B,"b").zfill(N))

numbit = 0
for i in range(N):
    if ((A^B) & (2**i)) > 0:
        numbit += 1
if numbit % 2 == 0:
    print ("NO")
    sys.exit()

ans = f(A,B,0)

if len(ans) != 2**N:
    print ("NO")
    sys.exit()
for i in range(2**N-1):
    if abs(ans[i+1]-ans[i]) not in d2lis:
        print ("NO")
        sys.exit()

print ("YES")
print (" ".join(map(str,ans)))




#WA解答2 貪欲で構成しようとしてみてだめだった
"""
import sys

N,A,B = map(int,input().split())

lis = [[0,i] for i in range(N)]
able = [True] * (2**N)
rem = 2**N-1

for i in range(N):
    if (A^B) & (2**i) > 0:
        lis[i][0] += 1
        rem -= 1

if rem % 2 == 1:
    print ("NO")
    sys.exit()

lis.sort()

for i in range(rem//2):
    lis[i % N][0] += 2

ans = []
#print (lis)
able[B] = False

for loop in range(2**N-1):

    if loop == 0:
        pass
    else:
        lis.sort()
        for i in range(N-1,-1,-1):
            if able[A ^ (2 ** lis[i][1])]:
                lis[i][0] -= 1
                if lis[i][0] < 0:
                    print ("NO")
                    sys.exit()
                A ^= 2 ** lis[i][1]
                break
        
    ans.append(A)
    able[A] = False

ans.append(B)
print ("YES")
print (" ".join(map(str,ans)))
"""

#WA解答1(そもそもハミングが1以外無理だと思ってた時)
"""
import sys

def want_min(x):

    for i in range(20):
        if (2**i)&x > 0:
            return i

d2lis = {}

for i in range(20):
    d2lis[2**i] = i

N,A,B = map(int,input().split())


if A^B not in d2lis:
    print ("NO")
    sys.exit()

print ("YES")

upk = d2lis[A^B]
ans = []

for i in range(2**N):

    if i == 0:
        ans.append(A)
    elif i == 2 ** (N-1):
        A ^= 2 ** upk
        ans.append(A)
    else:
        keta = want_min(i)
        if keta >= upk:
            keta += 1
        A ^= 2**keta
        ans.append(A)

    #print (format(A,"b").zfill(N))

#print (ans[-1])
print (" ".join(map(str,ans)))

"""

Buggy submission (verdict: Runtime Error):

"""
ハミング距離がちょうど1
絶対不可能なのは、AとBの1の数の偶奇が違うとき
それ以外は可能か？

可能と仮定して構成法を考えてみる
ハミング距離を1だけ変化させる方法
→2**xを xorする

AとBが1桁だけ違う場合は可能、それ以外は不可能？
→1回だけ選ぶ桁は1つしかないのでおｋそう

根本的に違う？
→最初と最後のハミング距離が1以外も可能？
→いやー無理やろ
"""
import sys

def want_min(x):

    for i in range(20):
        if (2**i)&x > 0:
            return i

d2lis = {}

for i in range(20):
    d2lis[2**i] = i

N,A,B = map(int,input().split())

if N >= 6:
    print (X)

if A^B not in d2lis:
    print ("NO")
    sys.exit()

print ("YES")

upk = d2lis[A^B]
ans = []

for i in range(2**N):

    if i == 0:
        ans.append(A)
    elif i == 2 ** (N-1):
        A ^= 2 ** upk
        ans.append(A)
    else:
        keta = want_min(i)
        if keta >= upk:
            keta += 1
        A ^= 2**keta
        ans.append(A)

    #print (format(A,"b").zfill(N))

#print (ans[-1])
print (" ".join(map(str,ans)))

Buggy submission (verdict: Runtime Error):

"""
ハミング距離がちょうど1
絶対不可能なのは、AとBの1の数の偶奇が違うとき
それ以外は可能か？

可能と仮定して構成法を考えてみる
ハミング距離を1だけ変化させる方法
→2**xを xorする

AとBが1桁だけ違う場合は可能、それ以外は不可能？
→1回だけ選ぶ桁は1つしかないのでおｋそう

根本的に違う？
→最初と最後のハミング距離が1以外も可能？
→いやー無理やろ
"""
import sys

def want_min(x):

    for i in range(20):
        if (2**i)&x > 0:
            return i

d2lis = {}

for i in range(20):
    d2lis[2**i] = i

N,A,B = map(int,input().split())

if N >= 4:
    print (X)

if A^B not in d2lis:
    print ("NO")
    sys.exit()

print ("YES")

upk = d2lis[A^B]
ans = []

for i in range(2**N):

    if i == 0:
        ans.append(A)
    elif i == 2 ** (N-1):
        A ^= 2 ** upk
        ans.append(A)
    else:
        keta = want_min(i)
        if keta >= upk:
            keta += 1
        A ^= 2**keta
        ans.append(A)

    #print (format(A,"b").zfill(N))

#print (ans[-1])
print (" ".join(map(str,ans)))