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

C++の練習を兼ねて, AtCoder Grand Contest 001 の問題C（Shorten Diameter) を解いてみた.

■感想.
1. 問題C は, 解答の方針が, 全く見えなかったので, 解説を読んだうえで, おおよそ, このような内容を問われていたと推測してコーディングしている.
なお, 深さ優先探索の実装は, AtCoder Beginner Contest 070 (問題D Transit Tree Path) の解説が分かりやすかったので, これをベースに, コーディングしている.

本家のサイトAtCoder Grand Contest 001 Editorialをご覧下さい.

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

// 解き直し.
// AtCoder Grand Contest 001 Editorial
// http://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

const int limit = 2000;

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

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

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 v: 探索地点となる頂点.
// @param p: 探索地点から見て, 前回探索済の頂点.
// @param d: 開始地点からの距離.
// @return : 特に無し.
void dfs(int v, int p, int d) {
    depth[v] = d;
    for (auto &e : tree[v]) {
        if (e.to == p) continue;
        dfs(e.to, v, d + e.cost);
    }
}

int main() {
    
    // 1. 入力情報取得.
    int N, K;
    cin >> N >> K;
    
    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});
    }
    
    // 2. 木の直径Dを計算.
    int D = 0;
    FOR(i, 0, N) {
        depth[limit] = {};
        dfs(i, -1, 0);
        FOR(j, 0, N) D = max(D, depth[j]);
    }
    // cout << D << endl;
    
    // 3. 頂点 1 から 頂点 N まで, 木の直径(K) を使って, 削除必要数をカウント.
    // 3-1. 直径D が, すでにK以下の場合.
    int ans = N - 1;
    if(D <= K) {
        ans = 0;
        cout << ans << endl;
        return 0;
    }
    
    // 3-2. 直径が, 偶数の場合.
    // ex.
    // 7 3
    // 1 2
    // 2 3
    // 3 4
    // 4 5
    // 5 6
    // 6 7
    // -> 正解は, 3 のはずだが, 偶奇判定に, 直径D を使うと, 4 が出力されるので, K を使うように修正.
    // if(D % 2 == 0) {
    if(K % 2 == 0) {
        FOR(i, 0, N) {
            // 3-2-1. 初期化.
            int count = 0;
            depth[limit] = {};
            
            // 3-2-2. 頂点 i を中心と見立てて, 各頂点までの距離を取得.
            dfs(i, i, 0);
            // FOR(j, 0, N) cout << depth[j];
            
            // 3-2-3. 頂点 j からの距離が, K / 2 より大きい頂点をカウント.
            FOR(j, 0, N) if(depth[j] > K / 2) count++;
            // cout << " " << i << " " << count << endl;
            
            // 3-2-4. 最小値更新.
            ans = min(ans, count);
        }
    }
    
    // 3-3. 直径が, 奇数の場合.
    // if(D % 2 != 0) {
    if(K % 2 != 0) {
        FOR(ai, 0, N) {
            for(auto &e : tree[ai]) {
                // 3-3-1. 初期化.
                int count = 0;
                int depth1[N] = {};
                int depth2[N] = {};
                // 3-3-2. 辺 (ai - bi) を中心と見立てて, 各頂点までの距離を取得.
                // Access vector<structure> elements in a function, how?
                // https://cboard.cprogramming.com/cplusplus-programming/142505-access-vector-structure-elements-function-how.html
                int bi = e.to;
                // cout << bi << endl;
                depth[limit] = {};
                dfs(ai, ai, 0);
                FOR(j, 0, N) depth1[j] = depth[j];
                
                depth[limit] = {};
                dfs(bi, bi, 0);
                FOR(j, 0, N) depth2[j] = depth[j];
                
                depth[limit] = {};
                FOR(j, 0, N) depth[j] = min(depth1[j], depth2[j]);
                // FOR(j, 0, N) cout << depth[j];
                
                // 3-3-3. 頂点 j からの距離が, K / 2 より大きい頂点をカウント.
                FOR(j, 0, N) if(depth[j] > K / 2) count++;
                // cout << " ai=" << ai << " bi=" << bi << " " << count << endl;
                
                // 3-3-4. 最小値更新.
                ans = min(ans, count);
                
            }
        }
    }
    
    // 4. 出力.
    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

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

// 解き直し.

// AtCoder Grand Contest 001 Editorial

// http://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

const int limit = 2000;

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

struct edge {

int to; // 次の頂点.

int cost; // コスト.

};

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 v: 探索地点となる頂点.

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

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

// @return : 特に無し.

void dfs(int v, int p, int d) {

depth[v] = d;

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

if (e.to == p) continue;

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

}

