個人用メモ帳

2023年3月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 076 の問題D (AtCoder Express) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 走れる最大の距離を計算できることに非常に興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc076/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#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--)
int t[202], v[202], tCum[202];
double f[40404];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &t[i + 1]);
    rep(i, N) scanf("%d", &v[i + 1]);
    
    // 2. 累積和.
    rep(i, N + 2) tCum[i + 1] = tCum[i] + t[i];
    
    // 3. 最小速度(0.5秒刻み).
    rep(i, 40404) f[i] = 2020202020.0;
    rep(i, N + 2){
        // 区間 の l, r.
        int l = 2 * tCum[i + 0];
        int r = 2 * tCum[i + 1];
        
        // 区間[0, l].
        repr(x, l, 0) f[x] = min(f[x], (double)v[i] + 0.5 * (l - x));
        
        // 区間[l, r].
        repx(x, l, r + 1) f[x] = min(f[x], (double)v[i]);
        
        // 区間[r, 40404).
        repx(x, r, 40404) f[x] = min(f[x], (double)v[i] + 0.5 * (x - r));
    }
    
    // 4. 集計.
    double ans = 0.0;
    rep(x, 2 * tCum[N + 1]) ans += f[x];
    
    // 5. 出力.
    printf("%.15lf\n", ans / 2);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc076/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

int t[202], v[202], tCum[202];

double f[40404];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%d", &t[i + 1]);

rep(i, N) scanf("%d", &v[i + 1]);

// 2. 累積和.

rep(i, N + 2) tCum[i + 1] = tCum[i] + t[i];

// 3. 最小速度(0.5秒刻み).

rep(i, 40404) f[i] = 2020202020.0;

rep(i, N + 2){

// 区間の l, r.

int l = 2 * tCum[i + 0];

int r = 2 * tCum[i + 1];

// 区間[0, l].

repr(x, l, 0) f[x] = min(f[x], (double)v[i] + 0.5 * (l - x));

// 区間[l, r].

repx(x, l, r + 1) f[x] = min(f[x], (double)v[i]);

// 区間[r, 40404).

repx(x, r, 40404) f[x] = min(f[x], (double)v[i] + 0.5 * (x - r));

}

// 4. 集計.

double ans = 0.0;

rep(x, 2 * tCum[N + 1]) ans += f[x];

// 5. 出力.

printf("%.15lf\n", ans / 2);

return 0;

}

[入力例]
1
100
30

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

[入力例]
2
60 50
34 38

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

[入力例]
3
12 14 2
6 2 7

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

[入力例]
1
9
10

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

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

[入力例]
10
64 55 27 35 76 119 7 18 49 100
29 19 31 39 27 48 41 87 55 70

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

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

[入力例]
5
13 152 63 71 93
36 30 22 5 23

[出力例]
7777.000000000000000

[入力例]
30
151 100 66 148 150 40 132 172 164 76 160 121 51 67 39 136 170 133 78 135 125 197 117 151 186 136 111 123 101 92
62 80 50 51 60 77 38 78 86 81 68 77 99 80 79 50 72 52 81 56 87 55 30 33 81 60 62 87 50 64

[出力例]
222222.000000000000000

[入力例]
100
8 121 6 60 172 83 136 108 1 51 165 36 98 164 50 92 66 174 22 175 106 190 110 107 108 38 70 5 93 199 133 119 166 167 68 128 77 66 133 177 87 184 194 34 175 98 153 71 72 119 172 71 51 13 168 156 165 155 31 189 134 127 103 22 67 110 47 25 115 111 49 12 6 39 79 55 128 176 156 184 67 123 167 78 161 184 155 88 76 109 132 59 50 160 122 29 132 110 61 180
5 53 25 54 18 99 19 87 25 8 8 73 26 83 8 26 64 66 59 63 64 33 89 64 57 62 69 50 62 51 60 82 70 33 73 55 99 55 33 62 88 27 87 11 60 86 1 86 96 97 72 63 99 33 11 50 95 60 67 86 55 88 77 64 69 77 79 55 99 7 71 30 94 67 81 23 5 84 31 96 22 55 57 60 70 40 36 51 77 37 57 7 11 58 10 11 89 11 93 58

[出力例]
500000.000000000000000

[入力例]

100

[出力例]

2100.000000000000000

※AtCoderテストケースより

[入力例]

60 50

34 38

[出力例]

2632.000000000000000

※AtCoderテストケースより

[入力例]

12 14 2

6 2 7

[出力例]

76.000000000000000

※AtCoderテストケースより

[入力例]

[出力例]

20.250000000000000000

※AtCoderテストケースより

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

20.250000000000000

[入力例]

64 55 27 35 76 119 7 18 49 100

29 19 31 39 27 48 41 87 55 70

[出力例]

20291.000000000000

※AtCoderテストケースより

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

20291.000000000000000

[入力例]

13 152 63 71 93

36 30 22 5 23

[出力例]

7777.000000000000000

[入力例]

151 100 66 148 150 40 132 172 164 76 160 121 51 67 39 136 170 133 78 135 125 197 117 151 186 136 111 123 101 92

62 80 50 51 60 77 38 78 86 81 68 77 99 80 79 50 72 52 81 56 87 55 30 33 81 60 62 87 50 64

[出力例]

222222.000000000000000

[入力例]

100

8 121 6 60 172 83 136 108 1 51 165 36 98 164 50 92 66 174 22 175 106 190 110 107 108 38 70 5 93 199 133 119 166 167 68 128 77 66 133 177 87 184 194 34 175 98 153 71 72 119 172 71 51 13 168 156 165 155 31 189 134 127 103 22 67 110 47 25 115 111 49 12 6 39 79 55 128 176 156 184 67 123 167 78 161 184 155 88 76 109 132 59 50 160 122 29 132 110 61 180

5 53 25 54 18 99 19 87 25 8 8 73 26 83 8 26 64 66 59 63 64 33 89 64 57 62 69 50 62 51 60 82 70 33 73 55 99 55 33 62 88 27 87 11 60 86 1 86 96 97 72 63 99 33 11 50 95 60 67 86 55 88 77 64 69 77 79 55 99 7 71 30 94 67 81 23 5 84 31 96 22 55 57 60 70 40 36 51 77 37 57 7 11 58 10 11 89 11 93 58

[出力例]

500000.000000000000000

■参照サイト
AtCoder Beginner Contest 076

2023年3月26日2023年3月26日

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

C++の練習を兼ねて, AtCoder Beginner Contest 133 の問題E (Virus Tree 2) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 苦手な動的計画法(木dp)の訓練を積めたので, 非常に良かったと思う.
3. メモ化再帰の復習もできたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc133/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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
const LL MOD = 1e9 + 7;
const int LIMIT = 101010;
LL FAC[LIMIT], INV[LIMIT], dp[LIMIT];

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

