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

C++の練習を兼ねて, AtCoder Regular Contest 106 の問題A (106) ～問題B (Values) を解いてみた.

■感想.
1. A問題は, A, B が 0 のパターンを, 除外する必要があることを見落としていたので, AC版到達までに苦労した.
2. B問題は, 方針が見えなかったので, 解説をベースに, AC版に到達できたので, 良かったと思う.
3. B問題で解説されていたグラフの性質は, 知らなかった内容であるため, 非常に勉強になったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// コメント修正して, 再提出.
// 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

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 数式を満たす (A, B) は？
    // 01_test_11, 01_test_12, 01_test_17 で, WA版.
    // -> A, B が 0 の パターンは, 除外する必要がある.
    // 2-1. 3 の 冪乗.
    // 3 の 38乗 = 1350851717672992089
    vector<LL> pow3, pow5;
    LL n3 = 1LL;
    while(n3 < 1e18) n3 *= 3LL, pow3.pb(n3);
    
    // 2-2. 5 の 冪乗.
    // 5 の 26乗 = 1490116119384765625
    LL n5 = 1LL;
    while(n5 < 1e18) n5 *= 5LL, pow5.pb(n5);
    
    // 3. N と等しくなる場合があるか？
    int A = -1, B = -1;
    rep(i, pow3.size()){
        rep(j, pow5.size()){
            if(pow3[i] + pow5[j] == N){
                A = i + 1;
                B = j + 1;
                break;
            }
        }
    }
    
    // 4. 出力.
    if(A == -1 && B == -1) puts("-1");
    else                   printf("%d %d\n", A, B);
    return 0;
    
}

// コメント修正して, 再提出.

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

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 数式を満たす (A, B) は？

// 01_test_11, 01_test_12, 01_test_17 で, WA版.

// -> A, B が 0 のパターンは, 除外する必要がある.

// 2-1. 3 の冪乗.

// 3 の 38乗 = 1350851717672992089

vector<LL> pow3, pow5;

LL n3 = 1LL;

while(n3 < 1e18) n3 *= 3LL, pow3.pb(n3);

// 2-2. 5 の冪乗.

// 5 の 26乗 = 1490116119384765625

LL n5 = 1LL;

while(n5 < 1e18) n5 *= 5LL, pow5.pb(n5);

// 3. N と等しくなる場合があるか？

int A = -1, B = -1;

