C++ の動作確認をしてみた（７１８）

C++の練習を兼ねて, AtCoder Grand Contest 017 の問題D (Game on Tree) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 解説上のロジックで, 計算可能であることが, 摩訶不思議な感じがして, 非常に面白いと感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Grand Contest 017 解説をご覧下さい.

■C++版プログラム(問題D／AC版).

// 解き直し.
// https://img.atcoder.jp/agc017/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* g) -> int {
        // 終了条件.
        if(bef != -1 && G[cur].size() == 1) return (g[cur] = 0);
        if(g[cur] != -1)                    return g[cur];
        
        // 隣接頂点(Grundy数 の XOR計算).
        int ret = 0;
        for(auto &nex : G[cur]){
            if(nex != bef) ret ^= (self(self, G, nex, cur, g) + 1);
        }
        
        // 返却.
        return (g[cur] = ret);
    };
    int grundy[101010];
    rep(i, N) grundy[i] = -1;
    int ans = dfs(dfs, G, 0, -1, grundy);
    // rep(i, N) printf("%d ", grundy[i]);
    // puts("");
    
    // 3. 出力.
    printf("%s\n", ans ? "Alice" : "Bob");
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/agc017/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int u, v;

scanf("%d %d", &u, &v);

--u;

--v;

G[u].pb(v);

G[v].pb(u);

}

// 2. dfs.

// https://ja.wikipedia.org/wiki/深さ優先探索

auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* g) -> int {

// 終了条件.

if(bef != -1 && G[cur].size() == 1) return (g[cur] = 0);

if(g[cur] != -1) return g[cur];

// 隣接頂点(Grundy数の XOR計算).

int ret = 0;

for(auto &nex : G[cur]){

if(nex != bef) ret ^= (self(self, G, nex, cur, g) + 1);

}

// 返却.

return (g[cur] = ret);

};

int grundy[101010];

rep(i, N) grundy[i] = -1;

int ans = dfs(dfs, G, 0, -1, grundy);

// rep(i, N) printf("%d ", grundy[i]);

// puts("");

// 3. 出力.

printf("%s\n", ans ? "Alice" : "Bob");

return 0;

}

[入力例]
5
1 2
2 3
2 4
4 5

[出力例]
Alice
※AtCoderテストケースより

[入力例]
5
1 2
2 3
1 4
4 5

[出力例]
Bob
※AtCoderテストケースより

[入力例]
6
1 2
2 4
5 1
6 3
3 2

[出力例]
Alice
※AtCoderテストケースより

[入力例]
7
1 2
3 7
4 6
2 3
2 4
1 5

[出力例]
Bob
※AtCoderテストケースより

[入力例]
7
1 2
1 3
2 4
3 5
4 6
5 7

[出力例]
Bob

[入力例]
8
1 2
1 3
1 8
2 4
3 5
4 6
5 7

[出力例]
Alice

[入力例]
13
1 2
1 3
1 4
8 2
9 2
10 2
8 11
5 3
6 3
4 7
7 12
7 13

[出力例]
Bob

[入力例]
20
1 2
1 6
1 7
1 12
1 14
13 12
3 2
3 4
3 5
4 17
18 5
19 18
10 6
11 6
11 20
7 8
9 8
14 15
16 15

[出力例]
Alice

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

[入力例]

1 2

2 3

2 4

4 5

[出力例]

Alice

※AtCoderテストケースより

[入力例]

1 2

2 3

1 4

4 5

[出力例]

Bob

※AtCoderテストケースより

[入力例]

1 2

2 4

5 1

6 3

3 2

[出力例]

Alice

※AtCoderテストケースより

[入力例]

1 2

3 7

4 6

2 3

2 4

1 5

[出力例]

Bob

※AtCoderテストケースより

[入力例]

1 2

1 3

2 4

3 5

4 6

5 7

[出力例]

Bob

[入力例]

1 2

1 3

1 8

2 4

3 5

4 6

5 7

[出力例]

Alice

[入力例]

1 2

1 3

1 4

8 2

9 2

10 2

8 11

5 3

6 3

4 7

7 12

7 13

[出力例]

Bob

[入力例]

1 2

1 6

1 7

1 12

1 14

13 12

3 2

3 4

3 5

4 17

18 5

19 18

10 6

11 6

11 20

7 8

9 8

14 15

16 15

[出力例]

Alice

■参照サイト
AtCoder Grand Contest 017

C++の練習を兼ねて, AtCoder Grand Contest 017 の 問題D (Game on Tree) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Grand Contest 017 の問題D (Game on Tree) を解いてみた.

コメントを残すコメントをキャンセル