// 順列(nPk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 順列(nPk)の計算結果(mod版).
LL permutation(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0LL;
    LL ret = FAC[n] * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 事前準備.
    FAC[0] = INV[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = (LL)i * FAC[i - 1] % MOD;
        INV[i] = mPow(FAC[i], MOD - 2);
    }
    rep(i, N) dp[i] = -1;
     
    // 3. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, int cur, int bef) -> LL {
        // 終了条件.
        if(dp[cur] != -1) return dp[cur];
        
        // 葉っぱ(根以外).
        if(cur != 0 && G[cur].size() == 1) return (dp[cur] = permutation(K - 2, 0));
        
        // 隣接頂点.
        LL ret = 1, cx = 0;
        for(auto &nex : G[cur]){
            if(nex == bef) continue;
            ret *= (dp[nex] != -1) ? dp[nex] : self(self, nex, cur);
            ret %= MOD;
            ++cx;
        }
        
        // 根.
        if(cur == 0){
            ret *= K;
            ret %= MOD;
            ret *= permutation(K - 1, cx);
            ret %= MOD;
        }
        
        // 根以外.
        if(cur != 0){
            ret *= permutation(K - 2, cx);
            ret %= MOD;
        }
        
        // メモ化して返却.
        return (dp[cur] = ret);
    };
    
    // 4. 出力.
    printf("%lld\n", dfs(dfs, 0, -1));
    return 0;
    
}

100

101

102

103

104

105

// 解き直し.

// https://img.atcoder.jp/abc133/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

const LL MOD = 1e9 + 7;

const int LIMIT = 101010;

LL FAC[LIMIT], INV[LIMIT], dp[LIMIT];

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

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

// @param b: 指数.

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

LL mPow(LL a, LL b){

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t;

}

// 順列(nPk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 順列(nPk)の計算結果(mod版).

LL permutation(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0LL;

LL ret = FAC[n] * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, K;

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

vvi G(N);

rep(i, N - 1){

int a, b;

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

--a, --b;

G[a].pb(b);

G[b].pb(a);

}

// 2. 事前準備.

FAC[0] = INV[0] = 1;

repx(i, 1, LIMIT){

FAC[i] = (LL)i * FAC[i - 1] % MOD;

INV[i] = mPow(FAC[i], MOD - 2);

}

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

// 3. dfs.

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

auto dfs = [&](auto&& self, int cur, int bef) -> LL {

// 終了条件.

if(dp[cur] != -1) return dp[cur];

// 葉っぱ(根以外).

if(cur != 0 && G[cur].size() == 1) return (dp[cur] = permutation(K - 2, 0));

// 隣接頂点.

LL ret = 1, cx = 0;

for(auto &nex : G[cur]){

if(nex == bef) continue;

ret *= (dp[nex] != -1) ? dp[nex] : self(self, nex, cur);

ret %= MOD;

++cx;

}

// 根.

if(cur == 0){

ret *= K;

ret %= MOD;

ret *= permutation(K - 1, cx);

ret %= MOD;

}

// 根以外.

if(cur != 0){

ret *= permutation(K - 2, cx);

ret %= MOD;

}

// メモ化して返却.

return (dp[cur] = ret);

};

// 4. 出力.

printf("%lld\n", dfs(dfs, 0, -1));

return 0;

}

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

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

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

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

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

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

[入力例]
1 5

[出力例]
5

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

[出力例]
4320

[入力例]
20 11
1 2
5 1
6 1
3 2
4 2
3 20
4 11
4 12
5 15
16 5
7 6
6 8
8 9
8 10
13 9
14 9
13 17
13 18
13 19

[出力例]
585418077

[入力例]

4 3

1 2

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 2

1 3

1 4

4 5

[出力例]

※AtCoderテストケースより

[入力例]

16 22

12 1

3 1

4 16

7 12

6 2

2 15

5 16

14 16

10 11

3 10

3 13

8 6

16 8

9 12

4 3

[出力例]

271414432

※AtCoderテストケースより

[入力例]

1 5

[出力例]

[入力例]

9 5

1 2

3 1

1 4

5 2

6 2

7 3

3 8

9 3

[出力例]

4320

[入力例]

20 11

1 2

5 1

6 1

3 2

4 2

3 20

4 11

4 12

5 15

16 5

7 6

6 8

8 9

8 10

13 9

14 9

13 17

13 18

13 19

[出力例]

585418077

■参照サイト
AtCoder Beginner Contest 133

2023年3月25日

C++ の動作確認をしてみた（９１６）

C++の練習を兼ねて, AtCoder Beginner Contest 127 の問題F (Absolute Minima) を解いてみた.

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, Slope Trick を復習することが出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc127/editorial.pdf
// 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--)
const LL INF = 202020202020202020;

int main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. f(x).
    LL y = 0, x = 0;
    multiset<LL> lMst, rMst;
    lMst.insert(-INF), rMst.insert(INF);
    auto f = [&](LL a, LL b){
        // 最大値(左側), 最小値(右側).
        auto l = (--lMst.end());
        auto r = rMst.begin();
        assert(lMst.size() == rMst.size());
        
        // 更新(y).
        y += b;
        
        // a >= l かつ a <= r.
        if(a >= *l && a <= *r){
            lMst.insert(a);
            rMst.insert(a);
        }
        
        // a < l.
        if(a < *l){
            lMst.insert(a);
            lMst.insert(a);
            y += *l - a;
            lMst.erase(lMst.find(*l));
            rMst.insert(*l);
        }
        
        // a > r.
        if(a > *r){
            rMst.insert(a);
            rMst.insert(a);
            y += a - *r;
            rMst.erase(rMst.find(*r));
            lMst.insert(*r);
        }
        
        // 更新(x).
        x = *(--lMst.end());
    };
    
    // 3. クエリ回答.
    rep(i, Q){
        int t;
        scanf("%d", &t);
        
        // クエリ 1.
        if(t == 1){
            LL a, b;
            scanf("%lld %lld", &a, &b);
            f(a, b);
        }
        
        // クエリ 2.
        if(t == 2) printf("%lld %lld\n", x, y);
    }
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc127/editorial.pdf

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

const LL INF = 202020202020202020;

int main(){

// 1. 入力情報.

int Q;

scanf("%d", &Q);

// 2. f(x).

LL y = 0, x = 0;

multiset<LL> lMst, rMst;

lMst.insert(-INF), rMst.insert(INF);

auto f = [&](LL a, LL b){

// 最大値(左側), 最小値(右側).

auto l = (--lMst.end());

auto r = rMst.begin();

assert(lMst.size() == rMst.size());

// 更新(y).

y += b;

// a >= l かつ a <= r.

if(a >= *l && a <= *r){

lMst.insert(a);

rMst.insert(a);

}

// a < l.

if(a < *l){

lMst.insert(a);

y += *l - a;

lMst.erase(lMst.find(*l));

rMst.insert(*l);

}

// a > r.

if(a > *r){

rMst.insert(a);

y += a - *r;

rMst.erase(rMst.find(*r));

lMst.insert(*r);

}

// 更新(x).

x = *(--lMst.end());

};

// 3. クエリ回答.

rep(i, Q){

int t;

scanf("%d", &t);

// クエリ 1.

if(t == 1){

LL a, b;

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

f(a, b);

}

// クエリ 2.

if(t == 2) printf("%lld %lld\n", x, y);

}

return 0;

}

