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

C++の練習を兼ねて, AtCoder Regular Contest 076 の問題D (Built?) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Regular Contest 076 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/arc076/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using P = pair<int, int>;
using vp = vector<P>;
using T3 = tuple<LL, 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
#define all(x) x.begin(), x.end()

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp cxy, cyx;
    map<P, int> m;
    rep(i, N){
        int x, y;
        scanf("%d %d", &x, &y);
        
        // 街情報(座標).
        cxy.pb({x, y});
        cyx.pb({y, x});
        
        // 街情報(番号).
        m[{x, y}] = i;
    }
    
    // 2. sort.
    // 2-1. X座標ソート.
    sort(all(cxy));
    
    // 2-2. Y座標ソート.
    sort(all(cyx));
    
    // 3. グラフ情報.
    // 3-1. X座標ソート版.
    vector<T3> t;
    rep(i, N - 1){
        // 出発地点.
        int sx = cxy[i].a;
        int sy = cxy[i].b;
        int sn = m[{sx, sy}];
        
        // 到着地点.
        int gx = cxy[i + 1].a;
        int gy = cxy[i + 1].b;
        int gn = m[{gx, gy}];
        
        // コスト.
        LL c = (LL)min(abs(sx - gx), abs(sy - gy));
        
        // 保存.
        t.emplace_back(c, sn, gn);
    }
    
    // 3-2. Y座標ソート版.
    rep(i, N - 1){
        // 出発地点.
        int sx = cyx[i].a;
        int sy = cyx[i].b;
        int sn = m[{sy, sx}];
        
        // 到着地点.
        int gx = cyx[i + 1].a;
        int gy = cyx[i + 1].b;
        int gn = m[{gy, gx}];
        
        // コスト.
        LL c = (LL)min(abs(sx - gx), abs(sy - gy));
        
        // 保存.
        t.emplace_back(c, sn, gn);
    }
    
    // 4. sort.
    sort(all(t));
    
    // 5. 最小全域木(Kruskal's Algorithm) の 構築.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    LL ans = 0;
    UnionFind uf(2 * N);
    rep(i, t.size()){
        // グラフ情報.
        int u = get<1>(t[i]);
        int v = get<2>(t[i]);
        LL c = get<0>(t[i]);
        
        // 最小全域木を構成する辺の追加, コスト計算.
        if(!uf.same(u, v)){
            uf.unite(u, v);
            ans += c;
        }
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using P = pair<int, int>;

using vp = vector<P>;

using T3 = tuple<LL, 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

#define all(x) x.begin(), x.end()

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp cxy, cyx;

map<P, int> m;

rep(i, N){

int x, y;

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

// 街情報(座標).

cxy.pb({x, y});

cyx.pb({y, x});

// 街情報(番号).

m[{x, y}] = i;

}

// 2. sort.

// 2-1. X座標ソート.

sort(all(cxy));

// 2-2. Y座標ソート.

sort(all(cyx));

// 3. グラフ情報.

// 3-1. X座標ソート版.

vector<T3> t;

rep(i, N - 1){

// 出発地点.

int sx = cxy[i].a;

int sy = cxy[i].b;

int sn = m[{sx, sy}];

// 到着地点.

int gx = cxy[i + 1].a;

int gy = cxy[i + 1].b;

int gn = m[{gx, gy}];

// コスト.

LL c = (LL)min(abs(sx - gx), abs(sy - gy));

// 保存.

t.emplace_back(c, sn, gn);

}

// 3-2. Y座標ソート版.

rep(i, N - 1){

// 出発地点.

int sx = cyx[i].a;

int sy = cyx[i].b;

int sn = m[{sy, sx}];

// 到着地点.

int gx = cyx[i + 1].a;

int gy = cyx[i + 1].b;

int gn = m[{gy, gx}];

// コスト.

LL c = (LL)min(abs(sx - gx), abs(sy - gy));

// 保存.

t.emplace_back(c, sn, gn);

}

// 4. sort.

sort(all(t));

// 5. 最小全域木(Kruskal's Algorithm) の構築.

// 競プロ典型 90 問 (049 - Flip Digits 2)

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp

LL ans = 0;

UnionFind uf(2 * N);

rep(i, t.size()){

// グラフ情報.

int u = get<1>(t[i]);

int v = get<2>(t[i]);

LL c = get<0>(t[i]);

// 最小全域木を構成する辺の追加, コスト計算.

if(!uf.same(u, v)){

uf.unite(u, v);

ans += c;

}

// 6. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
3
1 5
3 9
7 8

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

[入力例]
6
8 3
4 9
12 19
18 1
13 5
7 6

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

[入力例]
5
1 3
5 8
10 3
11 1
6 2

[出力例]
3

[入力例]
7
26 21
10 5
13 1
10 15
21 8
13 31
31 21

[出力例]
11

[入力例]
15
77 61
109 11
70 122
56 31
60 78
39 105
119 36
27 111
50 94
61 80
89 36
65 51
122 117
92 63
70 98

[出力例]
53

[入力例]
33
535841 392830
886700 439965
980165 242002
378567 1221215
718227 1116388
934737 507531
1177697 811662
1025786 532997
49250 130344
265694 220194
303104 128236
1016944 846327
210484 186383
1177345 96975
696687 122028
844685 896757
406707 69786
179549 172311
982700 1013573
908740 937724
568591 807355
649431 707575
911233 87617
169621 162873
562404 419802
560962 400670
827597 836935
746791 45279
242558 344460
547802 479310
791097 1131673
573639 1094305
1228744 350660

[出力例]
480000

100

101

102

103

104

105

106

[入力例]

1 5

3 9

7 8

[出力例]

※AtCoderテストケースより

[入力例]

8 3

4 9

12 19

18 1

13 5

7 6

[出力例]

※AtCoderテストケースより

[入力例]

1 3

5 8

10 3

11 1

6 2

[出力例]

[入力例]

26 21

10 5

13 1

10 15

21 8

13 31

31 21

[出力例]

[入力例]

77 61

109 11

70 122

56 31

60 78

39 105

119 36

27 111

50 94

61 80

89 36

65 51

122 117

92 63

70 98

[出力例]

[入力例]

535841 392830

886700 439965

980165 242002

378567 1221215

718227 1116388

934737 507531

1177697 811662

1025786 532997

49250 130344

265694 220194

303104 128236

1016944 846327

210484 186383

1177345 96975

696687 122028

844685 896757

406707 69786

179549 172311

982700 1013573

908740 937724

568591 807355

649431 707575

911233 87617

169621 162873

562404 419802

560962 400670

827597 836935

746791 45279

242558 344460

547802 479310

791097 1131673

573639 1094305

1228744 350660

[出力例]

480000

■参照サイト
AtCoder Regular Contest 076
Union-Find木
 競プロ典型 90 問の問題049

C++の練習を兼ねて, AtCoder Regular Contest 076 の 問題D (Built?) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 076 の問題D (Built?) を解いてみた.

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