C++ の動作確認をしてみた（３５７）

C++の練習を兼ねて, AtCoder Beginner Contest 040 の問題C (柱柱柱柱柱) ～問題D (道路の老朽化対策について) を解いてみた.

■感想.
1. 解説見る前に, AC版に到達できたので良かったと思う.
2. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
LL a[101010], dp[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. コストの最小値を計算.
    repx(i, 1, N) dp[i] = 202020202020202020;
    rep(i, N){
        // 2-1. 1個右の柱に移動.
        if(i + 1 < N) dp[i + 1] = min(dp[i + 1], dp[i] + abs(a[i + 1] - a[i]));
        
        // 2-2. 2個右の柱に移動.
        if(i + 2 < N) dp[i + 2] = min(dp[i + 2], dp[i] + abs(a[i + 2] - a[i]));
    }
    
    // 3. 出力.
    printf("%lld\n", dp[N - 1]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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--)

LL a[101010], dp[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld", &a[i]);

// 2. コストの最小値を計算.

repx(i, 1, N) dp[i] = 202020202020202020;

rep(i, N){

// 2-1. 1個右の柱に移動.

if(i + 1 < N) dp[i + 1] = min(dp[i + 1], dp[i] + abs(a[i + 1] - a[i]));

// 2-2. 2個右の柱に移動.

if(i + 2 < N) dp[i + 2] = min(dp[i + 2], dp[i] + abs(a[i + 2] - a[i]));

}

// 3. 出力.

printf("%lld\n", dp[N - 1]);

return 0;

}

[入力例]
4
100 150 130 120

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

[入力例]
4
100 125 80 110

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

[入力例]
9
314 159 265 358 979 323 846 264 338

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

[入力例]
100
5108 373 5586 756 4232 7998 9644 7666 7618 2493 1019 3452 6911 3189 8458 4914 1885 2976 1724 6021 5853 1949 3998 6659 2915 4656 875 7980 5099 5453 3358 8288 8087 8674 1483 527 5883 1283 3877 7769 2552 1152 6994 5658 6804 3119 9864 8178 6059 8881 2919 6144 9754 4533 3602 2371 6238 169 6045 7363 8307 3373 9545 1461 2672 4387 9231 7881 4913 6547 6038 5708 3535 2905 7760 9702 4603 8888 3822 9551 3235 6202 1093 9554 8676 5770 1179 4802 8565 7819 1439 7579 6445 7612 9376 3631 2638 6779 2974 2512

[出力例]
108362

[入力例]

100 150 130 120

[出力例]

※AtCoderテストケースより

[入力例]

100 125 80 110

[出力例]

※AtCoderテストケースより

[入力例]

314 159 265 358 979 323 846 264 338

[出力例]

310

※AtCoderテストケースより

[入力例]

100

5108 373 5586 756 4232 7998 9644 7666 7618 2493 1019 3452 6911 3189 8458 4914 1885 2976 1724 6021 5853 1949 3998 6659 2915 4656 875 7980 5099 5453 3358 8288 8087 8674 1483 527 5883 1283 3877 7769 2552 1152 6994 5658 6804 3119 9864 8178 6059 8881 2919 6144 9754 4533 3602 2371 6238 169 6045 7363 8307 3373 9545 1461 2672 4387 9231 7881 4913 6547 6038 5708 3535 2905 7760 9702 4603 8888 3822 9551 3235 6202 1093 9554 8676 5770 1179 4802 8565 7819 1439 7579 6445 7612 9376 3631 2638 6779 2974 2512

[出力例]

108362

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

// コメントを修正して, 再提出.
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using T3 = tuple<int, 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 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{
    vector<int> 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, M;
    scanf("%d %d", &N, &M);
    vector<T3> G;
    rep(i, M){
        int a, b, y;
        scanf("%d %d %d", &a, &b, &y);
        a--, b--;
        G.emplace_back(a, b, y);
    }
    
    // 2. クエリ情報.
    int Q;
    priority_queue<P> pq;
    scanf("%d", &Q);
    int v[Q], w[Q];
    rep(i, Q){
        scanf("%d %d", &v[i], &w[i]);
        v[i]--;
        pq.push({w[i], v[i]});
    }
    
    // 3. sort.
    // https://www.geeksforgeeks.org/sorting-vector-tuple-c-ascending-order/
    sort(all(G), [](const T3 &a, const T3 &b){
        return get<2>(a) > get<2>(b);
    });
    
    // 4. 新しい道路から, Union-Find木に, 順次追加.
    UnionFind uf(N);
    int idx = 0, cur;
    map<P, int> cities;
    while(!pq.empty()){
        // 4-1. 国民の情報を取得.
        P p = pq.top();
        pq.pop();
        
        // 4-2. 行き来可能な都市の個数を把握.
        repx(i, idx, M){
            // 都市情報を取得.
            int a = get<0>(G[i]);
            int b = get<1>(G[i]);
            int y = get<2>(G[i]);
            
            // p.a年より新しい場合は, 追加.
            if(p.a < y) uf.unite(a, b);
            
            // p.a年以前の場合は, 終了.
            if(p.a >= y){
                cur = i;
                break;
            }
        }
        
        // 4-3. 都市の個数を保存.
        // -> 都市 p.b に住んでいて, p.a年より新しい道路を使うケース.
        cities[{p.b, p.a}] = uf.size(p.b);
        
        // 4-4. idx更新.
        idx = cur;
    }
    
    // 5. 出力.
    rep(i, Q) printf("%d\n", cities[{v[i], w[i]}]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// コメントを修正して, 再提出.

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

vector<int> 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, M;

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

vector<T3> G;

rep(i, M){

int a, b, y;

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

a--, b--;

G.emplace_back(a, b, y);

}

// 2. クエリ情報.

int Q;

priority_queue<P> pq;

scanf("%d", &Q);

int v[Q], w[Q];

rep(i, Q){

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

v[i]--;

pq.push({w[i], v[i]});

}

// 3. sort.

// https://www.geeksforgeeks.org/sorting-vector-tuple-c-ascending-order/

sort(all(G), [](const T3 &a, const T3 &b){

return get<2>(a) > get<2>(b);

});

// 4. 新しい道路から, Union-Find木に, 順次追加.

UnionFind uf(N);

int idx = 0, cur;

map<P, int> cities;

while(!pq.empty()){

// 4-1. 国民の情報を取得.

P p = pq.top();

pq.pop();

// 4-2. 行き来可能な都市の個数を把握.

repx(i, idx, M){

// 都市情報を取得.

int a = get<0>(G[i]);

int b = get<1>(G[i]);

int y = get<2>(G[i]);

// p.a年より新しい場合は, 追加.

if(p.a < y) uf.unite(a, b);

// p.a年以前の場合は, 終了.

if(p.a >= y){

cur = i;

break;

}

// 4-3. 都市の個数を保存.

// -> 都市 p.b に住んでいて, p.a年より新しい道路を使うケース.

cities[{p.b, p.a}] = uf.size(p.b);

// 4-4. idx更新.

idx = cur;

}

// 5. 出力.

rep(i, Q) printf("%d\n", cities[{v[i], w[i]}]);

return 0;

}

[入力例]
5 4
1 2 2000
2 3 2004
3 4 1999
4 5 2001
3
1 2000
1 1999
3 1995

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

[入力例]
4 5
1 2 2005
3 1 2001
3 4 2002
1 4 2004
4 2 2003
5
1 2003
2 2003
1 2001
3 2003
4 2004

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

[入力例]
4 5
1 2 10
1 2 1000
2 3 10000
2 3 100000
3 1 200000
4
1 0
2 10000
3 100000
4 0

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

[入力例]
15 16
1 2 2020
2 4 2012
4 5 2014
1 3 2015
5 4 2016
1 3 2005
5 3 2008
9 6 2016
6 7 2008
7 9 2019
9 11 1999
10 9 2001
10 11 2017
12 13 2013
13 15 2020
14 12 2018
10
1 2019
2 2011
3 2014
8 2020
12 2012
9 2015
11 1998
10 2000
5 2012
15 2019

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

100

[入力例]

5 4

1 2 2000

2 3 2004

3 4 1999

4 5 2001

1 2000

1 1999

3 1995

[出力例]

※AtCoderテストケースより

[入力例]

4 5

1 2 2005

3 1 2001

3 4 2002

1 4 2004

4 2 2003

1 2003

2 2003

1 2001

3 2003

4 2004

[出力例]

※AtCoderテストケースより

[入力例]

4 5

1 2 10

1 2 1000

2 3 10000

2 3 100000

3 1 200000

1 0

2 10000

3 100000

4 0

[出力例]

※AtCoderテストケースより

[入力例]

15 16

1 2 2020

2 4 2012

4 5 2014

1 3 2015

5 4 2016

1 3 2005

5 3 2008

9 6 2016

6 7 2008

7 9 2019

9 11 1999

10 9 2001

10 11 2017

12 13 2013

13 15 2020

14 12 2018

1 2019

2 2011

3 2014

8 2020

12 2012

9 2015

11 1998

10 2000

5 2012

15 2019

[出力例]

■参照サイト
AtCoder Beginner Contest 040
Union-Find木

C++の練習を兼ねて, AtCoder Beginner Contest 040 の 問題C (柱柱柱柱柱) ～ 問題D (道路の老朽化対策について) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 040 の問題C (柱柱柱柱柱) ～問題D (道路の老朽化対策について) を解いてみた.

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