rep(i, pow3.size()){

rep(j, pow5.size()){

if(pow3[i] + pow5[j] == N){

A = i + 1;

B = j + 1;

break;

}

// 4. 出力.

if(A == -1 && B == -1) puts("-1");

else printf("%d %d\n", A, B);

return 0;

}

[入力例]
106

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

[入力例]
1024

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

[入力例]
10460353208

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

[入力例]
63177032

[出力例]
15 11

[入力例]
1610228062568

[出力例]
25 17

[入力例]
748307129767950488

[出力例]
37 25

[入力例]

106

[出力例]

4 2

※AtCoderのテストケースより

[入力例]

1024

[出力例]

-1

※AtCoderのテストケースより

[入力例]

10460353208

[出力例]

21 1

※AtCoderのテストケースより

[入力例]

63177032

[出力例]

15 11

[入力例]

1610228062568

[出力例]

25 17

[入力例]

748307129767950488

[出力例]

37 25

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

// 解き直し.
// https://atcoder.jp/contests/arc106/editorial/247
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
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
#define a first
#define b second
LL a[202020], b[202020];
int connection[202020];    // 連結成分番号を保存.
LL ca[202020], cb[202020]; // 連結成分ごとの a, b の 総和.

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @param l: 連結成分番号(※1以上).
// @return: 特に無し.
void bfs(vvi &G, int s, int l){
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 連結成分番号を設定.
    connection[s] = l;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        // 4. キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            if(connection[e])            continue;
            if(!connection[e] && e != s) connection[e] = l, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    rep(i, N) scanf("%lld", &b[i]);
    vvi G(N);
    rep(i, M){
        int c, d;
        scanf("%d %d", &c, &d);
        c--, d--;
        G[c].pb(d);
        G[d].pb(c);
    }
    
    // 2. 探索を行い, 連結成分に分割.
    int idx = 0;
    rep(i, N) if(!connection[i]) bfs(G, i, ++idx);
    
    // 3. 各連結成分ごとに, a, b の 総和を計算.
    rep(i, N){
        ca[connection[i]] += a[i];
        cb[connection[i]] += b[i];
    }
    
    // 4. 各連結成分ごとに, a, b の 総和が等しいかチェック.
    bool ok = true;
    rep(i, N){
        if(ca[i] != cb[i]){
            ok = false;
            break;
        }
    }
    
    // 5. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc106/editorial/247

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

#define a first

#define b second

LL a[202020], b[202020];

int connection[202020]; // 連結成分番号を保存.

LL ca[202020], cb[202020]; // 連結成分ごとの a, b の総和.

// グラフを幅優先探索する.

// https://ja.wikipedia.org/wiki/幅優先探索

// ※bfsの動作確認用.

// @param G: グラフ.

// @param s: グラフの探索開始頂点.

// @param l: 連結成分番号(※1以上).

// @return: 特に無し.

void bfs(vvi &G, int s, int l){

// 1. 空のキュー.

queue<int> q;

// 2. 連結成分番号を設定.

connection[s] = l;

// 3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 4. キューから取り出す.

int u = q.front();

q.pop();

// 5. 取り出した要素を処理.

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

// 6. 訪問済であれば, 処理をスキップ.

if(connection[e]) continue;

if(!connection[e] && e != s) connection[e] = l, q.push(e);

}

return;

}

int main(){

// 1. 入力情報.

int N, M;

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

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

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

vvi G(N);

rep(i, M){

int c, d;

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

c--, d--;

G[c].pb(d);

G[d].pb(c);

}

// 2. 探索を行い, 連結成分に分割.

int idx = 0;

rep(i, N) if(!connection[i]) bfs(G, i, ++idx);

// 3. 各連結成分ごとに, a, b の総和を計算.

rep(i, N){

ca[connection[i]] += a[i];

cb[connection[i]] += b[i];

}

// 4. 各連結成分ごとに, a, b の総和が等しいかチェック.

bool ok = true;

rep(i, N){

if(ca[i] != cb[i]){

ok = false;

break;

}

// 5. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

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

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

[入力例]
1 0
5
5

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

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

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

[入力例]
17 9
-905371741 -999219903 969314057 -989982132 -87720225 -175700172 -993990465 929461728 895449935 -999016241 782467448 -906404298 578539175 9684413 -619191091 -952046546 125053320
-440503430 -997661446 -912471383 -995879434 932992245 -928388880 -616761933 929461728 210953513 -994677396 648190629 -530944122 578539175 9684413 595786809 -952046546 125053320
2 10
6 12
9 11
11 5
7 6
3 15
3 1
1 9
10 4

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

[入力例]

3 2

1 2 3

2 2 2

1 2

2 3

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 0

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

2 1

1 1

2 1

1 2

[出力例]

※AtCoderのテストケースより

[入力例]

17 9

-905371741 -999219903 969314057 -989982132 -87720225 -175700172 -993990465 929461728 895449935 -999016241 782467448 -906404298 578539175 9684413 -619191091 -952046546 125053320

-440503430 -997661446 -912471383 -995879434 932992245 -928388880 -616761933 929461728 210953513 -994677396 648190629 -530944122 578539175 9684413 595786809 -952046546 125053320

2 10

6 12

9 11

11 5

7 6

3 15

3 1

1 9

10 4

[出力例]

Yes

※AtCoderのテストケースより

■参照サイト
AtCoder Regular Contest 106

C++の練習を兼ねて, AtCoder Regular Contest 106 の 問題A (106) ～ 問題B (Values) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 106 の問題A (106) ～問題B (Values) を解いてみた.

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