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

C++の練習を兼ねて, AtCoder Regular Contest 025 の問題C (ウサギとカメ) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, 個人的には, ダイクストラ法(応用版) と尺取り法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc025
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#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 all(x) x.begin(), x.end()
const LL INF = 202020202020202020;

struct edge{
    int n; // 次の頂点.
    LL c;  // コスト.
    bool operator < (const edge &E) const{ return c > E.c; }
};

vector<edge> G[3030];

int main(){
    
    // 1. 入力情報.
    int N, M, R, T;
    scanf("%d %d %d %d", &N, &M, &R, &T);
    rep(i, M){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        --a;
        --b;
        G[a].pb(edge{b, (LL)c});
        G[b].pb(edge{a, (LL)c});
    }
    
    // 2. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* m){
        // 2-1. 初期化.
        priority_queue<edge> pq;
        
        // 2-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // 2-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 2-4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 2-5. 訪問済みフラグ設定.
            if(m[cn]) continue;
            m[cn]++;
            
            // 2-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : G[cn]){
                // 移動コスト更新.
                int nn = g.n;
                LL nc = cc + g.c;
                if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
            }
        }
    };
    
    // 3. 最短経路のリスト作成.
    vvl v(N);
    rep(i, N){
        LL d[N];
        int memo[N];
        rep(j, N) d[j] = INF, memo[j] = 0;
        dijkstra(i, d, memo);
        rep(j, N) if(i != j) v[i].pb(d[j]);
        sort(all(v[i]));
    }
    /*
    for(auto &p : v){
        for(auto &q : p) printf("%d ", q);
        puts("\n-----");
    }
    */
    
    // 4. 組み合わせを集計.
    LL ans = 0;
    rep(i, N){
        // ウサギ, カメ の 最短経路長 を 評価.
        // -> X(ウサギの最短経路) * T(カメの速さ) > Y(カメの最短経路) * R(ウサギの速さ) に 注意.
        int r = 0;
        rep(l, N - 1){
            LL Y = v[i][l], X = v[i][r];
            while(X * T <= Y * R && r <= N - 2) X = v[i][++r];
            ans += (LL)(N - 1 - r);
        }
    }
    
    // 5. カメの速さ が ウサギの速さ よりも速かった場合.
    if(T > R) ans -= (LL)N * (LL)(N - 1);
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

// 解き直し.

// https://www.slideshare.net/chokudai/arc025

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

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

const LL INF = 202020202020202020;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

bool operator < (const edge &E) const{ return c > E.c; }

};

vector<edge> G[3030];

int main(){

// 1. 入力情報.

int N, M, R, T;

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

rep(i, M){

int a, b, c;

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

--a;

--b;

G[a].pb(edge{b, (LL)c});

G[b].pb(edge{a, (LL)c});

}

// 2. ダイクストラ法.

// https://ja.wikipedia.org/wiki/ダイクストラ法

auto dijkstra = [&](int s, LL* d, int* m){

// 2-1. 初期化.

priority_queue<edge> pq;

// 2-2. 始点設定.

d[s] = 0;

pq.push({s, 0LL});

// 2-3. キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 2-4. 探索を継続するために, 頂点を取得.

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 2-5. 訪問済みフラグ設定.

if(m[cn]) continue;

m[cn]++;

// 2-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.

for(auto &g : G[cn]){

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});

}

};

// 3. 最短経路のリスト作成.

vvl v(N);

rep(i, N){

LL d[N];

int memo[N];

rep(j, N) d[j] = INF, memo[j] = 0;

dijkstra(i, d, memo);

rep(j, N) if(i != j) v[i].pb(d[j]);

sort(all(v[i]));

}

for(auto &p : v){

for(auto &q : p) printf("%d ", q);

puts("\n-----");

}

// 4. 組み合わせを集計.

LL ans = 0;

rep(i, N){

// ウサギ, カメの最短経路長を評価.

// -> X(ウサギの最短経路) * T(カメの速さ) > Y(カメの最短経路) * R(ウサギの速さ) に注意.

int r = 0;

rep(l, N - 1){

LL Y = v[i][l], X = v[i][r];

while(X * T <= Y * R && r <= N - 2) X = v[i][++r];

ans += (LL)(N - 1 - r);

}

// 5. カメの速さがウサギの速さよりも速かった場合.

if(T > R) ans -= (LL)N * (LL)(N - 1);

// 6. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
6

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

[出力例]
12

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

[出力例]
50

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

[出力例]
50

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

[出力例]
565

[入力例]

4 5 2 1

1 2 4

1 3 3

1 4 6

2 3 5

3 4 4

[出力例]

※AtCoderテストケースより

[入力例]

5 4 7 7

1 2 1

2 3 1

3 4 1

4 5 1

[出力例]

※AtCoderテストケースより

[入力例]

3 3 1 2

1 2 5

2 3 8

1 3 7

[出力例]

[入力例]

4 6 2 3

1 2 2

1 3 5

1 4 3

2 3 3

2 4 5

3 4 2

[出力例]

[入力例]

5 7 2 5

1 2 6

1 3 5

2 3 2

3 5 3

2 5 1

2 4 7

4 5 4

[出力例]

[入力例]

6 8 5 4

1 2 8

2 3 2

1 3 5

3 4 3

2 4 10

4 5 5

2 6 7

[出力例]

[入力例]

12 18 7 6

1 2 10

1 8 5

2 7 8

2 3 7

2 11 3

11 12 11

3 4 2

4 12 5

4 6 3

3 5 10

5 6 1

5 10 2

6 10 3

7 10 2

7 9 3

9 10 5

8 9 1

7 8 2

[出力例]

565

■参照サイト
AtCoder Regular Contest 025

C++の練習を兼ねて, AtCoder Regular Contest 025 の 問題C (ウサギとカメ) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 025 の問題C (ウサギとカメ) を解いてみた.

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