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

C++の練習を兼ねて, AtCoder Regular Contest 030 の問題A (A – 閉路グラフ) ～問題B (B – ツリーグラフ) を解いてみた.

■感想.
1. 問題Bは, AtCoder Regular Contest 028 の問題C (C – 高橋王国の分割統治) に, 木dp の更新式が若干異なる感じで, 似ているように思った.
2. 木dp の訓練が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 出力.
    printf("%s\n", (K <= N / 2) ? "YES" : "NO");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N, K;

scanf("%d %d", &N, &K);

// 2. 出力.

printf("%s\n", (K <= N / 2) ? "YES" : "NO");

return 0;

}

[入力例]
6
2

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

[入力例]
3
2

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

[入力例]
11
6

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

[入力例]
11
5

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

[入力例]

[出力例]

YES

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

YES

※AtCoderのテストケースより

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

// C++14 (GCC 5.4.1)
#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 = 111;
int h[LIMIT];  // 宝石の情報.
int d[LIMIT];  // 頂点 x からの 距離 を 保存.
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, x, a, b;
    scanf("%d %d", &n, &x);
    x--;
    rep(i, n) scanf("%d", &h[i]);
    vvi G(n);
    rep(i, n - 1){
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 頂点 x から 各頂点までの距離を計算.
    bfs(G, x, d);
    
    // 3. 頂点 x から 遠い順 に並び替え.
    priority_queue<P> pq;
    rep(i, n) pq.push({d[i], i}); // {距離, 頂点番号}
    
    // 4. 木dp.
    while(!pq.empty()){
        // 4-1. 頂点 v を一つ取り出す.
        P p = pq.top();
        pq.pop();
        
        // 4-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 4-3. 頂点 v を 根とする部分木に含まれる 経路数 を 集計.
        for(auto &u : G[v]){
            // 頂点 v の 子頂点 に 相当する頂点 u を 選択.
            if(d[u] > d[v]){
                // 頂点 v の 周囲 の 頂点 u で, 頂点 x から, より遠いものを確認し, 子頂点 u までの経路数を加算.
                dp[v] += dp[u];
                // 子頂点 u を 根とする部分木 に 宝石が含まれる場合は, 1 を 加算.
                if(dp[u] || h[u]) dp[v]++;
            }
        }
    }
    // rep(i, n) printf("%d ", h[i]);
    // puts("");
    // rep(i, n) printf("%d ", dp[i]);
    // puts("");
    // rep(i, n) printf("%d ", d[i]);
    // puts("");
    
    // 5. 出力.
    printf("%d\n", dp[x] * 2);
    return 0;

}

100

101

102

103

// C++14 (GCC 5.4.1)

#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 = 111;

int h[LIMIT]; // 宝石の情報.

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

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, x, a, b;

scanf("%d %d", &n, &x);

x--;

rep(i, n) scanf("%d", &h[i]);

vvi G(n);

rep(i, n - 1){

scanf("%d %d", &a, &b);

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

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

bfs(G, x, d);

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

priority_queue<P> pq;

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

// 4. 木dp.

while(!pq.empty()){

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

P p = pq.top();

pq.pop();

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

int v = p.b;

// 4-3. 頂点 v を根とする部分木に含まれる経路数を集計.

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

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

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

// 頂点 v の周囲の頂点 u で, 頂点 x から, より遠いものを確認し, 子頂点 u までの経路数を加算.

dp[v] += dp[u];

// 子頂点 u を根とする部分木に宝石が含まれる場合は, 1 を加算.

if(dp[u] || h[u]) dp[v]++;

}

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

// puts("");

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

// puts("");

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

// puts("");

// 5. 出力.

printf("%d\n", dp[x] * 2);

return 0;

}

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

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

[入力例]
3 2
0 1 0
1 2
2 3

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

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

[出力例]
10

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

[出力例]
16

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

[出力例]
12

[入力例]

5 1

1 0 1 0 1

1 2

2 3

2 4

1 5

[出力例]

※AtCoderテストケースより

[入力例]

3 2

0 1 0

1 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

8 1

1 0 1 1 1 0 1 0

5 6

1 5

2 4

2 1

3 2

7 4

8 4

[出力例]

[入力例]

13 1

1 1 1 0 0 1 0 1 0 0 1 0 1

13 8

12 8

8 11

9 6

6 10

8 4

7 4

2 4

2 3

6 5

5 1

2 1

[出力例]

[入力例]

11 3

0 0 1 0 0 0 1 0 0 1 0

11 8

8 10

9 2

2 8

7 6

6 5

3 5

2 3

1 3

4 3

[出力例]

■参照サイト
AtCoder Regular Contest 030
AtCoder Regular Contest 028

C++の練習を兼ねて, AtCoder Regular Contest 030 の 問題A (A – 閉路グラフ) ～ 問題B (B – ツリーグラフ) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 030 の問題A (A – 閉路グラフ) ～問題B (B – ツリーグラフ) を解いてみた.

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