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

C++の練習を兼ねて, AtCoder Regular Contest 083 の問題E (Bichrome Tree) を解いてみた.

■感想.
1. E問題は, 方針が全く見えず, 解説を確認して, AC版に到達できたので, 良かったと思う.
2. 問題文で問われている内容を理解するのに, 時間かかってしまったように思う.
3. 木dp の訓練, 幅優先探索の復習が出来たので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc083/editorial.pdf
#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
int d[1010];   // 頂点 1 からの 距離 を 保存.
int x[1010];   // 重み(数列).
int dpX[1010]; // 木dp(頂点 i を 根 とみた 部分木 で 同じ色).
int dpY[1010]; // 木dp(頂点 i を 根 とみた 部分木 で 異なる色).

// 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. 探索地点 s をキュー q に追加.
    q.push(s);
    
    // 3. キューが空になるまで繰り返し.
    while(!q.empty()){
        // 4. 頂点を一つ取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 隣接する頂点を確認.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            if(d[e])            continue;
            if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, p;
    scanf("%d", &N);
    vvi G(N);
    repx(i, 1, N){
        scanf("%d", &p);
        p--;
        G[i].pb(p);
        G[p].pb(i);
    }
    rep(i, N) scanf("%d", &x[i]);
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    bfs(G, 0, d);
    // rep(i, N) printf("%d ", d[i]);
    // puts("");
    
    // 3. 頂点 1 から 遠い順 に並び替え.
    priority_queue<P> pq;
    rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}
    
    // 4. 木dp.
    bool ok = true;
    while(!pq.empty()){
        // 4-1. 頂点 v を一つ取り出す.
        P p = pq.top();
        pq.pop();
        
        // 4-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 4-3. 配列宣言.
        int z[5050], xy = 0, wSum = 0;
        memset(z, 0, sizeof(z));
        
        // 4-4. スタート地点は, 1 を 設定.
        z[0] = 1;
        
        // 4-5. 頂点 v を 根とする部分木 について, 木dp を 更新.
        // printf("1. v=%d\n", v);
        for(auto &u : G[v]){
            // 頂点 v の 子供 に 相当する頂点 u を 選択.
            if(d[u] > d[v]){
                // 頂点 v の 子供について, 重みの総和 を 集計.
                xy += x[u];   // 頂点 u の 重み(※同じ色, 子孫).
                xy += dpY[u]; // 頂点 u の 重み(※異なる色, 子孫).
                
                // 頂点 v の 子供について, 重みの総和(最小値) を 集計.
                wSum += min(x[u], dpY[u]);
                
                // 頂点 v の 子供について, 同色のものの重みの和が, x[v]以下となるか？
                // Typical DP Contest (A - コンテスト) を ベース に 実装.
                // https://atcoder.jp/contests/tdpc/tasks/tdpc_contest
                repr(i, x[v], 0){
                    if(z[i]){
                        if(i + x[u]   <= x[v]) z[i + x[u]]   = 1;
                        if(i + dpY[u] <= x[v]) z[i + dpY[u]] = 1;
                    }
                    // printf("2. u=%d dpX=%d dpY=%d\n", u, dpX[u], dpY[u]);
                }
            }
        }
        
        // 4-6. x[v]以下となる z[i] を 探索.
        int maxZ = 0;
        rep(i, x[v] + 1) if(z[i]) maxZ = i;
        
        // 4-7. 割り当てを行う.
        if(wSum <= x[v]){
            dpX[v] = x[v] - maxZ;
            dpY[v] = xy + dpX[v] - x[v];
        }else{
            ok = false;
            break;
        }
    }
    // rep(i, N) printf("%d ", dpX[i]);
    // puts("");
    // rep(i, N) printf("%d ", dpY[i]);
    // puts("");
    
    // 5. 出力.
    printf("%s\n", ok ? "POSSIBLE" : "IMPOSSIBLE");
    return 0;
    
}

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

// 解き直し.

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

#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

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

int x[1010]; // 重み(数列).

int dpX[1010]; // 木dp(頂点 i を根とみた部分木で同じ色).

int dpY[1010]; // 木dp(頂点 i を根とみた部分木で異なる色).

// 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. 探索地点 s をキュー q に追加.

q.push(s);

// 3. キューが空になるまで繰り返し.

while(!q.empty()){

// 4. 頂点を一つ取り出す.

int u = q.front();

q.pop();

// 5. 隣接する頂点を確認.

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

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

if(d[e]) continue;

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

}

return;

}

