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

C++の練習を兼ねて, AtCoder Beginner Contest 239 の問題F (Construct Highway) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 場合分けが多く, 実装に苦労したものの, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc239/editorial/3388
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;
using vp = vector<P>;
using PQ = priority_queue<pair<int, vi>, vector<pair<int, vi>>, greater<pair<int, vi>>>;
#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[202020];

int main(){
    
    // 1. 入力情報.
    int N, M, t = 0;
    scanf("%d %d", &N, &M);
    rep(i, N){
        scanf("%d", &d[i]);
        t += d[i];
    }
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        --a;
        --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. グラフが木となるか？
    if(t != 2 * N - 2){
        puts("-1");
        return 0;
    }
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    };
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 4. 各連結成分ごとに, 不足次数で分ける.
    PQ pq;
    queue<int> q;
    vvi s(idx + 1);
    int lack[idx + 1], lackSum = 0;
    repx(i, 1, idx + 1) lack[i] = 0;
    rep(i, N) lack[c[i]] += (d[i] - G[i].size());
    rep(i, N){
        int res = d[i] - G[i].size();
        rep(_, res) s[c[i]].pb(i);
    }
    repx(i, 1, idx + 1){
        // 次数 1 不足.
        if(lack[i] == 1) q.push(s[i][0]);
        
        // 次数 2以上 不足.
        if(lack[i] > 1) pq.push({s[i].size(), s[i]});
        
        // 不足分合計.
        lackSum += lack[i];
    }
    
    // 5. 例外(不足分なし).
    // -> 出力なしのケース.
    if(lackSum == 0){
        puts("");
        return 0;
    }
    
    // 6. 例外(不足分あり).
    // -> 不足次数の合計を確認.
    //    random_21.txt で, WA版 となったため, ロジック修正.
    if(2 * idx - 2 != lackSum){
        puts("-1");
        return 0;
    }
    
    // 7. 操作.
    vp ans;
    while(!pq.empty()){
        auto p = pq.top();
        pq.pop();
        int n = p.b.size();
        rep(i, n){
            // 次数 1 不足 に 追加.
            if(i == n - 1){
                q.push(p.b.back());
                break;
            }
            
            // 辺を追加.
            if(!q.empty()){
                int v = q.front();
                q.pop();
                ans.pb({p.b[i], v});
            }
        }
    }
    
    // 8. 出力.
    if(q.size() != 2) puts("-1");
    if(q.size() == 2){
        int u = q.front();
        q.pop();
        int v = q.front();
        ans.pb({u, v});
        for(auto &p : ans) printf("%d %d\n", p.a + 1, p.b + 1);
    }
    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

139

140

// 解き直し.

// https://atcoder.jp/contests/abc239/editorial/3388

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using vp = vector<P>;

using PQ = priority_queue<pair<int, vi>, vector<pair<int, vi>>, greater<pair<int, vi>>>;

#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[202020];

int main(){

// 1. 入力情報.

int N, M, t = 0;

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

rep(i, N){

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

t += d[i];

}

vvi G(N);

rep(i, M){

int a, b;

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

--a;

--b;

G[a].pb(b);

G[b].pb(a);

}

// 2. グラフが木となるか？

if(t != 2 * N - 2){

puts("-1");

return 0;

}

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

// 連結成分番号を設定.

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);

}

};

int c[N], idx = 0;

rep(i, N) c[i] = 0;

rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);

// 4. 各連結成分ごとに, 不足次数で分ける.

PQ pq;

queue<int> q;

vvi s(idx + 1);

int lack[idx + 1], lackSum = 0;

repx(i, 1, idx + 1) lack[i] = 0;

rep(i, N) lack[c[i]] += (d[i] - G[i].size());

rep(i, N){

int res = d[i] - G[i].size();

rep(_, res) s[c[i]].pb(i);

}

repx(i, 1, idx + 1){

// 次数 1 不足.

if(lack[i] == 1) q.push(s[i][0]);

// 次数 2以上不足.

if(lack[i] > 1) pq.push({s[i].size(), s[i]});

// 不足分合計.

lackSum += lack[i];

}

// 5. 例外(不足分なし).

// -> 出力なしのケース.

if(lackSum == 0){

puts("");

return 0;

}

// 6. 例外(不足分あり).

// -> 不足次数の合計を確認.

// random_21.txt で, WA版となったため, ロジック修正.

if(2 * idx - 2 != lackSum){

puts("-1");

return 0;

}

// 7. 操作.

vp ans;

while(!pq.empty()){

auto p = pq.top();

pq.pop();

int n = p.b.size();

rep(i, n){

// 次数 1 不足に追加.

if(i == n - 1){

q.push(p.b.back());

break;

}

// 辺を追加.

if(!q.empty()){

int v = q.front();

q.pop();

ans.pb({p.b[i], v});

}

// 8. 出力.

if(q.size() != 2) puts("-1");

if(q.size() == 2){

int u = q.front();

q.pop();

int v = q.front();

ans.pb({u, v});

for(auto &p : ans) printf("%d %d\n", p.a + 1, p.b + 1);

}

return 0;

}

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

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

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

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

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

[入力例]
4 0
3 3 3 3

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

[入力例]
2 1
1 1
1 2

[出力例]


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

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

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

[出力例]
1 2
3 4

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

[出力例]
1 11
3 12
5 7
6 8
9 10
6 9

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

[出力例]
6 2
1 5
1 7
6 1

[入力例]
20 7
6 2 1 3 2 1 1 1 1 5 1 1 1 1 2 5 1 1 1 1
1 2
1 3
16 17
4 5
10 11
1 5
10 13

[出力例]
15 6
10 7
10 8
16 9
16 12
16 14
1 18
1 19
1 20
2 15
4 10
16 4

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

6 2

1 2 1 2 2 2

2 3

1 4

[出力例]

6 2

5 6

4 5

※AtCoderテストケースより

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

5 4

6 2

5 6

[入力例]

5 1

1 1 1 1 4

2 3

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 0

3 3 3 3

[出力例]

-1

※AtCoderテストケースより

[入力例]

2 1

1 1

1 2

[出力例]

[入力例]

5 0

1 1 2 2 2

[出力例]

3 1

4 2

5 3

4 5

[入力例]

5 2

2 1 1 2 2

1 5

4 5

[出力例]

1 2

3 4

[入力例]

12 5

2 2 2 2 2 2 2 2 2 2 1 1

1 7

2 8

2 3

4 5

4 10

[出力例]

1 11

3 12

5 7

6 8

9 10

6 9

[入力例]

8 3

5 2 1 1 1 2 1 1

1 3

1 4

2 8

[出力例]

6 2

1 5

1 7

6 1

[入力例]

20 7

6 2 1 3 2 1 1 1 1 5 1 1 1 1 2 5 1 1 1 1

1 2

1 3

16 17

4 5

10 11

1 5

10 13

[出力例]

15 6

10 7

10 8

16 9

16 12

16 14

1 18

1 19

1 20

2 15

4 10

16 4

■参照サイト
デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）

C++の練習を兼ねて, AtCoder Beginner Contest 239 の 問題F (Construct Highway) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 239 の問題F (Construct Highway) を解いてみた.

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