int main() {

// 1. 入力情報取得.

int N, K;

cin >> N >> K;

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});

}

// 2. 木の直径Dを計算.

int D = 0;

FOR(i, 0, N) {

depth[limit] = {};

dfs(i, -1, 0);

FOR(j, 0, N) D = max(D, depth[j]);

}

// cout << D << endl;

// 3. 頂点 1 から頂点 N まで, 木の直径(K) を使って, 削除必要数をカウント.

// 3-1. 直径D が, すでにK以下の場合.

int ans = N - 1;

if(D <= K) {

ans = 0;

cout << ans << endl;

return 0;

}

// 3-2. 直径が, 偶数の場合.

// ex.

// 7 3

// 1 2

// 2 3

// 3 4

// 4 5

// 5 6

// 6 7

// -> 正解は, 3 のはずだが, 偶奇判定に, 直径D を使うと, 4 が出力されるので, K を使うように修正.

// if(D % 2 == 0) {

if(K % 2 == 0) {

FOR(i, 0, N) {

// 3-2-1. 初期化.

int count = 0;

depth[limit] = {};

// 3-2-2. 頂点 i を中心と見立てて, 各頂点までの距離を取得.

dfs(i, i, 0);

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

// 3-2-3. 頂点 j からの距離が, K / 2 より大きい頂点をカウント.

FOR(j, 0, N) if(depth[j] > K / 2) count++;

// cout << " " << i << " " << count << endl;

// 3-2-4. 最小値更新.

ans = min(ans, count);

}

// 3-3. 直径が, 奇数の場合.

// if(D % 2 != 0) {

if(K % 2 != 0) {

FOR(ai, 0, N) {

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

// 3-3-1. 初期化.

int count = 0;

int depth1[N] = {};

int depth2[N] = {};

// 3-3-2. 辺 (ai - bi) を中心と見立てて, 各頂点までの距離を取得.

// Access vector<structure> elements in a function, how?

// https://cboard.cprogramming.com/cplusplus-programming/142505-access-vector-structure-elements-function-how.html

int bi = e.to;

// cout << bi << endl;

depth[limit] = {};

dfs(ai, ai, 0);

FOR(j, 0, N) depth1[j] = depth[j];

depth[limit] = {};

dfs(bi, bi, 0);

FOR(j, 0, N) depth2[j] = depth[j];

depth[limit] = {};

FOR(j, 0, N) depth[j] = min(depth1[j], depth2[j]);

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

// 3-3-3. 頂点 j からの距離が, K / 2 より大きい頂点をカウント.

FOR(j, 0, N) if(depth[j] > K / 2) count++;

// cout << " ai=" << ai << " bi=" << bi << " " << count << endl;

// 3-3-4. 最小値更新.

ans = min(ans, count);

}

// 4. 出力.

cout << ans << endl;

return 0;

}

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

[出力例]
0

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

[出力例]
3

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

[出力例]
3

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

[出力例]
4

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

[出力例]
8
※辺 (3, 8) を中心と見ると, 頂点 1, 4, 7, 11, 12, 13, 14, 15 の 8頂点を削除すればよいため.

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

[出力例]
4
※頂点 3 を中心と見ると, 頂点 11, 12, 14, 15 の 4頂点を削除すればよいため.

[入力例]

9 5

1 2

3 2

4 2

4 5

4 6

6 7

6 8

8 9

[出力例]

[入力例]

9 3

1 2

3 2

4 2

4 5

4 6

6 7

6 8

8 9

[出力例]

[入力例]

7 3

1 2

2 3

3 4

4 5

5 6

6 7

[出力例]

[入力例]

9 2

1 2

1 3

1 4

1 5

2 6

3 7

4 8

5 9

[出力例]

[入力例]

15 3

1 2

2 3

2 4

3 5

3 6

3 8

6 7

8 9

8 10

10 11

11 12

6 13

13 14

13 15

[出力例]

※辺 (3, 8) を中心と見ると, 頂点 1, 4, 7, 11, 12, 13, 14, 15 の 8頂点を削除すればよいため.

[入力例]

15 4

1 2

2 3

2 4

3 5

3 6

3 8

6 7

8 9

8 10

10 11

11 12

6 13

13 14

13 15

[出力例]

※頂点 3 を中心と見ると, 頂点 11, 12, 14, 15 の 4頂点を削除すればよいため.

■参照サイト
AtCoder Grand Contest 001
ABC 070 解説

C++の練習を兼ねて, AtCoder Grand Contest 001 の 問題C（Shorten Diameter) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 001 の問題C（Shorten Diameter) を解いてみた.

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