Person responsible for problem description don’t w

問題概要

解法

閉路がないので必ず端の点は単調非増加. その点が0になったらその前の点が単調非増加になる.
よって必ずすべての石は取ることが出来て, 引き分けは存在しない.

各点について, その先の点の石の数は自由に変化させられる.
サンプルの1を例に取って考えてみる.
1番の山から石をとる時, 2番の山の石の数は自由に変化できる.
このとき, 2番の山を必ず0にすれば2番の山は無視でき, 同様に考えて1, 3, 5の独立した山だと考えることができる.
相手によって2番の山を増やされて, 1番の山がなくなった場合は, 2番の山を全てとって3番の山を減らしたい数だけ減らせば良い.
同様に, 2番めの山を取ってやりたいときは1番目の山をすべて取って, 2番めを減らしたい数だけ減らす. 1番目がないなら直接とって, 3番目は0にする. みたいに繰り返せる.
このことからサンプル1では
{1, 3, 5}, {2, 4, 6}
の2つ山の集合それぞれについて分けてそれぞれのNimを考えれば良い. どちらを選択するかは先手が自由に決められるのでどちらかに必勝な場合があれば先手の勝ち.
なお, 目的の山を相手に増やされた場合は同じ数だけ減らしてやれば打ち消せるので無視出来る.

もうすこし複雑な場合について考える.
サンプル1に新たに7番目の点を追加して, 5と6に有向辺を張った場合, その山は上のどちらの集合の山にもアクセスできる.
7番の山をすべてとって, 5番と6番を変化させて上のどちらの集合でも勝てるようにすれば必ず勝てるようになることが分かる.(つまり次の手が負けパターンになるようにする. )
また新たに8番目の山を4, 5の山に辺を張るように考えると, これも7番と同じように考えられるが7番が残っている. これは7, 8だけで考えた時に最後に石をとる時, 先の山をいじるようにすればよい.
よって{7, 8} を独立でかんがえた場合のの勝敗と全体の勝敗が一致する.
これを繰り返すことで, 様々な場合で勝敗が決められるようになる.

あとは集合の分け方さえちゃんと決まればいい.
ある点が属する集合は有向辺の先の集合と同じではいけないことは上から明らか.
もっと言うと, 辺の先の集合に非負の番号をつけておくと, それら以外の最小の非負整数がその点の属する集合の番号になる.(ちょっと考えれば上の考察からわかるはず)

ということで, 再帰でその点の番号を出して, 同じ番号同士でそれぞれNimを考えて, 勝ちパターンが一つでもあれば勝ち, それ以外は負け. としてやればよい.
Nimはxorとるだけ.

ちなみに, 集合の番号決めはgrundy数を決定するのとほぼおなじと考えられるので, grundy数について理解してからやると割りと自然にこの考察に行き着く.

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <cstdio>
#include <cstring>
#include <vector>

#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define pb push_back

using namespace std;

typedef vector<int> vi;

int N, M, maxId;
int v[1024], id[1024], nim[1024];
vi edge[1024];

void input() {
    scanf("%d%d", &N, &M);
    rep(i,N) scanf("%d", v+i);
    rep(i,M){
        int a, b;
        scanf("%d%d", &a, &b);
        a--; b--;
        edge[a].pb(b);
    }
    memset(id,-1,sizeof(id));
}

int build_id(int u){
    if(id[u] >= 0) return id[u];
    bool used[1024] = {0};
    rep(i,edge[u].size()) used[build_id(edge[u][i])] = 1;
    int k = 0;
    while(used[k++]);
    maxId = max(maxId, k);
    return id[u] = --k;
}

int solve() {
    rep(i,N) build_id(i);
    rep(i,maxId)
        rep(j,N) if(id[j] == i)
            nim[i] ^= v[j];
    rep(i,maxId)
        if(nim[i]) return 1;
    return 2;
}

int main() {
    input();
    printf("%d\n", solve());
    return 0;
}