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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題G (01Sequence) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc216/editorial/2474
// 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--)
#define pb push_back
const LL INF = 202020202020202020;

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

vector<edge> G[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, M){
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        edge e;
        e.n = r;
        e.c = (LL)(r - l + 1 - x);
        G[l - 1].pb(e);
    }
    
    // 2. グラフに辺を追加.
    rep(i, N){
        edge e1;
        e1.n = i + 1;
        e1.c = 1LL;
        G[i].pb(e1);
        
        edge e2;
        e2.n = i;
        e2.c = 0LL;
        G[i + 1].pb(e2);
    }
    
    // 3. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* memo){
        // 3-1. 初期化.
        priority_queue<edge> pq;
        
        // 3-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // 3-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 3-4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 3-5. 訪問済みフラグ設定.
            if(memo[cn]) continue;
            memo[cn]++;
            
            // 3-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});
            }
        }
        return;
    };
    
    // 4. 各頂点までの, 最短コストを求める.
    LL d[N + 1];     // 頂点 0 からの距離.
    int memo[N + 1]; // 訪問済みフラグ.
    rep(i, N + 1) d[i] = INF, memo[i] = 0;
    dijkstra(0, d, memo);
    
    // 5. 数列 A に含まれる 1 の 個数.
    LL a[N];
    rep(i, N) a[i] = 1LL - (d[i + 1] - d[i]);
    
    // 6. 出力.
    rep(i, N){
        printf("%lld", a[i]);
        printf("%s", (i < N - 1) ? " " : "\n");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2474

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

#define pb push_back

const LL INF = 202020202020202020;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

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

};

vector<edge> G[202020];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, M){

int l, r, x;

scanf("%d %d %d", &l, &r, &x);

edge e;

e.n = r;

e.c = (LL)(r - l + 1 - x);

G[l - 1].pb(e);

}

// 2. グラフに辺を追加.

rep(i, N){

edge e1;

e1.n = i + 1;

e1.c = 1LL;

G[i].pb(e1);

edge e2;

e2.n = i;

e2.c = 0LL;

G[i + 1].pb(e2);

}

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

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

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

// 3-1. 初期化.

priority_queue<edge> pq;

// 3-2. 始点設定.

d[s] = 0;

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

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

while(!pq.empty()){

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

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

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

if(memo[cn]) continue;

memo[cn]++;

// 3-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});

}

return;

};

// 4. 各頂点までの, 最短コストを求める.

LL d[N + 1]; // 頂点 0 からの距離.

int memo[N + 1]; // 訪問済みフラグ.

rep(i, N + 1) d[i] = INF, memo[i] = 0;

dijkstra(0, d, memo);

// 5. 数列 A に含まれる 1 の個数.

LL a[N];

rep(i, N) a[i] = 1LL - (d[i + 1] - d[i]);

// 6. 出力.

rep(i, N){

printf("%lld", a[i]);

printf("%s", (i < N - 1) ? " " : "\n");

}

return 0;

}

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

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

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

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

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

[出力例]
0 0 1 1 1 1 0 1 0 0

[入力例]
25 12
9 13 2
3 5 1
6 18 6
1 6 3
10 22 6
5 18 7
9 11 1
8 15 4
7 25 9
4 5 1
3 17 7
2 11 5

[出力例]
0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1

[入力例]

6 3

1 4 3

2 2 1

4 6 2

[出力例]

0 1 1 1 0 1

※AtCoderテストケースより

[入力例]

8 2

2 6 1

3 5 3

[出力例]

0 0 1 1 1 0 0 0

※AtCoderテストケースより

[入力例]

10 5

3 7 3

1 6 4

5 5 1

6 8 2

8 10 1

[出力例]

0 0 1 1 1 1 0 1 0 0

[入力例]

25 12

9 13 2

3 5 1

6 18 6

1 6 3

10 22 6

5 18 7

9 11 1

8 15 4

7 25 9

4 5 1

3 17 7

2 11 5

[出力例]

0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1

■参照サイト
AtCoder Beginner Contest 216

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題G (01Sequence) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題G (01Sequence) を解いてみた.

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