[入力例]
4
1 4 2
2
1 1 -8
2

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

[入力例]
4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2

[出力例]
-1000000000 3000000000
※AtCoderテストケースより

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

[出力例]
3 -1
3 0
4 1
3 3
4 -3

[入力例]
21
1 -3 -34
1 2 61
2
1 10 -30
2
1 -3 5
2
1 -9 -67
1 -4 20
2
1 -10 72
2
1 -5 -14
2
1 -6 -52
2
1 6 92
1 6 -34
2
1 -2 21
2

[出力例]
-3 32
2 10
-3 20
-3 -20
-3 59
-4 47
-4 -3
-3 74
-3 96

[入力例]
120
1 555 -87
2
1 -669 45
1 761 -87
2
1 226 -50
2
1 -653 -41
1 -920 66
2
1 -111 18
2
1 -520 1
2
1 -851 -77
2
1 -3 -16
1 278 91
2
1 513 -20
2
1 -968 -94
2
1 -33 -67
2
1 634 57
2
1 -611 -58
2
1 -189 75
2
1 -870 -66
2
1 -23 -81
1 432 65
1 743 54
2
1 -178 -95
2
1 -36 -68
1 733 81
2
1 440 39
1 -601 71
2
1 -222 -7
2
1 446 100
1 310 46
2
1 388 -10
1 -992 88
2
1 6 53
2
1 878 42
1 739 32
2
1 313 4
1 257 66
2
1 -1000 -37
2
1 -378 19
1 258 27
2
1 -585 -18
2
1 -739 46
1 763 -58
2
1 203 -24
1 -835 -19
2
1 -202 -70
2
1 -833 -35
1 -224 86
1 382 -16
2
1 565 -69
2
1 -884 38
1 -382 51
1 -494 79
1 -214 -95
2
1 -271 -24
1 -448 24
2
1 958 61
2
1 202 49
2
1 -778 -12
1 -123 -38
1 211 7
2
1 -432 63
2
1 785 -42
2
1 583 100
2
1 -331 78
2
1 101 -26
2
1 169 92
2
1 -59 80
1 -169 -57
2
1 191 -59
2
1 -860 80
2
1 167 -72
1 410 0
2

[出力例]
555 -87
555 1301
226 1580
-653 3630
-111 3648
-520 4058
-520 4312
-111 5293
-111 5897
-111 6660
-111 6671
-33 7395
-111 7915
-111 8068
-189 8761
-33 10206
-111 10256
-36 11038
-36 12189
-36 12368
-33 13339
-33 14797
-33 14889
-23 16626
-3 17272
-3 18232
-3 18914
-23 19478
-23 20968
-23 21963
-23 22072
-33 23523
-23 24042
-36 25964
-111 26536
-111 27666
-36 27953
-111 28986
-111 29370
-111 30224
-36 30943
-111 31316
-36 31427
-36 31724
-59 31903
-36 32071
-59 32975
-36 33552

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

[入力例]

1 4 2

1 1 -8

[出力例]

4 2

1 -3

※AtCoderテストケースより

[入力例]

1 -1000000000 1000000000

[出力例]

-1000000000 3000000000

※AtCoderテストケースより

[入力例]

1 3 -1

1 6 -2

1 4 1

1 -1 -3

1 5 -7

[出力例]

3 -1

3 0

4 1

3 3

4 -3

[入力例]

1 -3 -34

1 2 61

1 10 -30

1 -3 5

1 -9 -67

1 -4 20

1 -10 72

1 -5 -14

1 -6 -52

1 6 92

1 6 -34

1 -2 21

[出力例]

-3 32

2 10

-3 20

-3 -20

-3 59

-4 47

-4 -3

-3 74

-3 96

[入力例]

120

1 555 -87

1 -669 45

1 761 -87

1 226 -50

1 -653 -41

1 -920 66

1 -111 18

1 -520 1

1 -851 -77

1 -3 -16

1 278 91

1 513 -20

1 -968 -94

1 -33 -67

1 634 57

1 -611 -58

1 -189 75

1 -870 -66

1 -23 -81

1 432 65

1 743 54

1 -178 -95

1 -36 -68

1 733 81

1 440 39

1 -601 71

1 -222 -7

1 446 100

1 310 46

1 388 -10

1 -992 88

1 6 53

1 878 42

1 739 32

1 313 4

1 257 66

1 -1000 -37

1 -378 19

1 258 27

1 -585 -18

1 -739 46

1 763 -58

1 203 -24

1 -835 -19

1 -202 -70

1 -833 -35

1 -224 86

1 382 -16

1 565 -69

1 -884 38

1 -382 51

1 -494 79

1 -214 -95

1 -271 -24

1 -448 24

1 958 61

1 202 49

1 -778 -12

1 -123 -38

1 211 7

1 -432 63

1 785 -42

1 583 100

1 -331 78

1 101 -26

1 169 92

1 -59 80

1 -169 -57

1 191 -59

1 -860 80

1 167 -72

1 410 0

[出力例]

555 -87

555 1301

226 1580

-653 3630

-111 3648

-520 4058

-520 4312

-111 5293

-111 5897

-111 6660

-111 6671

-33 7395

-111 7915

-111 8068

-189 8761

-33 10206

-111 10256

-36 11038

-36 12189

-36 12368

-33 13339

-33 14797

-33 14889

-23 16626

-3 17272

-3 18232

-3 18914

-23 19478

-23 20968

-23 21963

-23 22072

-33 23523

-23 24042

-36 25964

-111 26536

-111 27666

-36 27953

-111 28986

-111 29370

-111 30224

-36 30943

-111 31316

-36 31427

-36 31724

-59 31903

-36 32071

-59 32975

-36 33552

■参照サイト
AtCoder Beginner Contest 127

2023年3月21日2023年3月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 008 の問題D (金塊ゲーム) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 苦手な動的計画法の訓練が積めたので, 非常に良かったと思う.
3. メモ化再帰の復習もできたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc008/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#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 a first
#define b second
int dp[101][101][101][101], x[33], y[33];

