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

C++の練習を兼ねて, AtCoder Beginner Contest 036 の問題D（塗り絵) を解いてみた.

■感想.
1. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
但し, おおよそ, このような内容を解答で説明されているだろう, との推測が多分に含まれていると思われる.
2. なお, 深さ優先探索の実装は, AtCoder Beginner Contest 070 (問題D Transit Tree Path) の解説が分かりやすかったので, 改めて, これをベースとしている.

本家のサイトABC #036 解説をご覧下さい.

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

// 解き直し.
// ABC #036 解説.
// http://abc036.contest.atcoder.jp/data/abc/036/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

typedef long long LL;
const int LIMIT = 100000;
const LL MOD = 1e9 + 7;

struct edge {
    int to;    // 次の頂点.
    int cost;  // コスト.
};

struct vertex {
    int id;        // 頂点番号.
    int distance;  // 指定された頂点(根)からの距離.
};

int depth[LIMIT];
vector<edge> tree[LIMIT];

// AtCoder Beginner Contest 070 (問題D Transit Tree Path) を参照.
// https://img.atcoder.jp/abc070/editorial.pdf
// 深さ優先探索(depth-first search).
// @param c: 探索地点となる頂点.
// @param b: 探索地点から見て, 前回探索済の頂点.
// @param d: 探索開始地点からの距離.
// @return : 特に無し.
void dfs(int c, int b, int d) {
    depth[c] = d;
    for (auto &e : tree[c]) {
        if (e.to == b) continue;
        dfs(e.to, c, d + e.cost);
    }
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    map<int, int> m; // 開始頂点取得用.
    FOR(i, 0, N - 1) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        tree[a].push_back({b, 1});
        tree[b].push_back({a, 1});
        m[a]++;
        m[b]++;
    }
    
    // 2. 探索開始の頂点(根)を取得し, 各頂点までの最短距離を保存.
    int root = -1;
    for(auto &p : m) {
        if(p.second == 1) {
            root = p.first;
            break;
        }
    }
    dfs(root, -1, 0);
    // cout << "root=" << root << endl;
    // FOR(i, 0, N) for(auto &p : tree[i]) cout << "i=" << i << " to=" << p.to << endl;
    // FOR(i, 0, N) cout << depth[i] << " ";
    
    // 3. 解説通り(色の塗り方の数をカウント).
    // -> tree DP を 使って解くとのこと.
    // 探索開始の頂点(根) から遠い順に, f, g の 値を計算していく.
    
    // 3-1. 頂点と距離のセットで保管.
    vector<vertex> vertexes;
    FOR(i, 0, N) {
        vertex v;
        v.id = i;
        v.distance = depth[i];
        vertexes.push_back(v);
    }
    
    // 3-2. 距離で, 降順sort.
    sort(vertexes.begin(), vertexes.end(), [](const vertex& x, const vertex& y) {return x.distance > y.distance;});
    
    // 3-3. f, g を 帰納的に計算.
    LL f[N] = {};
    LL g[N] = {};
    for(auto &x : vertexes) {
        // 頂点 x を 親とする部分木で, x と 隣り合っている頂点(xの子)を探索.
        int p = x.id;  // 親の頂点番号.
        LL lf = 1LL;
        LL lg = 1LL;
        // 隣接している, かつ, 探索開始の頂点(根) からより遠い場合は, xの子 と識別.
        for(auto &v : tree[p]) {
            int c = v.to;  // 子の候補となる頂点番号.
            if(depth[p] < depth[c]) {
                lg *= f[c];
                lf *= g[c];
                lg %= MOD;
                lf %= MOD;
            }
        }
        // f, g を 更新.
        lf += lg;
        lf %= MOD;
        f[p] = lf;
        g[p] = lg;
    }
    // FOR(i, 0, N) cout << f[i] << " ";
    // cout << endl;
    // FOR(i, 0, N) cout << g[i] << " ";
    
    // 4. 出力 ～ 後処理.
    LL ans = f[root];
    cout << ans << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

// 解き直し.

// ABC #036 解説.

// http://abc036.contest.atcoder.jp/data/abc/036/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

typedef long long LL;

