C++ の動作確認をしてみた（６９１）

C++の練習を兼ねて, AtCoder Beginner Contest 149 の問題F (Surrounded Nodes) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc149/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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
const LL MOD = 1e9 + 7;
LL mPow2[202020], c[202020];

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. 事前計算.
    mPow2[0] = 1;
    repx(i, 1, 202020) mPow2[i] = (mPow2[i - 1] * (LL)(5e8 + 4)) % MOD;
    rep(i, 202020) c[i] = (MOD + 1 - mPow2[i]) % MOD;
    // rep(i, N) printf("c[%d]=%lld\n", i, c[i]);
    
    // 3. dfs(部分木サイズ).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [](auto&& self, vvi &G, int cur, int bef, int* m, int* s){
        // 部分木サイズ(往路).
        ++s[cur];
        
        // 終了条件.
        if(m[cur]) return;
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]) if(nex != bef) self(self, G, nex, cur, m, s);
        
        // 部分木サイズ(復路).
        if(bef != -1) s[bef] += s[cur];
    };
    int subTree[N], memo[N];
    rep(i, N) subTree[i] = memo[i] = 0;
    dfs(dfs, G, 0, -1, memo, subTree);
    // rep(i, N) printf("subTree[%d]=%d\n", i, subTree[i]);
    
    // 4. S の 辺数(期待値).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    LL ans = 0;
    function<void(vvi&, int, int, int*)> f = [&](vvi &G, int cur, int bef, int* m){
        // 終了条件.
        if(m[cur]) return;
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            // 親頂点か否か.
            if(nex == bef) continue;
            
            // S に含まれる辺数の期待値を加算.
            ans += c[subTree[nex]] * c[N - subTree[nex]] % MOD;
            ans %= MOD;
            
            // 次へ.
            f(G, nex, cur, m);
        }
    };
    rep(i, N) memo[i] = 0;
    f(G, 0, -1, memo);
    
    // 5. S の 頂点数(期待値).
    // 5-1. 頂点数は, 辺数よりも, 1 多い.
    ++ans;
    ans %= MOD;
    
    // 5-2. 空グラフ除外.
    ans += (MOD - mPow2[N]);
    ans %= MOD;
    
    // 6. 黒く塗られた頂点数(期待値, 減算).
    ans += MOD - N * (LL)(5e8 + 4) % MOD;
    ans %= MOD;
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

const LL MOD = 1e9 + 7;

LL mPow2[202020], c[202020];

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. 事前計算.

mPow2[0] = 1;

repx(i, 1, 202020) mPow2[i] = (mPow2[i - 1] * (LL)(5e8 + 4)) % MOD;

rep(i, 202020) c[i] = (MOD + 1 - mPow2[i]) % MOD;

// rep(i, N) printf("c[%d]=%lld\n", i, c[i]);

// 3. dfs(部分木サイズ).

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

auto dfs = [](auto&& self, vvi &G, int cur, int bef, int* m, int* s){

// 部分木サイズ(往路).

++s[cur];

// 終了条件.

if(m[cur]) return;

m[cur] = 1;

// 隣接頂点.

for(auto &nex : G[cur]) if(nex != bef) self(self, G, nex, cur, m, s);

// 部分木サイズ(復路).

if(bef != -1) s[bef] += s[cur];

};

int subTree[N], memo[N];

rep(i, N) subTree[i] = memo[i] = 0;

dfs(dfs, G, 0, -1, memo, subTree);

// rep(i, N) printf("subTree[%d]=%d\n", i, subTree[i]);

// 4. S の辺数(期待値).

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

LL ans = 0;

function<void(vvi&, int, int, int*)> f = [&](vvi &G, int cur, int bef, int* m){

// 終了条件.

if(m[cur]) return;

m[cur] = 1;

// 隣接頂点.

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

// 親頂点か否か.

if(nex == bef) continue;

// S に含まれる辺数の期待値を加算.

ans += c[subTree[nex]] * c[N - subTree[nex]] % MOD;

ans %= MOD;

// 次へ.

f(G, nex, cur, m);

}

};

rep(i, N) memo[i] = 0;

f(G, 0, -1, memo);

// 5. S の頂点数(期待値).

// 5-1. 頂点数は, 辺数よりも, 1 多い.

++ans;

ans %= MOD;

// 5-2. 空グラフ除外.

ans += (MOD - mPow2[N]);

ans %= MOD;

// 6. 黒く塗られた頂点数(期待値, 減算).

ans += MOD - N * (LL)(5e8 + 4) % MOD;

ans %= MOD;

// 7. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
3
1 2
2 3

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

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

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

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

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

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

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

[入力例]
2
1 2

[出力例]
0

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

[出力例]
781250007

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

[出力例]
697387702

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

[出力例]
783004770

100

101

102

103

104

105

106

[入力例]

1 2

2 3

[出力例]

125000001

※AtCoderのテストケースより

[入力例]

1 2

2 3

3 4

[出力例]

375000003

※AtCoderのテストケースより

[入力例]

1 2

1 3

1 4

[出力例]

250000002

※AtCoderのテストケースより

[入力例]

4 7

3 1

2 6

5 2

7 1

2 7

[出力例]

570312505

※AtCoderのテストケースより

[入力例]

1 2

[出力例]

[入力例]

2 1

3 1

1 5

2 6

2 7

4 3

5 8

5 9

5 10

[出力例]

781250007

[入力例]

1 2

1 3

1 4

2 5

2 6

2 7

3 8

3 9

3 10

4 11

4 12

4 13

[出力例]

697387702

[入力例]

1 2

1 3

4 2

5 2

6 2

7 3

8 3

9 3

4 10

4 11

5 12

5 13

12 14

12 15

7 16

7 17

9 18

9 19

18 20

[出力例]

783004770

■参照サイト
AtCoder Beginner Contest 149

C++の練習を兼ねて, AtCoder Beginner Contest 149 の 問題F (Surrounded Nodes) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 149 の問題F (Surrounded Nodes) を解いてみた.

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