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

C++の練習を兼ねて, AtCoder Beginner Contest 324 の問題F (Beautiful Path) を解いてみた.

■感想.
1. 問題F は, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 二分探索, および, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc324/editorial/7405
// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vvi = vector<vector<int>>;
using vvt = vector<vector<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 pb push_back

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    vvt t(N);
    rep(i, M){
        int u, v, b, c;
        scanf("%d %d %d %d", &u, &v, &b, &c);
        --u;
        --v;
        
        // 有向グラフ.
        G[u].pb(v);
        
        // 頂点, 美しさ, コスト.
        t[u].emplace_back(v, b, c);
    }
    
    // 2. 評価関数.
    auto f = [&](LL x) -> bool {
        // 2-1. 初期化.
        LL dp[N];
        rep(i, N) dp[i] = -2e18;
        dp[0] = 0;
        
        // 2-2. dp更新(頂点番号の小さい順).
        rep(u, N){
            // 辺(u, v)で, 最大値更新.
            for(auto &e : t[u]){
                int v = get<0>(e);
                int b = get<1>(e);
                int c = get<2>(e);
                dp[v] = max(dp[v], dp[u] + (LL)b * 1000000000 - (LL)c * x);
            }
        }
        
        // 2-3. 判定結果(OK).
        return (dp[N - 1] >= 0);
    };
    
    // 3. 二分探索で確認してみる.
    LL l = -1, h = 400000000000001;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    
    // 4. 出力.
    printf("%.16lf\n", (double)h / 1000000000);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc324/editorial/7405

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vvi = vector<vector<int>>;

using vvt = vector<vector<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 pb push_back

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

vvt t(N);

rep(i, M){

int u, v, b, c;

scanf("%d %d %d %d", &u, &v, &b, &c);

--u;

--v;

// 有向グラフ.

G[u].pb(v);

// 頂点, 美しさ, コスト.

t[u].emplace_back(v, b, c);

}

// 2. 評価関数.

auto f = [&](LL x) -> bool {

// 2-1. 初期化.

LL dp[N];

rep(i, N) dp[i] = -2e18;

dp[0] = 0;

// 2-2. dp更新(頂点番号の小さい順).

rep(u, N){

// 辺(u, v)で, 最大値更新.

for(auto &e : t[u]){

int v = get<0>(e);

int b = get<1>(e);

int c = get<2>(e);

dp[v] = max(dp[v], dp[u] + (LL)b * 1000000000 - (LL)c * x);

}

// 2-3. 判定結果(OK).

return (dp[N - 1] >= 0);

};

// 3. 二分探索で確認してみる.

LL l = -1, h = 400000000000001;

while(l + 1 < h){

LL m = (h + l) >> 1;

if(f(m)) l = m;

else h = m;

// printf("h=%lld l=%lld m=%lld\n", h, l, m);

}

// 4. 出力.

printf("%.16lf\n", (double)h / 1000000000);

return 0;

}

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

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

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

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

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

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

[入力例]
10 20
3 4 1 2
7 9 4 5
2 4 4 5
4 5 1 4
6 9 4 1
9 10 3 2
6 10 5 5
5 6 1 2
5 6 5 2
2 3 2 3
6 10 4 4
4 6 3 4
4 8 4 1
3 5 3 2
2 4 3 2
3 5 4 2
1 5 3 4
1 2 4 2
3 7 2 2
7 8 1 3

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

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

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

[出力例]
2.2500000010000001

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

[出力例]
3.5000000010000001

[入力例]

5 7

1 2 3 6

1 3 9 5

2 3 1 5

2 4 5 3

2 5 1 9

3 4 4 8

4 5 2 7

[出力例]

0.7500000000000000

※AtCoderテストケースより

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

0.7500000010000000

[入力例]

3 3

1 3 1 1

1 3 2 1

1 3 3 1

[出力例]

3.0000000000000000

※AtCoderテストケースより

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

3.0000000010000001

[入力例]

10 20

3 4 1 2

7 9 4 5

2 4 4 5

4 5 1 4

6 9 4 1

9 10 3 2

6 10 5 5

5 6 1 2

5 6 5 2

2 3 2 3

6 10 4 4

4 6 3 4

4 8 4 1

3 5 3 2

2 4 3 2

3 5 4 2

1 5 3 4

1 2 4 2

3 7 2 2

7 8 1 3

[出力例]

1.8333333333333333

※AtCoderテストケースより

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

1.8333333340000000

[入力例]

7 10

1 2 5 6

2 3 1 6

2 7 5 8

3 7 9 2

1 5 3 1

5 6 5 6

3 6 5 7

4 6 3 7

3 4 6 1

6 7 10 1

[出力例]

2.2500000010000001

[入力例]

10 16

1 2 3 2

1 5 2 1

2 5 10 2

2 3 3 5

3 4 6 1

5 6 3 7

6 7 2 10

5 7 6 1

6 8 3 8

7 8 10 1

8 10 6 4

7 10 3 5

6 10 8 1

3 9 3 1

4 9 5 3

9 10 5 1

[出力例]

3.5000000010000001

■参照サイト
日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324）

C++の練習を兼ねて, AtCoder Beginner Contest 324 の 問題F (Beautiful Path) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 324 の問題F (Beautiful Path) を解いてみた.

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