abc 172 F-Unfair Nim (python)

4完 パフォ1412 でした。最近パフォが1400 くらいで安定している。今はいいけど水色になってからは困るなあ。
コンテスト後に F を通しました。考察はあと一歩だったけど、実装の場合分けは無理でした。

まず、Nim の必勝法は A1^A2^...^An = 0 なら 後手が必ず勝ちます。コンテスト中に蟻本を読んでズルした。理由ははしょります。
なので、s = A1+A2, c = A3^A4^...^An とおくとこの問題は、
(A1-i)^(A2+i) = c を満たす最小の i を求める、という問題になります。（A1^A2^c = 0 なので）
そこから、s の式に注目すると、P + Q = (P ^ Q) + 2*(P & Q) という xor の問題で使うらしいテクニックがあるので、s = A1+A2 の式を s = (A1-i)^(A2+i) + ( (A1-i) & (A2+i) )*2 と書き換えると、

x = (A1-i), y = (A2+i) とおくとこの問題は連立方程式
x ^ y = c　ー①
x & y = (s-c)/2　－②
をみたす１≦ x ≦ A1 のなかで最大のものを求めればいいことになります。
とりあえず、s < c のものや、(s-c)/2 が少数のものはその時点で答えは -1 としていいです。
さらに sc = (s-c)/2 とおいて ① に ^x を行って y = c^x とおくと①、②は
y = c^x　－③
x & (c^x) = sc　－④
と同値になります。
④の式の嬉しいところは xor も and も各桁ごとに独立なので、（繰り上がり、繰り下がりがない）
桁ごとに計算をしていい点です。

ここで、2進数で c = 1100, sc = 1010 としたとき、x の各桁はどのようになるのかを見ていくと、
(cc, ss, xx) = (c の桁の値、sc の桁の値、そのときのｘの桁の値）とすると
１．(cc, ss) = (0, 0) → xx = 0
２．(cc, ss) = (0, 1) → xx = 1
３．(cc, ss) = (1, 0) → xx = 0, 1
４．(cc, ss) = (1, 1) → これをみたす xx は存在しない
となります。
なので、 x は１. ~ 4 . と１≦ x ≦ A1 満たすもののなかで最大のものを求めればいいことになります。（これで④は成立して、③は x が存在すれば y も存在するので成立する）

1. ~ 4. を処理していく方針ですが、まず 4. は事前に

if c & sc != 0 :
  print(-1)
  exit()

と書いておけば気にしなくていいです。
あとはまず c と sc の桁を上から見ていって、1. と 2. なら x の桁は確定できるのでさせておき、３．なら x の桁を '?' としておきます。（例えば、c = 10010, sc = 100 なら x = '0?010?' となる）
この時点で x が A1 よりも超えることが確定していたら答えは -1 です。
あとは '?' の部分は A1 を超えない中で最大になるように前から決めたら終わりです。
出力する答えは A1 - x になります。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
s = a[0]+a[1]
# n = 2 は 別で処理
if n == 2:
  if a[0] < a[1] or s%2 == 1:
    print(-1)
  else:
    print(a[0]-s//2)
  exit()
  
# c を計算
c = 0
for i in a[2:]:
  c ^= i

# 取り合えず答えが -1 になるものを消す
sc = (s-c)//2
if s < c or (s-c)%2 == 1 or c&sc != 0:
  print(-1)
  exit()

# 1. ~ 3. の動作
# x は文字列、chk が実際の x の値
bb = a[0].bit_length()
x = ''
chk = 0
for i in range(bb-1,-1,-1):
  if (c>>i&1)|(sc>>i&1) == 0:
    x += '0'
  elif c>>i&1 == 0 and sc>>i&1 == 1:
    x += '1'
    chk += 2**i
  else:
    x += '?'

# この時点で x の値が A1 よりも超えていたら答えは -1 
if chk > a[0]:
  print(-1)
  exit()
  
# x が A1 を超えない最大値になるよう決めていく
for i in range(bb):
  if x[i] == '?':
    if a[0] >= chk+2**(bb-1-i):
      chk += 2**(bb-1-i)
     
# 条件を x の最小値は１なのでchk が１未満 (0) なら答えは -1
if chk == 0:
  print(-1)
else:
  print(a[0]-chk)