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

C++の練習を兼ねて, AtCoder Beginner Contest 299 の問題E (Nearest Black Vertex) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 299 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc299/editorial/6249
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;
using vp = vector<P>;
#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 a first
#define b second
#define pb push_back
int duv[2020][2020];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    scanf("%d", &K);
    vp c;
    rep(i, K){
        int p, d;
        scanf("%d %d", &p, &d);
        --p;
        c.pb({p, d});
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキューに追加.
        q.push(s);
        
        // キューを処理.
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &v : G[u]) if(!duv[s][v] && v != s) duv[s][v] = duv[s][u] + 1, q.push(v);
        }
    };
    
    // 3. 全探索.
    rep(i, N) bfs(G, i);
    /*
    rep(i, N){
        rep(j, N) printf("%d ", duv[i][j]);
        puts("");
    }
    */
    
    // 4. 頂点彩色.
    // -> いずれかの頂点 p[i] で, 距離が d[i] 未満 の 頂点を, 白で塗っていく.
    string ans(N, '1');
    for(auto &x : c){
        int p = x.a;
        int d = x.b;
        rep(i, N) if(duv[p][i] < d) ans[i] = '0';
    }
    
    // 5. 判定.
    // 5-1. 条件 1.
    bool b1 = false;
    rep(i, N) b1 |= (ans[i] - '0');
    
    // 5-2. 条件 2.
    bool b2 = true;
    for(auto &x : c){
        int p = x.a;
        int d = x.b;
        int dMin = 2020202020;
        rep(i, N) if(ans[i] == '1' && duv[p][i] < dMin) dMin = duv[p][i];
        if(d != dMin) b2 = false;
    }
    
    // 6. 出力.
    if(b1 && b2) printf("%s\n%s\n", "Yes", ans.c_str());
    else         puts("No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc299/editorial/6249

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using vp = vector<P>;

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

#define b second

#define pb push_back

int duv[2020][2020];

int main(){

// 1. 入力情報.

int N, M, K;

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

vvi G(N);

rep(i, M){

int u, v;

scanf("%d %d", &u, &v);

--u, --v;

G[u].pb(v);

G[v].pb(u);

}

scanf("%d", &K);

vp c;

rep(i, K){

int p, d;

scanf("%d %d", &p, &d);

--p;

c.pb({p, d});

}

// 2. bfs.

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

auto bfs = [&](vvi &G, int s){

// 空のキュー.

queue<int> q;

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

q.push(s);

// キューを処理.

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &v : G[u]) if(!duv[s][v] && v != s) duv[s][v] = duv[s][u] + 1, q.push(v);

}

};

// 3. 全探索.

rep(i, N) bfs(G, i);

rep(i, N){

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

puts("");

}

// 4. 頂点彩色.

// -> いずれかの頂点 p[i] で, 距離が d[i] 未満の頂点を, 白で塗っていく.

string ans(N, '1');

for(auto &x : c){

int p = x.a;

int d = x.b;

rep(i, N) if(duv[p][i] < d) ans[i] = '0';

}

// 5. 判定.

// 5-1. 条件 1.

bool b1 = false;

rep(i, N) b1 |= (ans[i] - '0');

// 5-2. 条件 2.

bool b2 = true;

for(auto &x : c){

int p = x.a;

int d = x.b;

int dMin = 2020202020;

rep(i, N) if(ans[i] == '1' && duv[p][i] < dMin) dMin = duv[p][i];

if(d != dMin) b2 = false;

}

// 6. 出力.

if(b1 && b2) printf("%s\n%s\n", "Yes", ans.c_str());

else puts("No");

return 0;

}

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

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
Yes
11100

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

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

[入力例]
1 0
0

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

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

[出力例]
Yes
010

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

[出力例]
Yes
0100100

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

[出力例]
Yes
101011010110101

100

101

102

103

104

105

106

107

108

109

110

[入力例]

5 5

1 2

2 3

3 1

3 4

4 5

1 0

5 2

[出力例]

Yes

10100

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

Yes

11100

[入力例]

5 5

1 2

2 3

3 1

3 4

4 5

1 1

2 1

3 1

4 1

5 1

[出力例]

※AtCoderテストケースより

[入力例]

1 0

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 2

1 2

2 3

1 1

2 0

3 1

[出力例]

Yes

010

[入力例]

7 7

1 2

2 3

3 1

4 3

6 1

5 1

7 6

1 1

3 1

4 2

5 0

6 2

[出力例]

Yes

0100100

[入力例]

15 15

6 1

2 1

2 4

2 5

12 4

11 4

5 10

5 13

10 13

3 1

3 7

3 8

8 9

14 9

15 9

2 1

5 0

7 1

9 1

11 0

12 2

14 2

15 0

[出力例]

Yes

101011010110101

■参照サイト
東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 299）

C++の練習を兼ねて, AtCoder Beginner Contest 299 の 問題E (Nearest Black Vertex) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 299 の問題E (Nearest Black Vertex) を解いてみた.

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