AGC 045 A Xor Battle 解説
はじめに
- 当日
- 20:55 よーし、AGCがんばるぞー
- 21:00 コンテスト開始
- 21:30 なんもわからん。コンテスト終わったら解説読むか
- 翌日以降: 誰も解説してくれないんだが...?
その後、おおよそ理解したのでメモ。
事前知識
XOR関連
XOR(排他的論理和)とは
詳細はWikiで。 要点は以下の真理値表(ここで⊕は問題文にならってXORに対応)
| A | B | A⊕B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
特に、
- ABが同じ: 0
- ABが異なる: 1
- XORを偶数回操作すると元に戻る: $A \oplus B \oplus B=A$
です。
自分自身が逆元である
単位元を0とすると、二進数表記のAに対する逆元はA自身です。 例えば、$A=00101$とします。自分自身とのXORをとってみましょう。
$$A \oplus A=00000$$
詳しい証明などはこちらを参照してください。
ベクトルの線型結合
線形従属・線形独立
線形代数の基礎知識、線形従属・線形独立の理解が必要です。 Wikiさんとか理数アラカルトさんに譲ります。
ここでは、具体例を交えながら簡単に解説します。 3次元空間を考えます。 ベクトル${\bf v}_{1}, {\bf v}_{2}$があるとしましょう。ただし、${\bf v}_{1}=(0, 0, 1)^\top, {\bf v}_{2}=(0, 1, 0)^\top$とします。 このとき 、${\bf v}_{3}$が${\bf v}_{1}, {\bf v}_{2}$の線形和で表せるかを考えます。
- case 1: ${\bf v}_{3}=(0, 1, 1)^\top$
→単純に${\bf v}_{1}+{\bf v}_{2}$で${\bf v}_{3}$で表すことができます。 このとき、${\bf v}_{3}$は${\bf v}_{1}, {\bf v}_{2}$と線形従属な関係にあります。
- case 2: ${\bf v}_{3}=(1, 0, 0)^\top$
→このケースはいくら${\bf v}_{1}, {\bf v}_{2}$をこねくりまわしても、${\bf v}_{3}$を表現することができません。 このとき、${\bf v}_{3}$は${\bf v}_{1}, {\bf v}_{2}$と線形独立な関係にあります。
続いて、XOR演算でこの特性を確認していきましょう。
XORにおける従属関係の確認方法
よく見ると、先程３次元で定義していたベクトル${\bf v}$というのは、二進数表記の整数に見えますね(見えてください)。
つまり、${\bf v}_{1}=(0, 0, 1) \rightarrow e_1=001, {\bf v}_{1}=(0, 1, 0) \rightarrow e_2=010$に見えます。 このとき 、ある整数の二進数表記$v$が、$e_1, e_2$のXORのみで表現できるかはどのように確認できるでしょうか？
- case 1: $v=011$
→単純に$e_1 \oplus e_2$で表すことができます。すなわち、$v$は既存の基底と従属な関係にある。
- case 1: $v=110$
→$e_1, e_2$をこねくり回しても表現できません。すなわち、$v$は既存の基底と独立な関係にある。ただし、追加で$e_3=100$という基底があれば表現可能です。
また、値の大きい基底から順番に、基底の最上位bitが$v$で立っているかを確認することで、従属関係を確認できます*1。
具体的なコードは以下。
base = [1, 2] v = int(input()) for e in sorted(base, reverse=True): # print('v : {:2d} {:05b}'.format(v, v)) # print('e : {:2d} {:05b}'.format(e, e)) # print('e^v: {:2d} {:05b}'.format(v ^ e, v ^ e)) # print('-'*16) v = min(v, e ^ v) # print('v : {:2d} {:05b}'.format(v, v)) if v == 0: print('従属!') if v > 0: print('独立!')
※print前のコメントアウトを消すと変数の細かな動きを確認できます。
ここで、minが掃き出し処理に相当します*2。
動作例
3 v : 3 00011 e : 2 00010 e^v: 1 00001 ---------------- v : 1 00001 e : 1 00001 e^v: 0 00000 ---------------- v : 0 00000 従属!
また、重要な知見として、計算結果の変数vは、入力値ｖを表現するために追加で必要な基底にあたります。
解説
発想と方針
- 発想
- $A_{1:i-1}$に関係なく、$A_i$を$A_{i+1:N}$のXORで表現できなければ、0さんは詰み
- $A_i$を$A_{i+1:N}$で表現できなくする動作をしたら、1さんの勝ち
- 方針
- 後ろから$A_i$を$A_{i+1:N}$で表現できるかチェック
- $A_{i+1:N}$の基底で貼る空間に$A_i$が収まっている(従属)か?
- 表現できるなら、0さん1さん関係なくpass
- 表現できない場合
- 0さん: $A_i$を使用(=基底を追加)
- 1さん: $A_i$を使わないことで勝利が確定
- 後ろから$A_i$を$A_{i+1:N}$で表現できるかチェック
ACコード
前項の発想と方針を実装すると以下になります。
def solve(): base = [] for a, s in zip(A[::-1], S[::-1]): # print(f'a: {a}, s: {s}') # for i, y in enumerate(base): # print('base{:d} {:3d}: {:05b}'.format(i, y, y)) x = a for y in sorted(base, reverse=True): x = min(x, x ^ y) if x: if s == "0": # print('=>add {:3d}: {:05b}'.format(x, x)) base.append(x) else: return 1 return 0 t = int(input()) for _ in range(t): n = int(input()) *A, = map(int, input().split()) S = input() # print(f'A: {A}, S: {S}') print(solve()) # print('-'*32)
※print前のコメントアウトを消すと変数の細かな動きを確認できます。
こんな感じ。baseで表現できなければ、baseにaddされていきます。
A: [2, 3, 4, 5, 6, 7], S: 111000 a: 7, s: 0 =>add 7: 00111 a: 6, s: 0 base0 7: 00111 =>add 1: 00001 a: 5, s: 0 base0 7: 00111 base1 1: 00001 =>add 2: 00010 a: 4, s: 1 base0 7: 00111 base1 1: 00001 base2 2: 00010 a: 3, s: 1 base0 7: 00111 base1 1: 00001 base2 2: 00010 a: 2, s: 1 base0 7: 00111 base1 1: 00001 base2 2: 00010 0
わからないこと
従属関係を確認する際に、appendした順に比較を行うこと(つまり、sorted(base, reverse_True) -> base)でもACとなるのはなぜか？
おわりに
AGC難しい...。 間違っている箇所などあればご指摘ください。