int main(){
    
    // 1. 入力情報.
    int W, H, N;
    scanf("%d %d %d", &W, &H, &N);
    map<int, int> mxi, mxo, myi, myo;
    mxi[1] = myi[1] = mxi[W] = myi[H] = 0;
    rep(i, N){
        scanf("%d %d", &x[i], &y[i]);
        mxi[x[i]] = myi[y[i]] = 0;
        if(x[i] > 1) mxi[x[i] - 1] = 0;
        if(y[i] > 1) myi[y[i] - 1] = 0;
        if(x[i] < W) mxi[x[i] + 1] = 0;
        if(y[i] < H) myi[y[i] + 1] = 0;
    }
    
    // 2. 座標圧縮.
    int idx = -1;
    for(auto &p : mxi) p.b = ++idx;
    for(auto &p : mxi) mxo[p.b] = p.a;
    int idy = -1;
    for(auto &p : myi) p.b = ++idy;
    for(auto &p : myi) myo[p.b] = p.a;
    
    // 3. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, int x1, int y1, int x2, int y2) -> int {
        // 終了条件.
        if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];
        
        // 再帰処理(各クレーン).
        int ret = 0;
        rep(i, N){
            // 回収可能か？
            if(mxi[x[i]] < x1 || mxi[x[i]] > x2 || myi[y[i]] < y1 || myi[y[i]] > y2) continue;
            
            // 金塊の回収.
            // クレーン.
            int cur = (mxo[x2] - mxo[x1]) + (myo[y2] - myo[y1]) + 1;
            
            // 左.
            if(x[i] > 1){
                // 左下.
                if(y[i] > 1) cur += self(self,            x1,            y1, mxi[x[i] - 1], myi[y[i] - 1]);
                
                // 左上.
                if(y[i] < H) cur += self(self,            x1, myi[y[i] + 1], mxi[x[i] - 1],            y2);
            }
            
            // 右.
            if(x[i] < W){
                // 右下.
                if(y[i] > 1) cur += self(self, mxi[x[i] + 1],            y1,            x2, myi[y[i] - 1]);
                
                // 右上.
                if(y[i] < H) cur += self(self, mxi[x[i] + 1], myi[y[i] + 1],            x2,            y2);
            }
            
            // 最大値更新.
            ret = max(ret, cur);
        }
        
        // メモ化して返却.
        return (dp[x1][y1][x2][y2] = ret);
    };
        
    // 4. dp更新.
    rep(i, 101) rep(j, 101) rep(k, 101) rep(l, 101) dp[i][j][k][l] = -1;
    int ans = dfs(dfs, mxi[1], myi[1], mxi[W], myi[H]);
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc008/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

#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 a first

#define b second

int dp[101][101][101][101], x[33], y[33];

int main(){

// 1. 入力情報.

int W, H, N;

scanf("%d %d %d", &W, &H, &N);

map<int, int> mxi, mxo, myi, myo;

mxi[1] = myi[1] = mxi[W] = myi[H] = 0;

rep(i, N){

scanf("%d %d", &x[i], &y[i]);

mxi[x[i]] = myi[y[i]] = 0;

if(x[i] > 1) mxi[x[i] - 1] = 0;

if(y[i] > 1) myi[y[i] - 1] = 0;

if(x[i] < W) mxi[x[i] + 1] = 0;

if(y[i] < H) myi[y[i] + 1] = 0;

}

// 2. 座標圧縮.

int idx = -1;

for(auto &p : mxi) p.b = ++idx;

for(auto &p : mxi) mxo[p.b] = p.a;

int idy = -1;

for(auto &p : myi) p.b = ++idy;

for(auto &p : myi) myo[p.b] = p.a;

// 3. dfs.

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

auto dfs = [&](auto&& self, int x1, int y1, int x2, int y2) -> int {

// 終了条件.

if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];

// 再帰処理(各クレーン).

int ret = 0;

rep(i, N){

// 回収可能か？

if(mxi[x[i]] < x1 || mxi[x[i]] > x2 || myi[y[i]] < y1 || myi[y[i]] > y2) continue;

// 金塊の回収.

// クレーン.

int cur = (mxo[x2] - mxo[x1]) + (myo[y2] - myo[y1]) + 1;

// 左.

if(x[i] > 1){

// 左下.

if(y[i] > 1) cur += self(self, x1, y1, mxi[x[i] - 1], myi[y[i] - 1]);

// 左上.

if(y[i] < H) cur += self(self, x1, myi[y[i] + 1], mxi[x[i] - 1], y2);

}

// 右.

if(x[i] < W){

// 右下.

if(y[i] > 1) cur += self(self, mxi[x[i] + 1], y1, x2, myi[y[i] - 1]);

// 右上.

if(y[i] < H) cur += self(self, mxi[x[i] + 1], myi[y[i] + 1], x2, y2);

}

// 最大値更新.

ret = max(ret, cur);

}

// メモ化して返却.

return (dp[x1][y1][x2][y2] = ret);

};

// 4. dp更新.

rep(i, 101) rep(j, 101) rep(k, 101) rep(l, 101) dp[i][j][k][l] = -1;

int ans = dfs(dfs, mxi[1], myi[1], mxi[W], myi[H]);

// 5. 出力.

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

return 0;

}

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

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

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

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

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

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

[入力例]
10 15
10 
3 12
10 1
8 11
6 11
4 10
1 3
5 10
4 11
5 9
3 4

[出力例]
102

[入力例]
333 333
15 
104 52
7 204
13 81
2 170
66 149
315 21
291 195
29 333
330 317
29 128
331 236
95 167
172 187
295 252
121 239

[出力例]
6230

[入力例]
35 30
20 
20 28
13 28
15 19
17 23
24 2
1 20
3 13
30 13
18 10
13 13
18 11
29 29
6 10
22 20
30 25
24 30
2 29
35 9
32 9
24 8

[出力例]
512

[入力例]
500 500
20
21 175
490 480
256 191
391 387
9 418
96 153
458 325
167 259
84 110
84 243
237 259
353 71
332 190
399 61
167 23
37 206
217 460
269 12
89 173
100 410

[出力例]
10682

[入力例]
1000000 1000000
30 
637828 319816
244524 123531
562573 809275
720223 918249
883753 853155
141958 383641
964471 19449
244552 25727
877562 368658
198190 576776
807178 858672
723437 434181
118576 250190
650166 872144
559030 352602
211905 971770
170666 972127
950292 367351
69139 404753
956204 162668
35771 168055
940217 706249
914198 373742
378983 854296
49242 132854
756632 863851
974092 503954
975854 274858
95497 890691
365021 25373

[出力例]
32383224

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

[入力例]

6 4

2 4

3 1

4 3

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 1

2 3

3 2

[出力例]

※AtCoderテストケースより

[入力例]

15 10

7 10

12 8

4 4

5 7

9 9

1 6

6 5

3 2

[出力例]

112

※AtCoderテストケースより

[入力例]

10 15

3 12

10 1

8 11

6 11

4 10

1 3

5 10

4 11

5 9

3 4

[出力例]

102

[入力例]

333 333

104 52

7 204

13 81

2 170

66 149

315 21

291 195

29 333

330 317

29 128

331 236

95 167

172 187

295 252

121 239

[出力例]

6230

[入力例]

35 30

20 28

13 28

15 19

17 23

24 2

1 20

3 13

30 13

18 10

13 13

18 11

29 29

6 10

22 20

30 25

24 30

2 29

35 9

32 9

24 8

[出力例]

512

[入力例]

500 500

21 175

490 480

256 191

391 387

9 418

96 153

458 325

167 259

84 110

84 243

237 259

353 71

332 190

399 61

167 23

37 206

217 460

269 12

