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

C++の練習を兼ねて, AtCoder Regular Contest 112 の問題C (DFS Game) を解いてみた.

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

本家のサイト AtCoder Regular Contest 112 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/arc112/editorial/724
// 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
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    repx(i, 1, N){
        int p;
        scanf("%d", &p);
        --p;
        G[p].pb(i);
        G[i].pb(p);
    }
    
    // 2. dfs(部分木サイズ).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs1 = [](auto&& self, vvi &G, int cur, int bef, int* m, int* s) -> void {
        // 部分木サイズ(往路).
        s[cur]++;
        
        // 終了条件.
        if(m[cur]) return;
        
        // 訪問済みフラグ.
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            if(nex == bef) continue;
            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;
    dfs1(dfs1, G, 0, -1, memo, subTree);
    // rep(i, N) printf("subTree[%d]=%d\n", i, subTree[i]);
    
    // 3. dfs(ゲーム).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    function<int(vvi&, int, int, int*, int*)> dfs2 = [&](vvi &G, int bef, int cur, int* dp, int* m) {
        // 終了条件.
        if(m[cur]) return dp[cur];
        
        // 訪問済みフラグ.
        m[cur] = 1;
        
        // コイン回収.
        ++dp[cur];
        
        // 葉っぱ(根は除く).
        if(cur != 0 && G[cur].size() == 1) return dp[cur];
        
        // 隣接頂点.
        vi f1, f2, f3;
        for(auto &nex : G[cur]){
            // 次へ.
            if(nex == bef) continue;
            
            // 部分木(頂点 nex) の f.
            int f = dfs2(G, cur, nex, dp, m);
            
            // 保存(パターン③).
            if(subTree[nex] & 1){
                f3.pb(f);
                continue;
            }
            
            // 保存(パターン①, ②).
            if(f < 0) f1.pb(f);
            else      f2.pb(f);
        }
        
        // sort.
        sort(all(f3));
        
        // 集計(パターン①).
        for(auto &f : f1) dp[cur] += f;
        
        // 集計(パターン③).
        int t = 0;
        for(auto &f : f3){
            dp[cur] += t ? -f : +f;
            t ^= 1;
        }
        
        // 集計(パターン②).
        for(auto &f : f2) dp[cur] += t ? -f : +f;
        
        // 返却.
        return dp[cur];
    };
    int dp[N];
    rep(i, N) dp[i] = memo[i] = 0;
    dfs2(G, -1, 0, dp, memo);
    // rep(i, N) printf("dp[%d]=%d\n", i, dp[i]);
    
    // 4. 出力.
    printf("%d\n", (dp[0] + N) / 2);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

// 解き直し.

// https://atcoder.jp/contests/arc112/editorial/724

// 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

#define all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

repx(i, 1, N){

int p;

scanf("%d", &p);

--p;

G[p].pb(i);

G[i].pb(p);

}

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

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

auto dfs1 = [](auto&& self, vvi &G, int cur, int bef, int* m, int* s) -> void {

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

s[cur]++;

// 終了条件.

if(m[cur]) return;

// 訪問済みフラグ.

m[cur] = 1;

// 隣接頂点.

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

if(nex == bef) continue;

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;

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

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

// 3. dfs(ゲーム).

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

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

// 終了条件.

if(m[cur]) return dp[cur];

// 訪問済みフラグ.

m[cur] = 1;

// コイン回収.

++dp[cur];

// 葉っぱ(根は除く).

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

// 隣接頂点.

vi f1, f2, f3;

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

// 次へ.

if(nex == bef) continue;

// 部分木(頂点 nex) の f.

int f = dfs2(G, cur, nex, dp, m);

// 保存(パターン③).

if(subTree[nex] & 1){

f3.pb(f);

continue;

}

// 保存(パターン①, ②).

if(f < 0) f1.pb(f);

else f2.pb(f);

}

// sort.

sort(all(f3));

// 集計(パターン①).

for(auto &f : f1) dp[cur] += f;

// 集計(パターン③).

int t = 0;

for(auto &f : f3){

dp[cur] += t ? -f : +f;

t ^= 1;

}

// 集計(パターン②).

for(auto &f : f2) dp[cur] += t ? -f : +f;

// 返却.

return dp[cur];

};

int dp[N];

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

dfs2(G, -1, 0, dp, memo);

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

// 4. 出力.

printf("%d\n", (dp[0] + N) / 2);

return 0;

}

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

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

[入力例]
5
1 2 3 1

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

[入力例]
10
1 1 3 1 3 6 7 6 6

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

[入力例]
15
1 2 3 3 3 2 1 8 8 1 11 11 13 13

[出力例]
8

[入力例]
27
1 2 2 2 5 5 1 8 8 10 10 1 13 14 14 13 13 18 18 18 1 22 22 22 25 25

[出力例]
15

[入力例]
33
3 1 5 2 5 1 1 3 9 9 7 12 12 14 14 8 17 17 17 19 19 1 23 23 8 24 25 28 28 16 16 2

[出力例]
16

[入力例]

1 2 3 4 5 6 7 8 9

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3 1

[出力例]

※AtCoderのテストケースより

[入力例]

1 1 3 1 3 6 7 6 6

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3 3 3 2 1 8 8 1 11 11 13 13

[出力例]

[入力例]

1 2 2 2 5 5 1 8 8 10 10 1 13 14 14 13 13 18 18 18 1 22 22 22 25 25

[出力例]

[入力例]

3 1 5 2 5 1 1 3 9 9 7 12 12 14 14 8 17 17 17 19 19 1 23 23 8 24 25 28 28 16 16 2

[出力例]

■参照サイト
AtCoder Regular Contest 112

C++の練習を兼ねて, AtCoder Regular Contest 112 の 問題C (DFS Game) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 112 の問題C (DFS Game) を解いてみた.

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