C++ の動作確認をしてみた（２２０）

C++の練習を兼ねて, AtCoder Regular Contest 028 の問題C (C – 高橋王国の分割統治) を解いてみた.

■感想.
1. 本問は, AtCoder Beginner Contest 160 の問題F (F – Distributing Integers) に, どことなく似ている感じがした.
2. 木dp の訓練が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトARC 028 解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
using P = pair<int, int>;
#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 a first
#define b second
const int LIMIT = 101010;
int d[LIMIT];    // 頂点 0 からの 距離 を 保存.
int size[LIMIT]; // 木の大きさ.
int dp[LIMIT];   // 木dp.

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @param d: 探索開始地点からの距離.
// @return: 特に無し.
void bfs(vvi &G, int s, int* d){
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    d[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        // 4. キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            if(d[e] > 0)            continue;
            if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, p;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        scanf("%d", &p);
        G[i + 1].pb(p);
        G[p].pb(i + 1);
    }
    
    // 2. 事前計算.
    rep(i, LIMIT) size[i] = 1;
    
    // 3. 頂点 0 から 各頂点までの距離を計算.
    bfs(G, 0, d);
    
    // 4. 頂点 0 から 遠い順 に並び替え.
    priority_queue<P> pq1, pq2;
    rep(i, N){
        // {距離, 頂点番号}
        pq1.push({d[i], i});
        pq2.push({d[i], i});
    }
    
    // 5. 部分木のサイズを取得.
    while(!pq1.empty()){
        // 5-1. 頂点 v を一つ取り出す.
        P p = pq1.top();
        pq1.pop();
        
        // 5-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 5-3. 頂点 v を 根とする部分木 の サイズ を 集計.
        for(auto &u : G[v]){
            // 頂点 v の 子頂点 に 相当する頂点 u を 選択.
            if(d[u] > d[v]){
                // 頂点 v の 周囲 の 頂点 u で, 頂点 0 から, より遠いものを加算.
                size[v] += size[u];
            }
        }
    }
    
    // 6. 木dp.
    while(!pq2.empty()){
        // 6-1. 頂点 v を一つ取り出す.
        P p = pq2.top();
        pq2.pop();
        
        // 6-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 6-3. 木dp の 更新.
        for(auto &u : G[v]){
            if(d[u] < d[v]) dp[v] = max(dp[v], N - size[v]); // 頂点 u は, 頂点 v の 親頂点.
            else            dp[v] = max(dp[v], size[u]);     // 頂点 u は, 頂点 v の 子頂点.
        }
    }
    
    // 7. 出力.
    rep(i, N) printf("%d\n", dp[i]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<vector<int>>;

using P = pair<int, int>;

#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 a first

#define b second

const int LIMIT = 101010;

int d[LIMIT]; // 頂点 0 からの距離を保存.

int size[LIMIT]; // 木の大きさ.

int dp[LIMIT]; // 木dp.

// グラフを幅優先探索する.

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

// ※bfsの動作確認用.

// @param G: グラフ.

// @param s: グラフの探索開始頂点.

// @param d: 探索開始地点からの距離.

// @return: 特に無し.

void bfs(vvi &G, int s, int* d){

// 1. 空のキュー.

queue<int> q;

// 2. 訪問済みフラグ設定.

// ※スタート地点は, 距離ゼロを指定.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

// 4. キューから取り出す.

int u = q.front();

q.pop();

// 5. 取り出した要素を処理.

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

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

if(d[e] > 0) continue;

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

}

return;

}

int main(){

// 1. 入力情報.

int N, p;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

scanf("%d", &p);

G[i + 1].pb(p);

G[p].pb(i + 1);

}

// 2. 事前計算.

rep(i, LIMIT) size[i] = 1;

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

bfs(G, 0, d);

// 4. 頂点 0 から遠い順に並び替え.

priority_queue<P> pq1, pq2;

rep(i, N){

// {距離, 頂点番号}

pq1.push({d[i], i});

pq2.push({d[i], i});

}

// 5. 部分木のサイズを取得.

while(!pq1.empty()){

// 5-1. 頂点 v を一つ取り出す.

P p = pq1.top();

pq1.pop();

// 5-2. 頂点 v の頂点番号は？

int v = p.b;

// 5-3. 頂点 v を根とする部分木のサイズを集計.

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

// 頂点 v の子頂点に相当する頂点 u を選択.

if(d[u] > d[v]){

// 頂点 v の周囲の頂点 u で, 頂点 0 から, より遠いものを加算.

size[v] += size[u];

}

// 6. 木dp.

while(!pq2.empty()){

// 6-1. 頂点 v を一つ取り出す.

P p = pq2.top();

pq2.pop();

// 6-2. 頂点 v の頂点番号は？

int v = p.b;

// 6-3. 木dp の更新.

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

if(d[u] < d[v]) dp[v] = max(dp[v], N - size[v]); // 頂点 u は, 頂点 v の親頂点.

else dp[v] = max(dp[v], size[u]); // 頂点 u は, 頂点 v の子頂点.

}

// 7. 出力.

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

return 0;

}

[入力例]
5
0
1
1
0

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

[入力例]
3
0
0

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

[入力例]
25
0
1
0
0
1
5
5
2
2
9
9
0
12
12
7
7
7
16
16
16
17
17
10
10
24

[出力例]
19
11
18
24
24
14
24
16
24
20
22
24
22
24
24
24
21
22
24
24
24
24
24
24
24

[入力例]
30
0
0
0
0
1
1
1
5
5
6
7
7
2
13
14
14
13
3
3
4
4
21
21
22
22
22
24
24
21

[出力例]
11
21
24
27
19
27
28
27
29
29
29
29
29
25
27
29
29
29
29
29
29
21
24
29
27
29
29
29
29
29

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

■参照サイト
AtCoder Regular Contest 028
AtCoder Beginner Contest 160

C++の練習を兼ねて, AtCoder Regular Contest 028 の 問題C (C – 高橋王国の分割統治) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 028 の問題C (C – 高橋王国の分割統治) を解いてみた.

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