89 173

100 410

[出力例]

10682

[入力例]

1000000 1000000

637828 319816

244524 123531

562573 809275

720223 918249

883753 853155

141958 383641

964471 19449

244552 25727

877562 368658

198190 576776

807178 858672

723437 434181

118576 250190

650166 872144

559030 352602

211905 971770

170666 972127

950292 367351

69139 404753

956204 162668

35771 168055

940217 706249

914198 373742

378983 854296

49242 132854

756632 863851

974092 503954

975854 274858

95497 890691

365021 25373

[出力例]

32383224

■参照サイト
AtCoder Beginner Contest 008

2023年3月18日

C++ の動作確認をしてみた（９１４）

C++の練習を兼ねて, AtCoder Beginner Contest 206 の問題F (Interval Game 2) を解いてみた.

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, メモ化再帰, Grundy数を復習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, int n, int x, int y) -> int {
        // 終了条件.
        if(dp[x][y] != -1) return dp[x][y];
        
        // ゲーム分割.
        set<int> st;
        rep(i, n){
            // 区間[L, R).
            int L = section[i].a;
            int R = section[i].b;
            
            // 区間[L, R) を 含まない.
            if(L < x || y < R) continue;
            
            // 区間[L, R) を 含む.
            // -> ゲームを分割し, XOR で 結合(但し, 各分割されたゲームは, 再帰処理を行う).
            int cur = self(self, n, x, L) ^ self(self, n, R, y);
            
            // 保存.
            st.insert(cur);
        }
        
        // Grundy数.
        int g = 0;
        while(st.count(g)) ++g;
        
        // メモ化して返却.
        return (dp[x][y] = g);
    };
        
    // 3. 各テストケース.
    rep(i, T){
        // 3-1. 初期化.
        rep(j, 101) rep(k, 101) dp[j][k] = -1;
        rep(j, 101) section[j].a = section[j].b = 0;
        
        // 3-2. テストケース入力情報.
        int N;
        scanf("%d", &N);
        rep(j, N) scanf("%d %d", &section[j].a, &section[j].b);
        
        // 3-3. 出力.
        printf("%s\n", dfs(dfs, N, 1, 100) ? "Alice" : "Bob");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc206/editorial/2100

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<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 a first

#define b second

int dp[101][101];

P section[101];

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. dfs.

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

auto dfs = [&](auto&& self, int n, int x, int y) -> int {

// 終了条件.

if(dp[x][y] != -1) return dp[x][y];

// ゲーム分割.

set<int> st;

rep(i, n){

// 区間[L, R).

int L = section[i].a;

int R = section[i].b;

// 区間[L, R) を含まない.

if(L < x || y < R) continue;

// 区間[L, R) を含む.

// -> ゲームを分割し, XOR で結合(但し, 各分割されたゲームは, 再帰処理を行う).

int cur = self(self, n, x, L) ^ self(self, n, R, y);

// 保存.

st.insert(cur);

}

// Grundy数.

int g = 0;

while(st.count(g)) ++g;

// メモ化して返却.

return (dp[x][y] = g);

};

// 3. 各テストケース.

rep(i, T){

// 3-1. 初期化.

rep(j, 101) rep(k, 101) dp[j][k] = -1;

rep(j, 101) section[j].a = section[j].b = 0;

// 3-2. テストケース入力情報.

int N;

scanf("%d", &N);

rep(j, N) scanf("%d %d", &section[j].a, &section[j].b);

// 3-3. 出力.

printf("%s\n", dfs(dfs, N, 1, 100) ? "Alice" : "Bob");

}

return 0;

}

[入力例]
5
3
53 98
8 43
12 53
10
4 7
5 7
3 7
4 5
5 8
6 9
4 8
5 10
1 9
5 10
2
58 98
11 29
6
79 83
44 83
38 74
49 88
18 45
64 99
1
5 9

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

[入力例]
5
3
7 9
3 10
18 38
5
12 23
4 13
4 24
10 20
18 27
5
8 12
15 19
23 50
27 39
51 55
10
6 19
10 17
11 30
28 46
17 23
13 54
55 68
17 26
35 70
10 30
15
17 37
26 44
29 36
4 23
19 24
23 32
13 25
9 30
22 36
1 18
21 55
7 8
17 35
26 78
16 37

[出力例]
Bob
Alice
Bob
Bob
Alice

[入力例]

53 98

8 43

12 53

4 7

5 7

3 7

4 5

5 8

6 9

4 8

5 10

1 9

5 10

58 98

11 29

79 83

44 83

38 74

49 88

18 45

64 99

5 9

[出力例]

Bob

Alice

Bob

Alice

※AtCoderテストケースより

[入力例]

7 9

3 10

18 38

12 23

4 13

4 24

10 20

18 27

8 12

15 19

23 50

27 39

51 55

6 19

10 17

11 30

28 46

17 23

13 54

55 68

17 26

35 70

10 30

17 37

26 44

29 36

4 23

19 24

23 32

13 25

9 30

22 36

1 18

21 55

7 8

17 35

26 78

16 37

[出力例]

Bob

Alice

Bob

Alice

■参照サイト
AtCoder Beginner Contest 206（Sponsored by Panasonic）

2023年3月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 206 の問題E (Divide Both) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで計算できる点が, 非常に興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc206/editorial/2099
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<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 a[1010101], b[1010101];

