AGC045 - A. Xor Battle

問題 : atcoder.jp
公式解説 : https://img.atcoder.jp/agc045/editorial.pdf
提出 : Submission #15405606 - AtCoder Grand Contest 045

AtCoder Problemsの青diff埋めをしていたら、手がつけられなくて、解説pdfや解法ブログを読んでも解法の理解に時間がかかったので、解法にたどり着くまでの記録をまとめます。（AGC045のとてもわかりやすい公式Youtube解説放送もない？）

問題概要

$N$ ステップの2人制ゲーム。手番と操作内容が予め固定されていて、プレイヤーは操作内容を実行するかしないかを選択できる。

ゲームの盤面は一つの変数 $x$ のみで、 $0$ で初期化されている。ゲームの $i$ ステップ目には手番 $S_i$ と操作内容の整数 $A_i$ が与えられていて、プレイヤー $S_i$ は変数 $x$ を $x \oplus A_i$ に置き換えるか、そのままにするかを選択できる。

プレイヤー $0$ はゲーム終了時の $x$ を $0$ にしたい。プレイヤー $1$ はゲーム終了時の $x$ を $0$ 以外にしたい。

勝つのはどちらか。

ケーススタディ

ゲームの必勝に関する考察では、何はともあれゲームの終局付近から考察を進めるのが基本です。*1

パターン1 : 最後の手番が $S_n=1$ のとき

プレイヤー $1$ が勝つ。

最後の手番で、

- 操作を行えばプレイヤー $1$ の勝ち
- 操作を行わなければプレイヤー $1$ の勝ち

パターン2 : 最後の手番が $S_{n-1:n}=10$ のとき

$A_n \neq A_{n-1}$ ならプレイヤー $1$ が勝つ。

- 操作を行えばプレイヤー $1$ の勝ち
- $(x_{n-2} \oplus A_{n} ) \oplus A_{n-1} = A_{n-1}$
- $x_{n-2} \oplus A_{n-1} \neq 0$
- 操作を行わなければプレイヤー $1$ の勝ち

$A_n = A_{n-1}$ の時は、この時点ではわからない。

パターン3 : 最後の手番が $S_{n-k:n}=10 \ldots 00$ のとき

整数 $A_i$ を

非負整数 $0, 1, \ldots, 2^{60}-1$ はxorに関して $\mathbb{F}_{2}$ ベクトル空間をなし、その構造は $\mathbb{F}_{2}^{60}$ と同型です。よって以下では、 $A_i \in \mathbb{F}_{2}^{60}$ と見なします。*2

$(A_{n-k+1} \cdots A_{n})$ の任意のxor上の線形結合によって得られるベクトルの集合を $W$ とする。 $W$ は $\mathbb{F}_{2}^{60}$ 上の $(A_{n-k+1} \cdots A_{n})$ を含む最小の部分空間であることに注意する。

$A_{n-k} \notin W$ なら、プレイヤー $1$ が勝つ。

- 操作を行えばプレイヤー $1$ の勝ち
- $\forall v \in W$
- $v \oplus A_{n-k} \notin W$
- $v \oplus A_{n-k} \neq x_{n-k-1}$
- $v \oplus A_{n-k} \oplus x_{n-k-1} \neq 0$
- 操作を行わなければプレイヤー $1$ の勝ち

$A_{n-k} \in W$ なら、さらに遡らないとわからない。が、プレイヤー $1$ が操作してもしなくても、その後にプレイヤー $0$ はその選択を打ち消すように行動を取れる。つまり、この場合、プレイヤー $1$ は操作しないものとしてスキップして良い。

解法

ゲームを後方から見ていく。あるステップ $i$ 以降でプレイヤー $0$ が作れる整数( $\mathbb{F}_{2}^{60}$ ベクトル)の集合を $W$ とする。 $W$ を更新していく。

あるステップ $i$ について

のとき
- $W$ に $A_i$ を含んだ線形結合で表せるベクトルを追加する。
のとき
- $W$ に $A_i$ が含まれているか調べる。
- 含まれているなら何もしない。
- 含まれていないなら、プレイヤー $1$ の勝ちとする。

最初のステップまで到達できた時、プレイヤー $0$ はプレイヤー $1$ の任意の行動に対して、打ち消しの行動を取れるということなので、プレイヤー $0$ の勝ちとする。

XORの基底の管理

実装するためには、

$W$ に $A_i$ を含んだ線形結合で表せるベクトルを追加する。(insert)
$W$ に $A_i$ が含まれているか調べる。(count)

の二つのクエリを高速に動作させるデータ構造が必要になる。解説pdfには

この DP は，xor の基底を管理することで，効率的に計算することができます．*3

とあり、「xor の基底を管理」するデータ構造が必要になる。

基底ベクトル行列を掃き出し法を用いて行簡約階段形で持っておくことで、insertとcountの動作をO(bit数)で行える。

コードを参考に動作を確認して欲しい。

#include <bits/stdc++.h>
 
#define debug(var)  do{std::cerr << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cerr << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cerr << e << " "; } std::cerr << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<ll> v1;
typedef vector<v1> v2;
typedef vector<v2> v3;
 
typedef unordered_map<ll, unordered_map<ll, ll>> graph;
 
const ll INF = 1ll << 50;
const ll mod = 1000000007;
 
class xor_set{
private:
    v1 w;
public:
    xor_set () {}
    void insert(ll x){
        for(ll v : w) if(v & -v & x) x ^= v;
        if(x == 0) return;
        for(ll& v : w) if(x & -x & v) v ^= x;
        w.push_back(x);
    }
 
    ll count(ll x){
        for(ll v : w) if(v & -v & x) x ^= v;
        if(x == 0) return 1;
        else return 0;
    }
};

コード中のv & -vとあるのはlong long型整数vの最下位に立っているbitのみを立たせた変数を表現する方法で、Binary Indexed Treeで使われていたりするテクニック。コードの多くはこちら*4を参考に作成した。

感想

むずい。

参考文献

*1:https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2020-06-07agc045#toc2

*2:https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2020-06-07agc045#toc2

*3:https://img.atcoder.jp/agc045/editorial.pdf

*4:https://suikaba.hatenablog.com/entry/2017/08/16/191209

deoxy’s diary

AtCoder Grand Contest 045 - A. Xor Battle 解法ログ

AGC045 - A. Xor Battle

問題概要