const int LIMIT = 100000;

const LL MOD = 1e9 + 7;

struct edge {

int to; // 次の頂点.

int cost; // コスト.

};

struct vertex {

int id; // 頂点番号.

int distance; // 指定された頂点(根)からの距離.

};

int depth[LIMIT];

vector<edge> tree[LIMIT];

// AtCoder Beginner Contest 070 (問題D Transit Tree Path) を参照.

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

// 深さ優先探索(depth-first search).

// @param c: 探索地点となる頂点.

// @param b: 探索地点から見て, 前回探索済の頂点.

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

// @return : 特に無し.

void dfs(int c, int b, int d) {

depth[c] = d;

for (auto &e : tree[c]) {

if (e.to == b) continue;

dfs(e.to, c, d + e.cost);

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

map<int, int> m; // 開始頂点取得用.

FOR(i, 0, N - 1) {

int a, b;

cin >> a >> b;

a--, b--;

tree[a].push_back({b, 1});

tree[b].push_back({a, 1});

m[a]++;

m[b]++;

}

// 2. 探索開始の頂点(根)を取得し, 各頂点までの最短距離を保存.

int root = -1;

for(auto &p : m) {

if(p.second == 1) {

root = p.first;

break;

}

dfs(root, -1, 0);

// cout << "root=" << root << endl;

// FOR(i, 0, N) for(auto &p : tree[i]) cout << "i=" << i << " to=" << p.to << endl;

// FOR(i, 0, N) cout << depth[i] << " ";

// 3. 解説通り(色の塗り方の数をカウント).

// -> tree DP を使って解くとのこと.

// 探索開始の頂点(根) から遠い順に, f, g の値を計算していく.

// 3-1. 頂点と距離のセットで保管.

vector<vertex> vertexes;

FOR(i, 0, N) {

vertex v;

v.id = i;

v.distance = depth[i];

vertexes.push_back(v);

}

// 3-2. 距離で, 降順sort.

sort(vertexes.begin(), vertexes.end(), [](const vertex& x, const vertex& y) {return x.distance > y.distance;});

// 3-3. f, g を帰納的に計算.

LL f[N] = {};

LL g[N] = {};

for(auto &x : vertexes) {

// 頂点 x を親とする部分木で, x と隣り合っている頂点(xの子)を探索.

int p = x.id; // 親の頂点番号.

LL lf = 1LL;

LL lg = 1LL;

// 隣接している, かつ, 探索開始の頂点(根) からより遠い場合は, xの子と識別.

for(auto &v : tree[p]) {

int c = v.to; // 子の候補となる頂点番号.

if(depth[p] < depth[c]) {

lg *= f[c];

lf *= g[c];

lg %= MOD;

lf %= MOD;

}

// f, g を更新.

lf += lg;

lf %= MOD;

f[p] = lf;

g[p] = lg;

}

// FOR(i, 0, N) cout << f[i] << " ";

// cout << endl;

// FOR(i, 0, N) cout << g[i] << " ";

// 4. 出力～後処理.

LL ans = f[root];

cout << ans << endl;

return 0;

}

[入力例]
2
1 2

[出力例]
3

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

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

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

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

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

[出力例]
157

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

[出力例]
415
-> 下図の頂点⑩で, f（⑩） = 415 であることからも分かる.

[入力例]

1 2

[出力例]

[入力例]

2 5

1 5

2 4

3 2

[出力例]

※AtCoderテストケースより

[入力例]

7 9

8 1

9 6

10 8

8 6

10 3

5 8

4 8

2 5

[出力例]

192

※AtCoderテストケースより

[入力例]

9 2

2 3

3 1

1 5

3 7

7 4

7 8

8 6

6 10

[出力例]

157

[入力例]

9 2

2 3

3 1

1 5

3 7

7 4

7 8

8 6

6 10

12 9

5 11

[出力例]

415

-> 下図の頂点⑩で, f（⑩） = 415 であることからも分かる.

■参照サイト
AtCoder Beginner Contest 036

C++の練習を兼ねて, AtCoder Beginner Contest 036 の 問題D（塗り絵) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 036 の問題D（塗り絵) を解いてみた.

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