int main(){
    
    // 1. 入力情報.
    int L, R;
    scanf("%d %d", &L, &R);
    
    // 2. 素数.
    vi p;
    repx(i, 2, 1010101) if(!a[i]) repex(j, i * 2, 1010101, i) ++a[j];
    repx(i, 2, 1010101) if(!a[i]) p.pb(i);
    // 素数は, 同じ素因数が, 1回出現したと見る.
    repx(i, 2, 1010101) if(!a[i]) a[i] = 1;
    
    // 3. 同じ素因数を二つ以上含まない整数は？
    for(auto &x : p){
        int cur = x * x;
        if(cur >= 1010101) break;
        repex(i, cur, 1010101, cur) ++b[i];
    }
    
    // 4. 互いに素でない整数の組.
    LL ans = 0;
    repx(k, 2, R + 1){
        if(b[k]) continue;
        LL A = (LL)((R / k) - (L - 1) / k);
        ans += A * (A - 1) / 2 * ((a[k] & 1) ? +1 : -1);
    }
    
    // 5. x = g を 減算.
    repx(g, max(2, L), R + 1) ans -= (R / g - 1);
    
    // 6. 出力.
    printf("%lld\n", ans * 2);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc206/editorial/2099

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<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 a[1010101], b[1010101];

int main(){

// 1. 入力情報.

int L, R;

scanf("%d %d", &L, &R);

// 2. 素数.

vi p;

repx(i, 2, 1010101) if(!a[i]) repex(j, i * 2, 1010101, i) ++a[j];

repx(i, 2, 1010101) if(!a[i]) p.pb(i);

// 素数は, 同じ素因数が, 1回出現したと見る.

repx(i, 2, 1010101) if(!a[i]) a[i] = 1;

// 3. 同じ素因数を二つ以上含まない整数は？

for(auto &x : p){

int cur = x * x;

if(cur >= 1010101) break;

repex(i, cur, 1010101, cur) ++b[i];

}

// 4. 互いに素でない整数の組.

LL ans = 0;

repx(k, 2, R + 1){

if(b[k]) continue;

LL A = (LL)((R / k) - (L - 1) / k);

ans += A * (A - 1) / 2 * ((a[k] & 1) ? +1 : -1);

}

// 5. x = g を減算.

repx(g, max(2, L), R + 1) ans -= (R / g - 1);

// 6. 出力.

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

return 0;

}

[入力例]
3 7

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

[入力例]
4 10

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

[入力例]
1 1000000

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

[入力例]
5 12

[出力例]
14

[入力例]
10 25

[出力例]
78

[入力例]
123 321

[出力例]
15202

[入力例]
2023 3202

[出力例]
545052

[入力例]
120205 690315

[出力例]
127432667154

[入力例]

3 7

[出力例]

※AtCoderテストケースより

[入力例]

4 10

[出力例]

※AtCoderテストケースより

[入力例]

1 1000000

[出力例]

392047955148

※AtCoderテストケースより

[入力例]

5 12

[出力例]

[入力例]

10 25

[出力例]

[入力例]

123 321

[出力例]

15202

[入力例]

2023 3202

[出力例]

545052

[入力例]

120205 690315

[出力例]

127432667154

■参照サイト
AtCoder Beginner Contest 206（Sponsored by Panasonic）

2023年3月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 205 の問題E (White and Black Balls) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 組み合わせの考え方について復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc205/editorial/2059
// 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--)
const LL MOD = 1e9 + 7;
const int LIMIT = 2020202;
LL FAC[LIMIT], INV[LIMIT];

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

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    
    // 2. 例外.
    if(N > M + K){
        puts("0");
        return 0;
    }
    
    // 3. 事前準備.
    FAC[0] = INV[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = (LL)i * FAC[i - 1] % MOD;
        INV[i] = mPow(FAC[i], MOD - 2);
    }
    
    // 4. 経路数.
    LL ans = combination(N + M, N);
    ans += MOD;
    ans -= combination(N + M, M + K + 1);
    ans %= MOD;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc205/editorial/2059

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

const LL MOD = 1e9 + 7;

const int LIMIT = 2020202;

LL FAC[LIMIT], INV[LIMIT];

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

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

// @param b: 指数.

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

LL mPow(LL a, LL b){

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, M, K;

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

// 2. 例外.

if(N > M + K){

puts("0");

return 0;

}

// 3. 事前準備.

FAC[0] = INV[0] = 1;

repx(i, 1, LIMIT){

FAC[i] = (LL)i * FAC[i - 1] % MOD;

INV[i] = mPow(FAC[i], MOD - 2);

}

// 4. 経路数.

LL ans = combination(N + M, N);

ans += MOD;

ans -= combination(N + M, M + K + 1);

ans %= MOD;

// 5. 出力.

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

return 0;

}

[入力例]
2 3 1

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

[入力例]
1 0 0

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

[入力例]
1000000 1000000 1000000

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

[入力例]
3 3 2

[出力例]
19

[入力例]
5 4 3

[出力例]
117

[入力例]
205 2021 613

[出力例]
32582334

[入力例]

2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

1 0 0

[出力例]

※AtCoderテストケースより

[入力例]

1000000 1000000 1000000

[出力例]

192151600

※AtCoderテストケースより

[入力例]

3 3 2

[出力例]

[入力例]

5 4 3

[出力例]

117

[入力例]

205 2021 613

[出力例]

32582334

■参照サイト
AtCoder Beginner Contest 205

2023年3月12日2023年3月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 292 の問題C (Four Variables) ～問題D (Unicyclic Components) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込むことが出来たので, AC版に到達できたと思う.
2. 個人的には, 問題D で, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題C／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--)

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 二数の積が, 1 ～ N - 1 となる場合の数は？
    map<int, LL> m;
    repx(n, 1, N){
        repx(a, 1, sqrt(n) + 1){
            if(a * a > n) break;
            if(n % a == 0){
                ++m[n];
                m[n] += (a != (n / a));
            }
        }
    }
    
    // 3. 集計.
    LL ans = 0;
    repx(n, 1, N) ans += m[n] * m[N - n];
    
    // 4. 出力.
    printf("%lld\n", ans);
    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--)

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 二数の積が, 1 ～ N - 1 となる場合の数は？

map<int, LL> m;

repx(n, 1, N){

repx(a, 1, sqrt(n) + 1){

if(a * a > n) break;

if(n % a == 0){

++m[n];

m[n] += (a != (n / a));

}

// 3. 集計.

LL ans = 0;

repx(n, 1, N) ans += m[n] * m[N - n];

// 4. 出力.

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

return 0;

}

[入力例]
4

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

[入力例]
292

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

[入力例]
19876

[出力例]
2219958

[入力例]
8

[出力例]
37

[入力例]
15

[出力例]
108

[入力例]
2023

[出力例]
96560

[入力例]
200000

[出力例]
39745938

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

292

[出力例]

10886

※AtCoderテストケースより

[入力例]

19876

[出力例]

2219958

[入力例]

[出力例]

[入力例]

[出力例]

108

[入力例]

2023

[出力例]

96560

[入力例]

200000

[出力例]

39745938

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    };
    
    // 3. 各連結成分に分解.
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    vvi gSub(idx);
    rep(i, N) gSub[c[i] - 1].pb(i);
    
    // 4. 判定.
    bool ok = true;
    rep(i, idx){
        int e = 0;
        for(auto &x : gSub[i]) e += G[x].size();
        if(e != gSub[i].size() * 2) ok = false;
    }
    
    // 5. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

rep(i, M){

int u, v;

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

--u, --v;

G[u].pb(v);

G[v].pb(u);

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);

}

};

// 3. 各連結成分に分解.

int c[N], idx = 0;

rep(i, N) c[i] = 0;

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

vvi gSub(idx);

rep(i, N) gSub[c[i] - 1].pb(i);

// 4. 判定.

bool ok = true;

rep(i, idx){

int e = 0;

for(auto &x : gSub[i]) e += G[x].size();

if(e != gSub[i].size() * 2) ok = false;

}

// 5. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
Yes

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

[出力例]
Yes

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

[出力例]
No

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

[出力例]
Yes

[入力例]

3 3

2 3

1 1

2 3

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 5

1 2

2 3

3 4

3 5

1 5

[出力例]

Yes

※AtCoderテストケースより

[入力例]

13 16

7 9

7 11

3 8

1 13

11 11

6 11

8 13

2 11

3 3

8 12

9 11

1 11

5 13

3 12

6 9

1 10

[出力例]

※AtCoderテストケースより

[入力例]

7 7

1 6

2 6

1 7

2 7

3 4

3 5

4 5

[出力例]