int main(){

// 1. 入力情報.

int N, p;

scanf("%d", &N);

vvi G(N);

repx(i, 1, N){

scanf("%d", &p);

p--;

G[i].pb(p);

G[p].pb(i);

}

rep(i, N) scanf("%d", &x[i]);

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

bfs(G, 0, d);

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

// puts("");

// 3. 頂点 1 から遠い順に並び替え.

priority_queue<P> pq;

rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}

// 4. 木dp.

bool ok = true;

while(!pq.empty()){

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

P p = pq.top();

pq.pop();

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

int v = p.b;

// 4-3. 配列宣言.

int z[5050], xy = 0, wSum = 0;

memset(z, 0, sizeof(z));

// 4-4. スタート地点は, 1 を設定.

z[0] = 1;

// 4-5. 頂点 v を根とする部分木について, 木dp を更新.

// printf("1. v=%d\n", v);

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

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

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

// 頂点 v の子供について, 重みの総和を集計.

xy += x[u]; // 頂点 u の重み(※同じ色, 子孫).

xy += dpY[u]; // 頂点 u の重み(※異なる色, 子孫).

// 頂点 v の子供について, 重みの総和(最小値) を集計.

wSum += min(x[u], dpY[u]);

// 頂点 v の子供について, 同色のものの重みの和が, x[v]以下となるか？

// Typical DP Contest (A - コンテスト) をベースに実装.

// https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

repr(i, x[v], 0){

if(z[i]){

if(i + x[u] <= x[v]) z[i + x[u]] = 1;

if(i + dpY[u] <= x[v]) z[i + dpY[u]] = 1;

}

// printf("2. u=%d dpX=%d dpY=%d\n", u, dpX[u], dpY[u]);

}

// 4-6. x[v]以下となる z[i] を探索.

int maxZ = 0;

rep(i, x[v] + 1) if(z[i]) maxZ = i;

// 4-7. 割り当てを行う.

if(wSum <= x[v]){

dpX[v] = x[v] - maxZ;

dpY[v] = xy + dpX[v] - x[v];

}else{

ok = false;

break;

}

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

// puts("");

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

// puts("");

// 5. 出力.

printf("%s\n", ok ? "POSSIBLE" : "IMPOSSIBLE");

return 0;

}

[入力例]
3
1 1
4 3 2

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

[入力例]
3
1 2
1 2 3

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

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

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

[入力例]
1

0

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

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

[出力例(debug版)]
1 4 2 0 1 
3 0 0 0 0 
POSSIBLE

[入力例]
10
1 4 1 4 4 4 9 1 9
1 1 1 1 1 1 1 1 1 1

[出力例(debug版)]
0 1 1 0 1 1 1 1 0 1 
0 0 0 3 0 0 0 0 1 0 
IMPOSSIBLE

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

[出力例(debug版)]
0 2 3 0 2 5 0 0 3 6 1 
12 0 0 3 0 0 1 3 0 0 0 
POSSIBLE

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

[出力例(debug版)]
1 3 1 0 0 0 1 2 5 3 1 1 2 3 2 
13 0 4 11 0 1 0 0 0 0 0 2 0 0 0 
POSSIBLE

[入力例]

1 1

4 3 2

[出力例]

POSSIBLE

※AtCoderテストケースより

[入力例]

1 2

1 2 3

[出力例]

IMPOSSIBLE

※AtCoderテストケースより

[入力例]

1 1 1 3 4 5 5

4 1 6 2 2 1 3 3

[出力例]

POSSIBLE

※AtCoderテストケースより

[入力例]

[出力例]

POSSIBLE

※AtCoderテストケースより

[入力例]

1 4 1 4

5 4 2 3 1

[出力例(debug版)]

1 4 2 0 1

3 0 0 0 0

POSSIBLE

[入力例]

1 4 1 4 4 4 9 1 9

1 1 1 1 1 1 1 1 1 1

[出力例(debug版)]

0 1 1 0 1 1 1 1 0 1

0 0 0 3 0 0 0 0 1 0

IMPOSSIBLE

[入力例]

7 8 1 8 8 1 1 4 4 7

10 2 3 6 2 5 2 7 3 6 1

[出力例(debug版)]

0 2 3 0 2 5 0 0 3 6 1

12 0 0 3 0 0 1 3 0 0 0

POSSIBLE

[入力例]

1 1 1 4 4 5 5 6 6 6 3 3 12 12

12 3 5 1 3 8 1 2 5 3 1 4 2 3 2

[出力例(debug版)]

1 3 1 0 0 0 1 2 5 3 1 1 2 3 2

13 0 4 11 0 1 0 0 0 0 0 2 0 0 0

POSSIBLE

■参照サイト
AtCoder Regular Contest 083

C++の練習を兼ねて, AtCoder Regular Contest 083 の 問題E (Bichrome Tree) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 083 の問題E (Bichrome Tree) を解いてみた.

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