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

C++の練習を兼ねて, AtCoder Grand Contest 033 の問題C (Removing Coins) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を見て提出したところ, AC版に到達できた.
2. ゲームの勝者が, 木の直径の長さに依存する点が, 不思議な感じがした.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
// 解き直し.
// https://img.atcoder.jp/agc033/editorial.pdf
#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 a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. N が 1 の 場合.
    if(N == 1){
        puts("First");
        return 0;
    }
    
    // 3. 頂点 1 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 3-1. 空のキュー.
        queue<int> q;
        
        // 3-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 3-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 3-4. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 3-5. 訪問済であれば, 処理をスキップ.
                if(d[e])            continue;
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    int d[N];
    memset(d, 0, sizeof(d));
    bfs(G, 0, d);
    
    // 4. 直径 の 両端 の 頂点 x, y は？
    // 4-1. 頂点 1 から 最も遠い 頂点 x を保存.
    int x = -1, r = 0;
    rep(i, N){
        if(r < d[i]){
            r = max(r, d[i]);
            x = i;
        }
    }
    assert(x != -1);
    
    // 4-2. 頂点 x から 各頂点までの距離を計算.
    int dx[N];
    memset(dx, 0, sizeof(dx));
    bfs(G, x, dx);
    
    // 4-3. 頂点 x から 最も遠い 頂点 y を保存.
    int y = -1;
    r = 0;
    rep(i, N){
        if(r < dx[i]){
            r = max(r, dx[i]);
            y = i;
        }
    }
    assert(y != -1);
    
    // 4-4. 頂点 y から 各頂点までの距離を計算.
    int dy[N];
    memset(dy, 0, sizeof(dy));
    bfs(G, y, dy);
    
    // 4-5. 直径 L は？
    int L = dx[y];
    
    // 5. 出力.
    printf("%s\n", (L % 3 == 1) ? "Second" : "First");
    return 0;
    
}

100

// C++(GCC 9.2.1)

// 解き直し.

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

#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 a, b;

scanf("%d %d", &a, &b);

a--;

b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. N が 1 の場合.

if(N == 1){

puts("First");

return 0;

}

// 3. 頂点 1 から各頂点までの距離を計算.

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

auto bfs = [&](vvi &G, int s, int* d){

// 3-1. 空のキュー.

queue<int> q;

// 3-2. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 3-3. キューから取り出す.

int u = q.front();

q.pop();

// 3-4. 取り出した要素を処理.

for(auto &e : G[u]){

// 3-5. 訪問済であれば, 処理をスキップ.

if(d[e]) continue;

if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);

}

return;

};

int d[N];

memset(d, 0, sizeof(d));

bfs(G, 0, d);

// 4. 直径の両端の頂点 x, y は？

// 4-1. 頂点 1 から最も遠い頂点 x を保存.

int x = -1, r = 0;

rep(i, N){

if(r < d[i]){

r = max(r, d[i]);

x = i;

}

assert(x != -1);

// 4-2. 頂点 x から各頂点までの距離を計算.

int dx[N];

memset(dx, 0, sizeof(dx));

bfs(G, x, dx);

// 4-3. 頂点 x から最も遠い頂点 y を保存.

int y = -1;

r = 0;

rep(i, N){

if(r < dx[i]){

r = max(r, dx[i]);

y = i;

}

assert(y != -1);

// 4-4. 頂点 y から各頂点までの距離を計算.

int dy[N];

memset(dy, 0, sizeof(dy));

bfs(G, y, dy);

// 4-5. 直径 L は？

int L = dx[y];

// 5. 出力.

printf("%s\n", (L % 3 == 1) ? "Second" : "First");

return 0;

}

[入力例]
3
1 2
2 3

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

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

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

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

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

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

[出力例]
Second

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

[出力例]
First

[入力例]

1 2

2 3

[出力例]

First

※AtCoderのテストケースより

[入力例]

1 2

2 3

2 4

4 6

5 6

[出力例]

Second

※AtCoderのテストケースより

[入力例]

1 7

7 4

3 4

7 5

6 3

2 1

[出力例]

First

※AtCoderのテストケースより

[入力例]

5 4

4 1

6 1

2 1

3 1

7 3

8 3

[出力例]

Second

[入力例]

1 5

4 1

2 1

2 6

2 13

13 3

13 7

13 8

8 11

12 8

7 10

7 9

[出力例]

First

■参照サイト
AtCoder Grand Contest 033

C++の練習を兼ねて, AtCoder Grand Contest 033 の 問題C (Removing Coins) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 033 の問題C (Removing Coins) を解いてみた.

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