Yes

[入力例]

5 5

1 1

1 2

3 4

4 5

5 5

[出力例]

Yes

[入力例]

6 6

1 2

2 3

4 5

4 6

5 6

[出力例]

[入力例]

12 12

1 2

2 3

3 4

4 5

6 7

7 8

6 8

9 10

10 11

10 12

11 12

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 292

2023年3月7日

C++ の動作確認をしてみた（９１０）

C++の練習を兼ねて, AtCoder Regular Contest 119 の問題C (ARC Wrecker 2) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 計算できる点が, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc119/editorial/1850
// 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 a first
#define b second
LL C[303030], D[303030];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        LL a;
        scanf("%lld", &a);
        
        // 累積和.
        C[i + 1] = C[i] + ((i & 1) ? -1 : +1) * a;
    }
    
    // 2. 座標圧縮.
    map<LL, int> m;
    rep(i, N + 1) m[C[i + 1]] = 0;
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    
    // 3. 集計.
    LL ans = 0;
    rep(i, N){
        ++D[m[C[i]]];
        ans += D[m[C[i + 1]]];
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc119/editorial/1850

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

#define b second

LL C[303030], D[303030];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

LL a;

scanf("%lld", &a);

// 累積和.

C[i + 1] = C[i] + ((i & 1) ? -1 : +1) * a;

}

// 2. 座標圧縮.

map<LL, int> m;

rep(i, N + 1) m[C[i + 1]] = 0;

int idx = -1;

for(auto &p : m) p.b = ++idx;

// 3. 集計.

LL ans = 0;

rep(i, N){

++D[m[C[i]]];

ans += D[m[C[i + 1]]];

}

// 4. 出力.

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

return 0;

}

[入力例]
5
5 8 8 6 6

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

[入力例]
7
12 8 11 3 3 13 2

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

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

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

[入力例]
14
630551244 683685976 249199599 863395255 667330388 617766025 564631293 614195656 944865979 277535591 390222868 527065404 136842536 971731491

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

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

[出力例]
1

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

[出力例]
11

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

[出力例]
85

[入力例]
500
11 2 3 15 2 19 11 12 10 9 20 15 17 3 6 9 19 18 5 5 10 11 12 10 10 13 16 16 15 5 6 3 13 17 16 7 12 16 2 19 18 5 15 16 9 12 13 9 12 19 5 20 5 9 5 9 19 3 3 20 18 3 13 12 19 13 3 5 19 17 3 8 3 3 6 6 3 17 18 16 13 9 3 9 13 2 13 6 17 18 17 13 8 6 6 12 6 20 3 16 7 5 11 11 1 7 15 7 15 2 7 5 2 19 15 18 8 1 7 17 11 19 11 19 12 5 7 1 1 13 3 3 3 13 7 1 15 1 13 13 6 20 12 20 9 13 3 7 12 6 9 6 11 16 2 15 15 10 2 17 9 9 7 2 15 9 5 8 8 2 12 13 16 16 8 9 15 9 2 10 18 9 16 11 2 18 15 9 13 12 18 12 9 19 15 7 13 3 5 20 5 13 18 1 19 16 9 3 18 18 2 11 18 8 7 1 9 3 2 11 13 7 10 15 7 16 1 15 19 5 7 12 5 10 5 11 18 17 20 2 8 6 10 7 6 3 11 12 17 18 13 12 2 6 15 5 13 16 13 16 1 15 12 6 7 19 16 13 11 8 9 16 17 17 7 16 15 16 20 10 1 15 20 10 19 13 20 13 16 18 12 16 2 3 15 2 13 5 6 18 9 10 1 13 8 19 20 16 3 8 13 11 18 16 3 5 6 9 1 3 3 17 1 16 1 12 10 6 15 5 2 11 6 8 12 8 10 19 11 6 3 19 18 9 10 5 12 20 1 1 2 13 19 12 10 11 9 12 12 3 8 2 9 10 7 20 1 5 19 18 10 11 15 19 16 5 20 5 17 3 16 16 15 18 13 12 15 17 12 8 11 19 7 13 6 19 18 17 18 16 16 13 11 16 1 5 17 1 20 12 6 7 18 13 3 12 18 15 15 6 5 5 5 7 18 17 7 2 15 10 6 7 18 6 20 18 11 1 13 18 19 19 20 7 6 3 15 18 11 10 8 18 17 18 2 1 18 1 5 15 5 20 8 3 2 13 15 18 12 11 12 16 12 3 17 3 7 1 19 16 15 10 12 13 19 16 5 15 19 5 15 10 9 7 11 3 3 13 12 12

[出力例]
903

[入力例]

5 8 8 6 6

[出力例]

※AtCoderテストケースより

[入力例]

12 8 11 3 3 13 2

[出力例]

※AtCoderテストケースより

[入力例]

8 6 3 9 5 4 7 2 1 10

[出力例]

※AtCoderテストケースより

[入力例]

630551244 683685976 249199599 863395255 667330388 617766025 564631293 614195656 944865979 277535591 390222868 527065404 136842536 971731491

[出力例]

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2

[出力例]

[入力例]

7 8 9 5 1 4 5 3 4 1 6 3 4 8 3 7 6 4 7 1

[出力例]

[入力例]

100

6 3 1 6 3 10 6 9 3 5 10 9 10 10 1 9 7 8 8 5 9 10 6 2 2 5 3 8 1 7 7 10 7 3 3 10 3 2 7 5 8 8 8 7 5 3 3 3 1 8 10 8 5 9 3 10 3 8 7 7 7 10 5 10 9 7 9 7 5 2 6 3 8 2 9 5 3 1 8 3 9 7 5 6 1 5 1 3 1 9 9 10 5 2 1 3 1 3 9 3

[出力例]

[入力例]

500

