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

C++の練習を兼ねて, AtCoder Regular Contest 105 の問題C (Camels and Bridge) を解いてみた.

■感想.
1. 問題C は, 解答方針が見えなかったので, 解説を参考に実装したところ, 何とかAC版に到達できた.
2. グラフの最長路を求める部分は, Warshall–Floyd法の簡易版をイメージした実装で対応した.
3. 実装に, 非常に苦労したものの, いろいろな情報が整理出来たので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc105/editorial/170
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
#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 all(x) x.begin(), x.end()
LL cW[11], bL[101010], bV[101010];

struct bridge{
    LL l, v; // 長さ, 耐荷重.
    bool operator < (const bridge& rhs) const{
        return (v != rhs.v) ? (v > rhs.v) : (l < rhs.l);
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    LL maxW = 0, minV = 202020202020202020;
    rep(i, N){
        scanf("%lld", &cW[i]);
        maxW = max(maxW, cW[i]);
    }
    priority_queue<bridge> pq;
    rep(i, M){
        LL l, v;
        scanf("%lld %lld", &l, &v);
        minV = min(minV, v);
        pq.push({l, v});
    }
    
    // 2. 橋が崩落するパターンを除外.
    if(maxW > minV){
        puts("-1");
        return 0;
    }
    
    // 3. 橋の耐荷重に対する必要な最小間隔を保存.
    int idx = 0;
    while(!pq.empty()){
        bridge b = pq.top();
        pq.pop();
        bL[idx + 1] = max(bL[idx], b.l);
        bV[idx + 1] = b.v;
        idx++;
    }
    
    // 4. ラクダの隊列を全探索.
    vector<int> z(N);
    iota(all(z), 0);
    LL ans = 202020202020202020;
    do{
        // 4-1. ラクダの隊列の重量(累積和).
        LL cWCum[N + 1];
        memset(cWCum, 0LL, sizeof(cWCum));
        rep(i, N) cWCum[i + 1] = cWCum[i] + cW[z[i]];
        
        // 4-2. 制約.
        LL x[N][N];
        memset(x, 0LL, sizeof(x));
        rep(i, N){
            repx(j, i + 1, N){
                int at = lower_bound(bV, bV + M + 1, cWCum[j + 1] - cWCum[i]) - bV - 1;
                x[i][j] = max(x[i][j], bL[at]);
                x[j][i] = x[i][j];
            }
        }
        
        // 4-3. グラフの最長路の長さは？
        // AtCoder Beginner Contest 022 (C - Blue Bird) を ベース に 実装.
        // https://atcoder.jp/contests/abc022/tasks/abc022_c
        // -> 具体的には, Warshall–Floyd法で, 
        // repx(k, 1, N) repx(i, 1, N) repx(j, 1, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        // とあるものを, i = 0 に 固定するイメージで, 更新する形に変更.
        LL g[N][N], way = 0;
        memset(g, 0LL, sizeof(g));
        repx(i, 1, N){
            rep(j, i + 1){
                g[0][i] = min(g[0][i], g[0][j] - x[j][i]);
                way = min(way, g[0][i]);
            }
        }
        
        // 4-4. 最長路の長さについて, 最小値を更新.
        ans = min(ans, -way);
    }while(next_permutation(all(z)));
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc105/editorial/170

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

#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 all(x) x.begin(), x.end()

LL cW[11], bL[101010], bV[101010];

struct bridge{

LL l, v; // 長さ, 耐荷重.

bool operator < (const bridge& rhs) const{

return (v != rhs.v) ? (v > rhs.v) : (l < rhs.l);

}

};

int main(){

// 1. 入力情報.

int N, M;

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

LL maxW = 0, minV = 202020202020202020;

rep(i, N){

scanf("%lld", &cW[i]);

maxW = max(maxW, cW[i]);

}

priority_queue<bridge> pq;

rep(i, M){

LL l, v;

scanf("%lld %lld", &l, &v);

minV = min(minV, v);

pq.push({l, v});

}

// 2. 橋が崩落するパターンを除外.

if(maxW > minV){

puts("-1");

return 0;

}

// 3. 橋の耐荷重に対する必要な最小間隔を保存.

int idx = 0;

while(!pq.empty()){

bridge b = pq.top();

pq.pop();

bL[idx + 1] = max(bL[idx], b.l);

bV[idx + 1] = b.v;

idx++;

}

// 4. ラクダの隊列を全探索.

vector<int> z(N);

iota(all(z), 0);

LL ans = 202020202020202020;

do{

// 4-1. ラクダの隊列の重量(累積和).

LL cWCum[N + 1];

memset(cWCum, 0LL, sizeof(cWCum));

rep(i, N) cWCum[i + 1] = cWCum[i] + cW[z[i]];

// 4-2. 制約.

LL x[N][N];

memset(x, 0LL, sizeof(x));

rep(i, N){

repx(j, i + 1, N){

int at = lower_bound(bV, bV + M + 1, cWCum[j + 1] - cWCum[i]) - bV - 1;

x[i][j] = max(x[i][j], bL[at]);

x[j][i] = x[i][j];

}

// 4-3. グラフの最長路の長さは？

// AtCoder Beginner Contest 022 (C - Blue Bird) をベースに実装.

// https://atcoder.jp/contests/abc022/tasks/abc022_c

// -> 具体的には, Warshall–Floyd法で,

// repx(k, 1, N) repx(i, 1, N) repx(j, 1, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

// とあるものを, i = 0 に固定するイメージで, 更新する形に変更.

LL g[N][N], way = 0;

memset(g, 0LL, sizeof(g));

repx(i, 1, N){

rep(j, i + 1){

g[0][i] = min(g[0][i], g[0][j] - x[j][i]);

way = min(way, g[0][i]);

}

// 4-4. 最長路の長さについて, 最小値を更新.

ans = min(ans, -way);

}while(next_permutation(all(z)));

// 5. 出力.

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

return 0;

}

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

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

[入力例]
2 1
12 345
1 1

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

[入力例]
8 1
1 1 1 1 1 1 1 1
100000000 1

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

[入力例]
8 20
57 806 244 349 608 849 513 857
778 993
939 864
152 984
308 975
46 860
123 956
21 950
850 876
441 899
249 949
387 918
34 965
536 900
875 889
264 886
583 919
88 954
845 869
208 963
511 975

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

[入力例]
2 3
111 222
1 1010
2 2020
3 3030

[出力例]
0

[入力例]
8 12
11 13 7 9 3 12 8 5
17 20
20 20
21 20
5 25
7 25
11 33
13 33
17 40
18 40
23 50
15 50
29 52

[出力例]
63

[入力例]
8 15
17 10 12 19 15 22 32 27
21 81
23 81
13 90
11 90
55 100
22 100
17 58
6 58
17 80
33 80
91 45
27 45
73 45
60 77
83 77

[出力例]
273

[入力例]
8 32
940 727 412 991 481 225 680 385
6509 10969
121 2488
12037 11674
8409 11227
2344 4221
11547 5016
7294 8779
7584 3936
2259 4680
12074 8164
4670 10801
9290 8955
11063 7198
1499 2327
4909 6702
10397 8018
3329 1853
3955 2205
4255 7027
6930 11399
1295 6254
3079 8523
9737 4232
5041 10961
302 3614
763 5774
1927 11331
6516 2066
9917 3587
4050 11726
3065 1700
1260 2387

[出力例]
13032

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

141

142

143

144

145

[入力例]

3 2

1 4 2

10 4

2 6

[出力例]

※AtCoderのテストケースより

[入力例]

2 1

12 345

1 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

8 1

1 1 1 1 1 1 1 1

100000000 1

[出力例]

700000000

※AtCoderのテストケースより

[入力例]

8 20

57 806 244 349 608 849 513 857

778 993

939 864

152 984

308 975

46 860

123 956

21 950

850 876

441 899

249 949

387 918

34 965

536 900

875 889

264 886

583 919

88 954

845 869

208 963

511 975

[出力例]

3802

※AtCoderのテストケースより

[入力例]

2 3

111 222

1 1010

2 2020

3 3030

[出力例]

[入力例]

8 12

11 13 7 9 3 12 8 5

17 20

20 20

21 20

5 25

7 25

11 33

13 33

17 40

18 40

23 50

15 50

29 52

[出力例]

[入力例]

8 15

17 10 12 19 15 22 32 27

21 81

23 81

13 90

11 90

55 100

22 100

17 58

6 58

17 80

33 80

91 45

27 45

73 45

60 77

83 77

[出力例]

273

[入力例]

8 32

940 727 412 991 481 225 680 385

6509 10969

121 2488

12037 11674

8409 11227

2344 4221

11547 5016

7294 8779

7584 3936

2259 4680

12074 8164

4670 10801

9290 8955

11063 7198

1499 2327

4909 6702

10397 8018

3329 1853

3955 2205

4255 7027

6930 11399

1295 6254

3079 8523

9737 4232

5041 10961

302 3614

763 5774

1927 11331

6516 2066

9917 3587

4050 11726

3065 1700

1260 2387

[出力例]

13032

■参照サイト
AtCoder Regular Contest 105
AtCoder Beginner Contest 022 (C – Blue Bird)

C++の練習を兼ねて, AtCoder Regular Contest 105 の 問題C (Camels and Bridge) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 105 の問題C (Camels and Bridge) を解いてみた.

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