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

C++の練習を兼ねて, AtCoder Beginner Contest 188 の問題E (Peddler) を解いてみた.

■感想.
1. 問題E は解答方針が見えなかったので, 解説を参考に実装し, AC版に到達できたので, 良かったと思う.
2. DAG(Directed Acyclic Graph) の復習と, 苦手な dp の訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc188/editorial/477
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<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
LL a[202020], dp[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    vvi G(N);
    rep(i, M){
        int x, y;
        scanf("%d %d", &x, &y);
        x--, y--;
        G[x].pb(y);
    }
    
    // 2. 初期化.
    rep(i, N) dp[i] = 202020202020202020;
    
    // 3. dp更新.
    // -> 頂点 x から 頂点 y へ向かって, dp更新.
    rep(x, N) for(auto &y : G[x]) dp[y] = min({dp[y], dp[x], a[x]});
    
    // 4. 利益の最大値を計算.
    LL ans = -202020202020202020;
    rep(i, N) ans = max(ans, a[i] - dp[i]);
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc188/editorial/477

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<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

LL a[202020], dp[202020];

int main(){

// 1. 入力情報.

int N, M;

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

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

vvi G(N);

rep(i, M){

int x, y;

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

x--, y--;

G[x].pb(y);

}

// 2. 初期化.

rep(i, N) dp[i] = 202020202020202020;

// 3. dp更新.

// -> 頂点 x から頂点 y へ向かって, dp更新.

rep(x, N) for(auto &y : G[x]) dp[y] = min({dp[y], dp[x], a[x]});

// 4. 利益の最大値を計算.

LL ans = -202020202020202020;

rep(i, N) ans = max(ans, a[i] - dp[i]);

// 5. 出力.

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

return 0;

}

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

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

[入力例]
5 5
13 8 3 15 18
2 4
1 2
4 5
2 3
1 3

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

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

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

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

[出力例]
6

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

[出力例]
10

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

[出力例]
15

[入力例]

4 3

2 3 1 5

2 4

1 2

1 3

[出力例]

※AtCoderテストケースより

[入力例]

5 5

13 8 3 15 18

2 4

1 2

4 5

2 3

1 3

[出力例]

※AtCoderテストケースより

[入力例]

3 1

1 100 1

2 3

[出力例]

-99

※AtCoderテストケースより

[入力例]

5 4

3 7 6 12 8

2 3

3 4

2 5

3 5

[出力例]

[入力例]

7 10

5 10 2 3 4 12 7

1 4

4 7

3 5

2 3

6 7

3 6

2 6

4 5

5 6

6 7

[出力例]

[入力例]

11 11

3 4 2 5 12 11 13 5 16 17 12

4 5

4 6

4 7

1 4

2 4

3 4

5 8

5 9

5 10

6 10

6 11

[出力例]

■参照サイト
AtCoder Beginner Contest 188

C++の練習を兼ねて, AtCoder Beginner Contest 188 の 問題E (Peddler) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 188 の問題E (Peddler) を解いてみた.

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