11 2 3 15 2 19 11 12 10 9 20 15 17 3 6 9 19 18 5 5 10 11 12 10 10 13 16 16 15 5 6 3 13 17 16 7 12 16 2 19 18 5 15 16 9 12 13 9 12 19 5 20 5 9 5 9 19 3 3 20 18 3 13 12 19 13 3 5 19 17 3 8 3 3 6 6 3 17 18 16 13 9 3 9 13 2 13 6 17 18 17 13 8 6 6 12 6 20 3 16 7 5 11 11 1 7 15 7 15 2 7 5 2 19 15 18 8 1 7 17 11 19 11 19 12 5 7 1 1 13 3 3 3 13 7 1 15 1 13 13 6 20 12 20 9 13 3 7 12 6 9 6 11 16 2 15 15 10 2 17 9 9 7 2 15 9 5 8 8 2 12 13 16 16 8 9 15 9 2 10 18 9 16 11 2 18 15 9 13 12 18 12 9 19 15 7 13 3 5 20 5 13 18 1 19 16 9 3 18 18 2 11 18 8 7 1 9 3 2 11 13 7 10 15 7 16 1 15 19 5 7 12 5 10 5 11 18 17 20 2 8 6 10 7 6 3 11 12 17 18 13 12 2 6 15 5 13 16 13 16 1 15 12 6 7 19 16 13 11 8 9 16 17 17 7 16 15 16 20 10 1 15 20 10 19 13 20 13 16 18 12 16 2 3 15 2 13 5 6 18 9 10 1 13 8 19 20 16 3 8 13 11 18 16 3 5 6 9 1 3 3 17 1 16 1 12 10 6 15 5 2 11 6 8 12 8 10 19 11 6 3 19 18 9 10 5 12 20 1 1 2 13 19 12 10 11 9 12 12 3 8 2 9 10 7 20 1 5 19 18 10 11 15 19 16 5 20 5 17 3 16 16 15 18 13 12 15 17 12 8 11 19 7 13 6 19 18 17 18 16 16 13 11 16 1 5 17 1 20 12 6 7 18 13 3 12 18 15 15 6 5 5 5 7 18 17 7 2 15 10 6 7 18 6 20 18 11 1 13 18 19 19 20 7 6 3 15 18 11 10 8 18 17 18 2 1 18 1 5 15 5 20 8 3 2 13 15 18 12 11 12 16 12 3 17 3 7 1 19 16 15 10 12 13 19 16 5 15 19 5 15 10 9 7 11 3 3 13 12 12

[出力例]

903

■参照サイト
AtCoder Regular Contest 119

2023年3月5日

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

C++の練習を兼ねて, AtCoder Regular Contest 119 の問題A (119 × 2^23 + 1) ～問題B (Electric Board) を解いてみた.

■感想.
1. 問題B は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 計算できる点が, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#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. 2 の 冪乗.
    vl cPow;
    cPow.pb(1);
    while(cPow.back() < N) cPow.pb(cPow.back() << 1);
    
    // 3. a + b + c の 最小値は？
    LL ans = N;
    repx(b, 1, cPow.size()){
        LL a = N / cPow[b];
        LL c = N % cPow[b];
        ans = min(ans, a + b + c);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

#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. 2 の冪乗.

vl cPow;

cPow.pb(1);

while(cPow.back() < N) cPow.pb(cPow.back() << 1);

// 3. a + b + c の最小値は？

LL ans = N;

repx(b, 1, cPow.size()){

LL a = N / cPow[b];

LL c = N % cPow[b];

ans = min(ans, a + b + c);

}

// 4. 出力.

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

return 0;

}

[入力例]
998244353

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

[入力例]
1000000007

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

[入力例]
1

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

[入力例]
998984374864432412

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

[入力例]
20230305

[出力例]
5112

[入力例]
1234567890

[出力例]
10158

[入力例]
202105162100

[出力例]
387924

[入力例]
1000000000000000000

[出力例]
1126526342

[入力例]

998244353

[出力例]

143

※AtCoderのテストケースより

[入力例]

1000000007

[出力例]

49483

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

998984374864432412

[出力例]

2003450165

※AtCoderのテストケースより

[入力例]

20230305

[出力例]

5112

[入力例]

1234567890

[出力例]

10158

[入力例]

202105162100

[出力例]

387924

[入力例]

1000000000000000000

[出力例]

1126526342

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

// 解き直し.
// https://atcoder.jp/contests/arc119/editorial/1841
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<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;
    char s[505050], t[505050];
    scanf("%d %s %s", &N, s, t);
    
    // 2. '0' の 位置.
    vi zs, zt;
    rep(i, N){
        if(s[i] == '0') zs.pb(i);
        if(t[i] == '0') zt.pb(i);
    }
    
    // 3. 集計(操作回数).
    int ans = 0;
    rep(i, zs.size()) ans += (zs[i] != zt[i]);
    
    // 4. 文字列 T に 変換できない.
    if(zs.size() != zt.size()) ans = -1;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc119/editorial/1841

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<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;

char s[505050], t[505050];

scanf("%d %s %s", &N, s, t);

// 2. '0' の位置.

vi zs, zt;

rep(i, N){

if(s[i] == '0') zs.pb(i);

if(t[i] == '0') zt.pb(i);

}

// 3. 集計(操作回数).

int ans = 0;

rep(i, zs.size()) ans += (zs[i] != zt[i]);

// 4. 文字列 T に変換できない.

if(zs.size() != zt.size()) ans = -1;

// 5. 出力.

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

return 0;

}

[入力例]
7
1110110
1010111

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

[入力例]
20
11111000000000011111
11111000000000011111

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

[入力例]
6
111100
111000

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

[入力例]
119
10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011
11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

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

[入力例]
10
0001110110
1101100100

[出力例]
4

[入力例]
30
000111011010100011010100101110
100110010011101101110001100100

[出力例]
12

[入力例]
200
10010100011110101000010001010100111010010100001000111100011111101100100100110001111010011100110101100001110000010011001000110001110101000110001101111011111010001011101001101001110010011000011110111010
01010010011100100010111100110100110010011101111011001011101011111110011000111001100010001011011011110010101101000000000101010001011010010101011000000100111010100000001111011110011101100011110000100110

[出力例]
96

[入力例]

1110110

1010111

[出力例]

※AtCoderテストケースより

[入力例]

11111000000000011111

[出力例]

※AtCoderテストケースより

[入力例]

111100

111000

[出力例]

-1

※AtCoderテストケースより

[入力例]

119

10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011

11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

[出力例]

※AtCoderテストケースより

[入力例]

0001110110

1101100100

[出力例]

[入力例]

000111011010100011010100101110

100110010011101101110001100100

[出力例]

[入力例]

200

10010100011110101000010001010100111010010100001000111100011111101100100100110001111010011100110101100001110000010011001000110001110101000110001101111011111010001011101001101001110010011000011110111010

01010010011100100010111100110100110010011101111011001011101011111110011000111001100010001011011011110010101101000000000101010001011010010101011000000100111010100000001111011110011101100011110000100110

[出力例]

■参照サイト
AtCoder Regular Contest 119

C++の練習を兼ねて, AtCoder Beginner Contest 076 の 問題D (AtCoder Express) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 133 の 問題E (Virus Tree 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 127 の 問題F (Absolute Minima) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 008 の 問題D (金塊ゲーム) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 206 の 問題F (Interval Game 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 206 の 問題E (Divide Both) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 205 の 問題E (White and Black Balls) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 292 の 問題C (Four Variables) ～ 問題D (Unicyclic Components) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 119 の 問題C (ARC Wrecker 2) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 119 の 問題A (119 × 2^23 + 1) ～ 問題B (Electric Board) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 076 の問題D (AtCoder Express) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 133 の問題E (Virus Tree 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 127 の問題F (Absolute Minima) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 008 の問題D (金塊ゲーム) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 206 の問題F (Interval Game 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 206 の問題E (Divide Both) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 205 の問題E (White and Black Balls) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 292 の問題C (Four Variables) ～問題D (Unicyclic Components) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 119 の問題C (ARC Wrecker 2) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 119 の問題A (119 × 2^23 + 1) ～問題B (Electric Board) を解いてみた.