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

C++の練習を兼ねて, AtCoder Regular Contest 111 の問題A (Simple Math 2) ～問題B (Reversible Cards) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @param m: 余りを計算するための正整数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b, LL m){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % m;
        a = a * a % m;
        b >>= 1;
    }
    return t % m;
}

int main(){
    
    // 1. 入力情報.
    LL N, M;
    scanf("%lld %lld", &N, &M);
    
    // 2. 与式を計算.
    // ① 10 の N乗 = q * M + r と 置くと, 与式は, q を M で 割った余りと一致する.
    // ② q = q' * M + r' と 置くと, 
    //    10 の N乗 = (q' * M + r') * M + r = q' * (M の 二乗) + r' * M + r
    //    なので, 10 の N乗 を M の 二乗 で 割った余りは, r' * M + r
    // ③ 従って, q を M で 割った余り(r')は, ①, ② から, ((r' * M + r) - r) / M で 計算できる.
    LL r1 = mPow(10LL, N, M);
    LL r2 = mPow(10LL, N, M * M);
    LL ans = (r2 - r1) / M;
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @param m: 余りを計算するための正整数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b, LL m){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % m;

a = a * a % m;

b >>= 1;

}

return t % m;

}

int main(){

// 1. 入力情報.

LL N, M;

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

// 2. 与式を計算.

// ① 10 の N乗 = q * M + r と置くと, 与式は, q を M で割った余りと一致する.

// ② q = q' * M + r' と置くと,

// 10 の N乗 = (q' * M + r') * M + r = q' * (M の二乗) + r' * M + r

// なので, 10 の N乗を M の二乗で割った余りは, r' * M + r

// ③ 従って, q を M で割った余り(r')は, ①, ② から, ((r' * M + r) - r) / M で計算できる.

LL r1 = mPow(10LL, N, M);

LL r2 = mPow(10LL, N, M * M);

LL ans = (r2 - r1) / M;

// 3. 出力.

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

return 0;

}

[入力例]
1 2

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

[入力例]
2 7

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

[入力例]
1000000000000000000 9997

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

[入力例]
987654321123456789 2021

[出力例]
1726

[入力例]

1 2

[出力例]

※AtCoderのテストケースより

[入力例]

2 7

[出力例]

※AtCoderのテストケースより

[入力例]

1000000000000000000 9997

[出力例]

9015

※AtCoderのテストケースより

[入力例]

987654321123456789 2021

[出力例]

1726

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

// 解き直し.
// https://atcoder.jp/contests/arc111/editorial/519
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
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
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vector<P> v;  // グラフ作成用のデータ保存.
    set<int> s;   // 頂点番号割り当て用のデータ保存.
    rep(i, N){
        int a, b;
        scanf("%d %d", &a, &b);
        v.pb({a, b});
        s.insert(a);
        s.insert(b);
    }
    
    // 2. 頂点番号の割り当て.
    int n = 0;
    map<int, int> m;
    for(auto &p : s) m[p] = n++;
    
    // 3. グラフ作成.
    vvi G(n + 1);
    for(auto &p : v){
        int a = m[p.a];
        int b = m[p.b];
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 4. グラフを連結成分に分解.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 4-1. 空のキュー.
        queue<int> q;
        
        // 4-2. 連結成分番号を設定.
        c[s] = l;
        
        // 4-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 4-4. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 4-5. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 4-6. 訪問済であれば, 処理をスキップ.
                if(c[e])            continue;
                if(!c[e] && e != s) c[e] = l, q.push(e);
            }
        }
        return;
    };
    int c[n], idx = 0;
    memset(c, 0, sizeof(c));
    rep(i, n) if(!c[i]) bfs(G, i, c, ++idx);
    // rep(i, n) printf("%d ", c[i]);
    // puts("");
    
    // 5. 各連結成分ごとに, 頂点を振り分ける.
    vvi C(idx);
    rep(i, n) C[c[i] - 1].pb(i);
    
    // 6. 各連結成分ごとに, 木であるか判定し, 集計.
    int ans = 0;
    rep(i, idx){
        // 6-1. 頂点数.
        int cv = C[i].size();
        
        // 6-2. 頂点の次数合計.
        int cd = 0;
        for(auto &v : C[i]) cd += G[v].size();
        
        // 6-3. 木であるか判定し, 集計.
        ans += cv;
        if(2 * cv - 2 == cd) ans--; // 木の場合.
    }
    
    // 7. 出力.
    printf("%d\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc111/editorial/519

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vector<P> v; // グラフ作成用のデータ保存.

set<int> s; // 頂点番号割り当て用のデータ保存.

rep(i, N){

int a, b;

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

v.pb({a, b});

s.insert(a);

s.insert(b);

}

// 2. 頂点番号の割り当て.

int n = 0;

map<int, int> m;

for(auto &p : s) m[p] = n++;

// 3. グラフ作成.

vvi G(n + 1);

for(auto &p : v){

int a = m[p.a];

int b = m[p.b];

G[a].pb(b);

G[b].pb(a);

}

// 4. グラフを連結成分に分解.

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

auto bfs = [&](vvi &G, int s, int* c, int l){

// 4-1. 空のキュー.

queue<int> q;

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

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(c[e]) continue;

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

}

return;

};

int c[n], idx = 0;

memset(c, 0, sizeof(c));

rep(i, n) if(!c[i]) bfs(G, i, c, ++idx);

// rep(i, n) printf("%d ", c[i]);

// puts("");

// 5. 各連結成分ごとに, 頂点を振り分ける.

vvi C(idx);

rep(i, n) C[c[i] - 1].pb(i);

// 6. 各連結成分ごとに, 木であるか判定し, 集計.

int ans = 0;

rep(i, idx){

// 6-1. 頂点数.

int cv = C[i].size();

// 6-2. 頂点の次数合計.

int cd = 0;

for(auto &v : C[i]) cd += G[v].size();

// 6-3. 木であるか判定し, 集計.

ans += cv;

if(2 * cv - 2 == cd) ans--; // 木の場合.

}

// 7. 出力.

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

return 0;

}

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

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

[入力例]
2
111 111
111 111

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

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

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

[入力例]
5
111 121
113 121
104 113
155 104
113 155

[出力例]
5

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

[出力例]
15

[入力例]

1 2

1 3

4 2

2 3

[出力例]

※AtCoderのテストケースより

[入力例]

111 111

[出力例]

※AtCoderのテストケースより

[入力例]

5 2

5 6

1 2

9 7

2 7

5 5

4 2

6 7

2 2

7 8

9 7

1 8

[出力例]

※AtCoderのテストケースより

[入力例]

111 121

113 121

104 113

155 104

113 155

[出力例]

[入力例]

7 11

3 9

3 10

2 4

3 11

7 6

15 11

14 10

9 10

14 15

9 2

12 13

6 5

5 9

5 12

14 1

6 10

2 7

13 10

8 5

1 6

15 9

8 2

10 15

15 2

[出力例]

■参照サイト
AtCoder Regular Contest 111

C++の練習を兼ねて, AtCoder Regular Contest 111 の 問題A (Simple Math 2) ～ 問題B (Reversible Cards) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 111 の問題A (Simple Math 2) ～問題B (Reversible Cards) を解いてみた.

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