C++ | 個人用メモ帳

2022年8月13日

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

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題D (ぴょんぴょんトレーニング) を解いてみた.

■感想.
1. 問題Dは, 方針が絞り込めたので, AC版に到達出来た.
※ 但し, 実行時間は, 7623[ms] だったので, 実行時間制限の 8[sec] に, ギリギリ収まる実装となっている.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題D／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 h[303030];
const LL MOD = 1e9 + 7;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &h[i + 1]);
    int D;
    scanf("%d", &D);
    
    // 2. クエリ回答.
    rep(i, D){
        // 2-1. クエリ入力情報.
        int s, t;
        scanf("%d %d", &s, &t);
        
        // 2-2. dp更新.
        LL dp[N + 1];
        rep(j, N + 1) dp[j] = 0;
        dp[s] = 1;
        repx(j, s, t){
            // 現在地点.
            LL cur = dp[j];
            
            // 区間[j + 1, j + h[j] + 1) へ ジャンプ.
            rep(k, h[j]){
                int n = j + k + 1;
                if(n <= N) dp[n] += cur, dp[n] %= MOD;
                else       break;
            }
        }
        
        // 2-3. 出力.
        printf("%lld\n", dp[t]);
    }
    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 h[303030];

const LL MOD = 1e9 + 7;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

int D;

scanf("%d", &D);

// 2. クエリ回答.

rep(i, D){

// 2-1. クエリ入力情報.

int s, t;

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

// 2-2. dp更新.

LL dp[N + 1];

rep(j, N + 1) dp[j] = 0;

dp[s] = 1;

repx(j, s, t){

// 現在地点.

LL cur = dp[j];

// 区間[j + 1, j + h[j] + 1) へジャンプ.

rep(k, h[j]){

int n = j + k + 1;

if(n <= N) dp[n] += cur, dp[n] %= MOD;

else break;

}

// 2-3. 出力.

printf("%lld\n", dp[t]);

}

return 0;

}

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

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

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

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

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

[出力例]
2
4
14
216
16
657
13

[入力例]
100
5 2 5 1 8 10 8 2 9 1 1 5 7 9 7 7 6 1 6 2 2 1 10 6 2 2 4 2 8 6 1 4 1 4 6 8 5 1 9 4 8 1 6 5 1 2 7 10 9 1 10 9 7 9 4 7 2 2 4 3 9 8 4 1 7 1 4 1 5 1 7 7 10 7 2 1 7 5 4 3 9 5 6 7 8 5 8 5 7 10 3 4 1 2 5 9 8 10 3 2
15
57 78
36 88
81 100
28 41
46 51
41 53
18 40
74 93
62 80
90 98
3 21
7 36
70 94
99 100
84 98

[出力例]
92250
461505895
127192
1122
12
684
108651
136102
20899
68
27120
12050088
2109316
1
4064

[入力例]

1 2 3 2 2 1 1

2 6

5 7

1 7

[出力例]

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2 6 5 3 5

3 7

2 9

1 10

1 11

[出力例]

175

※AtCoderテストケースより

[入力例]

3 9 10 8 4 2 9 5 2 3 2 1

3 5

4 7

1 6

2 11

3 8

1 12

5 10

[出力例]

216

657

[入力例]

100

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

57 78

36 88

81 100

28 41

46 51

41 53

18 40

74 93

62 80

90 98

3 21

7 36

70 94

99 100

84 98

[出力例]

92250

461505895

127192

1122

684

108651

136102

20899

27120

12050088

2109316

4064

■参照サイト
AtCoder Regular Contest 027

2022年8月12日2022年8月12日

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

C++の練習を兼ねて, AtCoder Regular Contest 140 の問題C (ABS Permutation (LIS ver.)) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 解説のロジックで, 条件を満たす順列を抽出できることが, 非常に印象的だった.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc140/editorial/3893
// 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, X;
    scanf("%d %d", &N, &X);
    int M = N / 2;
    
    // 2. N が 奇数.
    if(N & 1){
        // 2-1. X が M + 1.
        if(X == M + 1){
            int cur = X, sign = -1;
            rep(i, N){
                sign *= -1;
                cur += i * sign;
                printf("%d%s", cur, (i < N - 1) ? " " : "\n");
            }
        }
        
        // 2-2. X が M + 1 以外.
        if(X != M + 1){
            vi v;
            rep(i, N) if(X != i + 1) v.pb(i + 1);
            int cur = M - 1, sign = -1;
            printf("%d ", X);
            rep(i, N - 1){
                cur += i * sign;
                printf("%d%s", v[cur], (i < N - 2) ? " " : "\n");
                sign *= -1;
            }
        }
    }
    
    // 3. N が 偶数.
    if(!(N & 1)){
        // 3-1. X が M or M + 1.
        if(X == M || X == M + 1){
            int cur = X, sign = (X == M) ? -1 : 1;
            rep(i, N){
                cur += i * sign;
                sign *= -1;
                printf("%d%s", cur, (i < N - 1) ? " " : "\n");
            }
        }
        
        // 3-2. X が M, M + 1 以外.
        if(X != M && X != M + 1){
            vi v;
            rep(i, N) if(X != i + 1) v.pb(i + 1);
            int cur = M - 1, sign = -1;
            printf("%d %d ", X, v[cur]);
            rep(i, N - 2){
                cur += (i + 1) * sign;
                printf("%d%s", v[cur], (i < N - 3) ? " " : "\n");
                sign *= -1;
            }
        }
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc140/editorial/3893

// 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, X;

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

int M = N / 2;

// 2. N が奇数.

if(N & 1){

// 2-1. X が M + 1.

if(X == M + 1){

int cur = X, sign = -1;

rep(i, N){

sign *= -1;

cur += i * sign;

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

}

// 2-2. X が M + 1 以外.

if(X != M + 1){

vi v;

rep(i, N) if(X != i + 1) v.pb(i + 1);

int cur = M - 1, sign = -1;

printf("%d ", X);

rep(i, N - 1){

cur += i * sign;

printf("%d%s", v[cur], (i < N - 2) ? " " : "\n");

sign *= -1;

}

// 3. N が偶数.

if(!(N & 1)){

// 3-1. X が M or M + 1.

if(X == M || X == M + 1){

int cur = X, sign = (X == M) ? -1 : 1;

rep(i, N){

cur += i * sign;

sign *= -1;

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

}

// 3-2. X が M, M + 1 以外.

if(X != M && X != M + 1){

vi v;

rep(i, N) if(X != i + 1) v.pb(i + 1);

int cur = M - 1, sign = -1;

printf("%d %d ", X, v[cur]);

rep(i, N - 2){

cur += (i + 1) * sign;

printf("%d%s", v[cur], (i < N - 3) ? " " : "\n");

sign *= -1;

}

return 0;

}

[入力例]
3 2

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

[入力例]
3 1

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

[入力例]
6 1

[出力例]
1 4 3 5 2 6

[入力例]
6 3

[出力例]
3 4 2 5 1 6

[入力例]
6 4

[出力例]
4 3 5 2 6 1

[入力例]
7 3

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

[入力例]
7 4

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

[入力例]
7 5

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

[入力例]
30 15

[出力例]
15 16 14 17 13 18 12 19 11 20 10 21 9 22 8 23 7 24 6 25 5 26 4 27 3 28 2 29 1 30

[入力例]
123 62

[出力例]
62 61 63 60 64 59 65 58 66 57 67 56 68 55 69 54 70 53 71 52 72 51 73 50 74 49 75 48 76 47 77 46 78 45 79 44 80 43 81 42 82 41 83 40 84 39 85 38 86 37 87 36 88 35 89 34 90 33 91 32 92 31 93 30 94 29 95 28 96 27 97 26 98 25 99 24 100 23 101 22 102 21 103 20 104 19 105 18 106 17 107 16 108 15 109 14 110 13 111 12 112 11 113 10 114 9 115 8 116 7 117 6 118 5 119 4 120 3 121 2 122 1 123

[入力例]

3 2

[出力例]

2 1 3

※AtCoderのテストケースより

[入力例]

3 1

[出力例]

1 2 3

※AtCoderのテストケースより

[入力例]

6 1

[出力例]

1 4 3 5 2 6

[入力例]

6 3

[出力例]

3 4 2 5 1 6

[入力例]

6 4

[出力例]

4 3 5 2 6 1

[入力例]

7 3

[出力例]

3 4 5 2 6 1 7

[入力例]

7 4

[出力例]

4 3 5 2 6 1 7

[入力例]

7 5

[出力例]

5 3 4 2 6 1 7

[入力例]

30 15

[出力例]

15 16 14 17 13 18 12 19 11 20 10 21 9 22 8 23 7 24 6 25 5 26 4 27 3 28 2 29 1 30

[入力例]

123 62

[出力例]

62 61 63 60 64 59 65 58 66 57 67 56 68 55 69 54 70 53 71 52 72 51 73 50 74 49 75 48 76 47 77 46 78 45 79 44 80 43 81 42 82 41 83 40 84 39 85 38 86 37 87 36 88 35 89 34 90 33 91 32 92 31 93 30 94 29 95 28 96 27 97 26 98 25 99 24 100 23 101 22 102 21 103 20 104 19 105 18 106 17 107 16 108 15 109 14 110 13 111 12 112 11 113 10 114 9 115 8 116 7 117 6 118 5 119 4 120 3 121 2 122 1 123

■参照サイト
AtCoder Regular Contest 140

2022年8月12日2022年8月12日

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

C++の練習を兼ねて, AtCoder Regular Contest 140 の問題A (Right String) ～問題B (Shorten ARC) を解いてみた.

■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc140/editorial/3964
// 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 main(){
    
    // 1. 入力情報.
    int N, K;
    char c[202020];
    scanf("%d %d %s", &N, &K, c);
    string s(c);
    s += s;
    
    // 2. 約数.
    auto div = [&](int X) -> set<int> {
        set<int> ret;
        repx(d, 1, (int)sqrt(X) + 1){
            if(!(X % d)){
                ret.insert(d);
                if(d * d != X) ret.insert(X / d);
            }
        }
        return ret;
    };
    
    // 3. N の 約数.
    set<int> nDiv = div(N);
    
    // 4. f[S] の 有り得る最小値は？
    int ans = 2020202020;
    for(auto &m : nDiv){
        string cur = s;
        int d = 0;
        
        // f[S] = m が 可能か？
        rep(i, m){
            // 各文字の出現回数.
            int memo[26];
            rep(j, 26) memo[j] = 0;
            rep(j, N / m) ++memo[cur[i + m * j] - 'a'];
            
            // 最大値.
            int mCur = 0;
            rep(j, 26) mCur = max(mCur, memo[j]);
            
            // 差分.
            // -> 最大値の内, いずれか, 一つに合わせるため, 最大値 1個分 を 減算.
            rep(j, 26) d += memo[j];
            d -= mCur;
        }
        
        // 最小値更新.
        // -> 最小 m が, 見つかったことになるため, 終了.
        if(d <= K){
            ans = min(ans, m);
            break;
        }
    }
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc140/editorial/3964

// 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 main(){

// 1. 入力情報.

int N, K;

char c[202020];

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

string s(c);

s += s;

// 2. 約数.

auto div = [&](int X) -> set<int> {

set<int> ret;

repx(d, 1, (int)sqrt(X) + 1){

if(!(X % d)){

ret.insert(d);

if(d * d != X) ret.insert(X / d);

}

return ret;

};

// 3. N の約数.

set<int> nDiv = div(N);

// 4. f[S] の有り得る最小値は？

int ans = 2020202020;

for(auto &m : nDiv){

string cur = s;

int d = 0;

// f[S] = m が可能か？

rep(i, m){

// 各文字の出現回数.

int memo[26];

rep(j, 26) memo[j] = 0;

rep(j, N / m) ++memo[cur[i + m * j] - 'a'];

// 最大値.

int mCur = 0;

rep(j, 26) mCur = max(mCur, memo[j]);

// 差分.

// -> 最大値の内, いずれか, 一つに合わせるため, 最大値 1個分を減算.

rep(j, 26) d += memo[j];

d -= mCur;

}

// 最小値更新.

// -> 最小 m が, 見つかったことになるため, 終了.

if(d <= K){

ans = min(ans, m);

break;

}

// 5. 出力.

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

return 0;

}

[入力例]
4 1
abac

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

[入力例]
10 0
aaaaaaaaaa

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

[入力例]
50 39
fmrbfvlfopklpalqehekzachoddrdcxqqfcgressccewbagfnp

[出力例]
10

[入力例]
100 77
rawmtbwjsjgnjmpafljmtayqtmjomnknutldmhzjsyouegubketezielclyuusdbaxlogxrlevlnpmxtfpkxqkyichgwujcwmkho

[出力例]
20

[入力例]
250 185
zvsgwjqbirpmmrnvnuosfxdzucqeolhbijogtrigujfnuxlvmiugpyljrjdxvkxifdrjcsdwftnnsjxguixecbwganebcpnoaatienaohbwwudjsxesvxvgsykuwpelbnmgirrxokffrmcoutgjuogzfvfwtikxbvftsylturlbifsydhimgfoimcwsvthsdnjytbpywnmjaoghgdtmsdwhevvzpfymlziunrjcakpkfljdifkxjudcffj

[出力例]
50

[入力例]
5000 2022
mofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmctascpeqtlversbzhotisfqiifovrrpbpwctjjuujptwaxppjgkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmdxdxqlkqrberieoznulkbxdvrlzxfpxgghshodiajmrwovnqmvgmuwdacyxtjgjdypdmsmceizqyfqdqjzvahmutgtacenldomphsmixwdcmwllxooqcimphxrhtmxobupgneeyrxmlfwgtbecjyzwdqdfkxsilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcqylajdbwfpsxebfmtwelmrkqgypaaxurrvihhxjpqjrvxvnlcgefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmsbdnlwfikfsocklkiirbvmeibiqelisfftgllchnqwzxfpimhbmcyzgwpkyfrafnggpdlmvniptuqfwrrvhobsswrwalnaaacsgyshwszlrsgjanykvtjqeurruxioqrjwdwefqwtxfelessqpbqcgguxqftoilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibccgkpfnzrwgplrvsyxvfepmscvlcidyzweirtegdsgifuqifrjgefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmkulealhqpcazqvehepghlztgazeyutiinlamabupafvwpjnhlccvalhcfqxlptwqxznsbakneccjwwyjwlgwcnrlvuystrwfturqlbdgmuodiuezxxaszzabaoteczkqgxtndduqpuysmuoxybthpgripoxvbilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcdqobykmiafzjmxrlrkpmgufusepxymprjbifhpisukettxypdgefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmqgeveqgzhxduxmxqtgpwykehjglxkholhsepilctuaxvqyqnrchbbqxaqowljlplastpcxugsiesansceenvtmlciewuvqqriamhebpirmwrzbvibtmxtvnfukmipwtgmquzfyrhzhtrukohvpemiwjbskvfcilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcpxwnqiwyismhssaulvygsccgjzneoyeblbnhpfqnyglgezgcegefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcm

[出力例]
250
※ 整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]

4 1

abac

[出力例]

※AtCoderのテストケースより

[入力例]

10 0

aaaaaaaaaa

[出力例]

※AtCoderのテストケースより

[入力例]

50 39

fmrbfvlfopklpalqehekzachoddrdcxqqfcgressccewbagfnp

[出力例]

[入力例]

100 77

rawmtbwjsjgnjmpafljmtayqtmjomnknutldmhzjsyouegubketezielclyuusdbaxlogxrlevlnpmxtfpkxqkyichgwujcwmkho

[出力例]

[入力例]

250 185

zvsgwjqbirpmmrnvnuosfxdzucqeolhbijogtrigujfnuxlvmiugpyljrjdxvkxifdrjcsdwftnnsjxguixecbwganebcpnoaatienaohbwwudjsxesvxvgsykuwpelbnmgirrxokffrmcoutgjuogzfvfwtikxbvftsylturlbifsydhimgfoimcwsvthsdnjytbpywnmjaoghgdtmsdwhevvzpfymlziunrjcakpkfljdifkxjudcffj

[出力例]

[入力例]

5000 2022

mofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmctascpeqtlversbzhotisfqiifovrrpbpwctjjuujptwaxppjgkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmdxdxqlkqrberieoznulkbxdvrlzxfpxgghshodiajmrwovnqmvgmuwdacyxtjgjdypdmsmceizqyfqdqjzvahmutgtacenldomphsmixwdcmwllxooqcimphxrhtmxobupgneeyrxmlfwgtbecjyzwdqdfkxsilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcqylajdbwfpsxebfmtwelmrkqgypaaxurrvihhxjpqjrvxvnlcgefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmsbdnlwfikfsocklkiirbvmeibiqelisfftgllchnqwzxfpimhbmcyzgwpkyfrafnggpdlmvniptuqfwrrvhobsswrwalnaaacsgyshwszlrsgjanykvtjqeurruxioqrjwdwefqwtxfelessqpbqcgguxqftoilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibccgkpfnzrwgplrvsyxvfepmscvlcidyzweirtegdsgifuqifrjgefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmkulealhqpcazqvehepghlztgazeyutiinlamabupafvwpjnhlccvalhcfqxlptwqxznsbakneccjwwyjwlgwcnrlvuystrwfturqlbdgmuodiuezxxaszzabaoteczkqgxtndduqpuysmuoxybthpgripoxvbilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcdqobykmiafzjmxrlrkpmgufusepxymprjbifhpisukettxypdgefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmqgeveqgzhxduxmxqtgpwykehjglxkholhsepilctuaxvqyqnrchbbqxaqowljlplastpcxugsiesansceenvtmlciewuvqqriamhebpirmwrzbvibtmxtvnfukmipwtgmquzfyrhzhtrukohvpemiwjbskvfcilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcpxwnqiwyismhssaulvygsccgjzneoyeblbnhpfqnyglgezgcegefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcmmofhhafhcfakhcimiemggefmkmmchfikfgfehagiocmcamjheliblgnlnlingljfkkogelgnagfjckfnmbddeeielncegkllomeadkfcbbfchefcedeakjodlbhmbagceglcacjeibobmmmnnchdamlkjlfddilbgdfgkckcfhcbebgdeigdbeffgelcjahjjjgalenddcjngiblnlkkmjmjloibcgkgbdcffkejddgblicnbdnhhohbcm

[出力例]

250

※ 整数 N が, 問題文の制約条件から範囲外であるケース.

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

// 解き直し.
// https://atcoder.jp/contests/arc140/editorial/3894
// 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 x[202020];
    scanf("%d %s", &N, x);
    string s(x);
    
    // 2. ブロックに分割.
    vi v;
    repx(i, 1, N - 1){
        int a = 0, c = 0;
        // ..XRX.. となる 位置.
        if(s[i - 1] != 'R' && s[i] == 'R' && s[i + 1] != 'R'){
            // 左側 の 'A'.
            repr(j, i - 1, 0){
                if(s[j] == 'A') ++a;
                else            break;
            }
            
            // 右側 の 'C'.
            repx(j, i + 1, N){
                if(s[j] == 'C') ++c;
                else            break;
            }
        }
        
        // ブロックを保存.
        if(a && c) v.pb(min(a, c));
    }
    
    // 3. 集計.
    int ans = 0;
    for(auto &p : v) ans += p;
    ans = min(ans, (int)v.size() * 2);
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc140/editorial/3894

// 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 x[202020];

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

string s(x);

// 2. ブロックに分割.

vi v;

repx(i, 1, N - 1){

int a = 0, c = 0;

// ..XRX.. となる位置.

if(s[i - 1] != 'R' && s[i] == 'R' && s[i + 1] != 'R'){

// 左側の 'A'.

repr(j, i - 1, 0){

if(s[j] == 'A') ++a;

else break;

}

// 右側の 'C'.

repx(j, i + 1, N){

if(s[j] == 'C') ++c;

else break;

}

// ブロックを保存.

if(a && c) v.pb(min(a, c));

}

// 3. 集計.

int ans = 0;

for(auto &p : v) ans += p;

ans = min(ans, (int)v.size() * 2);

// 4. 出力.

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

return 0;

}

[入力例]
6
AARCCC

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

[入力例]
5
AAAAA

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

[入力例]
9
ARCARCARC

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

[入力例]
100
AARRARCRRCACRCACCCACCCCACCRCAARCCARARRCACCACAAARCAARCCAACCRRCCCARRACCCRAARARARCCRRCRAACRRCARAARCCRRR

[出力例]
9

[入力例]
500
ACRRCRRRRCCAARCAACAAACRCCCAAARCACAAAARRAAARCAACCACACRCACCRCACCCAACARRRAARAARARARARRAARCCCRCCRCARARAACACCARAACCRACRCRCCRCRCCCRCRACACCCARRAAAACARCACRCACRCRCAARCRCACACACCRCCACCAACARAARCRARCACRCCRRACAACCARRRAACRRCCRRCRRRRARCRRAAARCRCRCACAACAARCAAARRRCCRCCRCCARARACARCACACAAACCRRCRCCCACARRCRARCCRRAARACRCAACRRCARAAARACRARARCCRCARRCARARACCRACRCRACCACAAACRRRCARCACAAAARACARRARCCRAARRACRRCRACRACACCCACCRRRRCAARAAARRAARRRRARRAAARARCRCRRCCAACACRAACARAACRCCARARCAARCCACACCACCARRCRCARCRAACRCCRRRCCACRARRAACRRRACR

[出力例]
22

[入力例]
3000
ARCACRCAACCRRAACCCRCCCCARACAARRACRRACAACACRACRCCRACCRCRARRCARCCCCRRRRRCACCACCCRRARRRARCRACAARCCCAARRCARACARRRRRRCAARRCARRRCAACCCRARCCCRCCRRACRRCRARRARRCAAACAACRRAAAARARRCCCRRARCARACARACRRACRCRCRRCAACACACCCACRRCRCAAARCRARCRRRACRCRRAACCCRRARACARRARRAARCAACCARCACRACRCRCARACAACAARRACRCCRRCACACCACRACARACARAACAACAARAARACAARACARCCACCCCAARRRAACRAAACRAARCCCRCCRCCACAACRRARCAACAARCARCRCACACCRRCCCCRCRAAARCCACCARCCRCARAARARAAAARRACRARCRCRCRCCRRACCRCRACCRCCCACCRRRRRCARAAARCRCAAARARACRCACAARCCACCRARCRCRACAARAAAAAARCRRACCRCAARRACCCRRCCAARRCRRCCRCCCCRACCRARACCCRRACRRARARAACCARARAAAARCRCCCCRRRACRCRAARCCRAAARRAARCAARAACCARRRCCARRCRACRAARACCCRRACRRRRRARCRRRRRACCARCCRARARRRRACCRAAACAACCRCRARACCCAARCARARCRCRRCRCACRCCCRAAARRRRCRCRCAARCACARAACRACRAARCARRCCARRACRCRAAARRCAACCCAAACAACACCRCRCRACAACCARCRARRACRRCCACRARCACCARARACARCCAACRCCCCCAAAACCRCRRARAAACCCARRARRARCRRRRRARRRCRRARRRCRAACAARRAAACACCRCCACCRACCCRARACCCRCARCAACCRCCARCCCRCACAAAAARCCRARCACCACCCCRCRCARRRAARRRRRRCRAAACARAAACRRCRCCRCCRACARACAACAARRRRCRCCACCRCARARRCRRARRCCAACCCRACCCACAARRRRCCCAARRRRAARAARACCCCCARCRRRCARACCRCRCCRRRARARRCARRARCARRCCRCACCCAARCARCRCARCACCRAACCARCRCRRARRRCCCAACRARARCCCCRRARRRAARARRRRCRCCARRARRCRCRACCCCCCRCCRCCARARRRAAARCRARCRCRRRCCACCCRRARRCCACRRARACRAACRRARRCARCRRCACRCCACCCRRAARACRRAAAACAACAAARRAACRRCCRACACAAAARCRCCARRCACRRARAACRRCRACAAACRAACRRCRCCCCCAAARAACAACARACCACCRCRACCCARRCACAACRCAAARCARRRRRARRACRCCRCACARARCACCAACAAARCRAARRAARACARCCACRCCARRRRCRCCRAAARCCAACRRCCRRCRARCCRCARCAACRRRAARCRARRARRCACARAAAAACARACCCACRAARAACCCAARRCRAAARCARCAAAAACRRCAAARRCACARCRRCCRARACCCAACACCCCRCAACCCCRCRARRAARARRACCCCRAARRRCACARACRAARRCRRRCCACRACRACRCCACACRARRCCARRACARCRRACCRCAARRCRCRRCRAARRRCCCRACCRRAACRRRRACACAAAAARCCARACACACCRARRCRARCACCCCCRCCARRRRRRRAAARCCCRRCARCAACAAAARCARAACARAACACCRCCCCRCARRCRCARRRRCAACCCCRACCRCCRCRCRCARRCCACRCCARCRAAACAACACCRCAAAACRARAARRRAAARCCCARCCARRRRRCRRCACRRCRACRCCARCARCACARRCARRCRRACRCRARAARCARAARCARCCARACRACACRARARRCRACARCRARCAACCCRCACRRCCARACCCAAAAARARACAAARAAAACRARCRACRRACCCRRCARRCARCRRACACCARCRACCRRCCRARAARAAAACCRCCCRRRCRRCCCCRRRCARRRRRCARAARRCCCRRCARRRCARRRCCCARCCRAACCACACAARCCACRCRCCRCCCCRCAAACRCCRACAAAAACACARAARRCCCACAAARCRRACRCCARCACAACAAAAAACAARAACRAAACCAARAACRAARCRRCCACAACRACRRRCARRCCAACRRCCCRAAAARCCCRARRRCRRAACCACRAACRARARAARRAACRCRCARARACCRRAACRRARCRCCRACARRRCAARAAACCRCRRRCRRRRCACARAAACCRACCCCCRRAARACRACRRACCACARACRRRRCARCCAARACRCAACCCAAARRACRAAACRRAARCRCCRAACRAACAARCCAACACCRRCRCCCRCAARRRRCACCACACCRRACCRARAAACRARRRRARCRACRARRACRCACCRRRARCRAAARCACACARCACRCCARACACARCRCRRARRCACARCARRAARRAAARRCARACAACRCACARRCRACCRCRACACACCCAARCAACACRCACRRRARARRARRCRRCRCRACARARCCCAACRRACACRCACRCRCAACCRARRRRRARCCCRRARCRCCCRRCACRRRRRRARRAARACARCARRCRACRAACRARRRAARARAAARAACCCCACRAAAACCAARRRCCCACCRCCRCCCRACAAARRRCRAAACCRAAACRCARCCCAACCRCCAARRACCRARACARCACARARRAARCCACCCAAAACRCRRCACRACCCCRCCRRCRCRRACRRARRCCARCCARRACAARACRACCCAACACCRRCRCARACRCRCRARCRCCRAACAARCCRARRRCACAAAARCRARARRRRRACCCCCACACRARCCACRRRCARCARRACACRRRRAAAACRRCCRRCCACCRARCACCRCCCAAARCCRCCRRCCCARRCAACCCRACAAAAAARACCCACCAARCARCCA

[出力例]
133

[入力例]

AARCCC

[出力例]

※AtCoderのテストケースより

[入力例]

AAAAA

[出力例]

※AtCoderのテストケースより

[入力例]

ARCARCARC

[出力例]

※AtCoderのテストケースより

[入力例]

100

AARRARCRRCACRCACCCACCCCACCRCAARCCARARRCACCACAAARCAARCCAACCRRCCCARRACCCRAARARARCCRRCRAACRRCARAARCCRRR

[出力例]

[入力例]

500

ACRRCRRRRCCAARCAACAAACRCCCAAARCACAAAARRAAARCAACCACACRCACCRCACCCAACARRRAARAARARARARRAARCCCRCCRCARARAACACCARAACCRACRCRCCRCRCCCRCRACACCCARRAAAACARCACRCACRCRCAARCRCACACACCRCCACCAACARAARCRARCACRCCRRACAACCARRRAACRRCCRRCRRRRARCRRAAARCRCRCACAACAARCAAARRRCCRCCRCCARARACARCACACAAACCRRCRCCCACARRCRARCCRRAARACRCAACRRCARAAARACRARARCCRCARRCARARACCRACRCRACCACAAACRRRCARCACAAAARACARRARCCRAARRACRRCRACRACACCCACCRRRRCAARAAARRAARRRRARRAAARARCRCRRCCAACACRAACARAACRCCARARCAARCCACACCACCARRCRCARCRAACRCCRRRCCACRARRAACRRRACR

[出力例]

[入力例]

3000

ARCACRCAACCRRAACCCRCCCCARACAARRACRRACAACACRACRCCRACCRCRARRCARCCCCRRRRRCACCACCCRRARRRARCRACAARCCCAARRCARACARRRRRRCAARRCARRRCAACCCRARCCCRCCRRACRRCRARRARRCAAACAACRRAAAARARRCCCRRARCARACARACRRACRCRCRRCAACACACCCACRRCRCAAARCRARCRRRACRCRRAACCCRRARACARRARRAARCAACCARCACRACRCRCARACAACAARRACRCCRRCACACCACRACARACARAACAACAARAARACAARACARCCACCCCAARRRAACRAAACRAARCCCRCCRCCACAACRRARCAACAARCARCRCACACCRRCCCCRCRAAARCCACCARCCRCARAARARAAAARRACRARCRCRCRCCRRACCRCRACCRCCCACCRRRRRCARAAARCRCAAARARACRCACAARCCACCRARCRCRACAARAAAAAARCRRACCRCAARRACCCRRCCAARRCRRCCRCCCCRACCRARACCCRRACRRARARAACCARARAAAARCRCCCCRRRACRCRAARCCRAAARRAARCAARAACCARRRCCARRCRACRAARACCCRRACRRRRRARCRRRRRACCARCCRARARRRRACCRAAACAACCRCRARACCCAARCARARCRCRRCRCACRCCCRAAARRRRCRCRCAARCACARAACRACRAARCARRCCARRACRCRAAARRCAACCCAAACAACACCRCRCRACAACCARCRARRACRRCCACRARCACCARARACARCCAACRCCCCCAAAACCRCRRARAAACCCARRARRARCRRRRRARRRCRRARRRCRAACAARRAAACACCRCCACCRACCCRARACCCRCARCAACCRCCARCCCRCACAAAAARCCRARCACCACCCCRCRCARRRAARRRRRRCRAAACARAAACRRCRCCRCCRACARACAACAARRRRCRCCACCRCARARRCRRARRCCAACCCRACCCACAARRRRCCCAARRRRAARAARACCCCCARCRRRCARACCRCRCCRRRARARRCARRARCARRCCRCACCCAARCARCRCARCACCRAACCARCRCRRARRRCCCAACRARARCCCCRRARRRAARARRRRCRCCARRARRCRCRACCCCCCRCCRCCARARRRAAARCRARCRCRRRCCACCCRRARRCCACRRARACRAACRRARRCARCRRCACRCCACCCRRAARACRRAAAACAACAAARRAACRRCCRACACAAAARCRCCARRCACRRARAACRRCRACAAACRAACRRCRCCCCCAAARAACAACARACCACCRCRACCCARRCACAACRCAAARCARRRRRARRACRCCRCACARARCACCAACAAARCRAARRAARACARCCACRCCARRRRCRCCRAAARCCAACRRCCRRCRARCCRCARCAACRRRAARCRARRARRCACARAAAAACARACCCACRAARAACCCAARRCRAAARCARCAAAAACRRCAAARRCACARCRRCCRARACCCAACACCCCRCAACCCCRCRARRAARARRACCCCRAARRRCACARACRAARRCRRRCCACRACRACRCCACACRARRCCARRACARCRRACCRCAARRCRCRRCRAARRRCCCRACCRRAACRRRRACACAAAAARCCARACACACCRARRCRARCACCCCCRCCARRRRRRRAAARCCCRRCARCAACAAAARCARAACARAACACCRCCCCRCARRCRCARRRRCAACCCCRACCRCCRCRCRCARRCCACRCCARCRAAACAACACCRCAAAACRARAARRRAAARCCCARCCARRRRRCRRCACRRCRACRCCARCARCACARRCARRCRRACRCRARAARCARAARCARCCARACRACACRARARRCRACARCRARCAACCCRCACRRCCARACCCAAAAARARACAAARAAAACRARCRACRRACCCRRCARRCARCRRACACCARCRACCRRCCRARAARAAAACCRCCCRRRCRRCCCCRRRCARRRRRCARAARRCCCRRCARRRCARRRCCCARCCRAACCACACAARCCACRCRCCRCCCCRCAAACRCCRACAAAAACACARAARRCCCACAAARCRRACRCCARCACAACAAAAAACAARAACRAAACCAARAACRAARCRRCCACAACRACRRRCARRCCAACRRCCCRAAAARCCCRARRRCRRAACCACRAACRARARAARRAACRCRCARARACCRRAACRRARCRCCRACARRRCAARAAACCRCRRRCRRRRCACARAAACCRACCCCCRRAARACRACRRACCACARACRRRRCARCCAARACRCAACCCAAARRACRAAACRRAARCRCCRAACRAACAARCCAACACCRRCRCCCRCAARRRRCACCACACCRRACCRARAAACRARRRRARCRACRARRACRCACCRRRARCRAAARCACACARCACRCCARACACARCRCRRARRCACARCARRAARRAAARRCARACAACRCACARRCRACCRCRACACACCCAARCAACACRCACRRRARARRARRCRRCRCRACARARCCCAACRRACACRCACRCRCAACCRARRRRRARCCCRRARCRCCCRRCACRRRRRRARRAARACARCARRCRACRAACRARRRAARARAAARAACCCCACRAAAACCAARRRCCCACCRCCRCCCRACAAARRRCRAAACCRAAACRCARCCCAACCRCCAARRACCRARACARCACARARRAARCCACCCAAAACRCRRCACRACCCCRCCRRCRCRRACRRARRCCARCCARRACAARACRACCCAACACCRRCRCARACRCRCRARCRCCRAACAARCCRARRRCACAAAARCRARARRRRRACCCCCACACRARCCACRRRCARCARRACACRRRRAAAACRRCCRRCCACCRARCACCRCCCAAARCCRCCRRCCCARRCAACCCRACAAAAAARACCCACCAARCARCCA

[出力例]

133

■参照サイト
AtCoder Regular Contest 140

2022年8月10日2022年8月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 263 の問題E (Sugoroku 3) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. Binary Indexed Tree の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 苦手な動的計画法の訓練も積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc263/editorial/4546
// 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 = 998244353;
LL a[202020], dp[202020];

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

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
// -> MOD版 に 改変(2022/06/21).
template<typename T>
struct BIT{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1){
        for(i++; i <= n; i += i & -i) d[i] = (d[i] + x) % MOD;
    }
    T sum(int i){
        T x = 0;
        for(i++; i; i -= i & -i) x = (x + d[i]) % MOD;
        return x;
    }
    T sum(int l, int r){
        return (sum(r - 1) + MOD - sum(l - 1)) % MOD;
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N - 1) scanf("%lld", &a[i + 1]);
    
    // 2. dp更新.
    BIT<LL> ft(N + 1);
    repr(i, N - 1, 1){
        // X (= 1 / a[i]) を 計算.
        LL X = mPow(a[i], MOD - 2);
        
        // 区間[i + 1, i + a[i] + 1) の 合計.
        dp[i] += ft.sum(i + 1, i + a[i] + 1);
        dp[i] %= MOD;
        
        // 1 / a[i].
        dp[i] *= X;
        dp[i] %= MOD;
        
        // 1 + X.
        dp[i] += 1;
        dp[i] %= MOD;
        dp[i] += X;
        dp[i] %= MOD;
        
        // dp[i] を 保存.
        ft.add(i, dp[i]);
    }
    
    // 3. 出力.
    printf("%lld\n", dp[1]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc263/editorial/4546

// 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 = 998244353;

LL a[202020], dp[202020];

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

}

// Binary Indexed Tree (Fenwick Tree)

// https://youtu.be/lyHk98daDJo?t=7960

// -> MOD版に改変(2022/06/21).

template<typename T>

struct BIT{

int n;

vector<T> d;

BIT(int n = 0) : n(n), d(n + 1) {}

void add(int i, T x = 1){

for(i++; i <= n; i += i & -i) d[i] = (d[i] + x) % MOD;

}

T sum(int i){

T x = 0;

for(i++; i; i -= i & -i) x = (x + d[i]) % MOD;

return x;

}

T sum(int l, int r){

return (sum(r - 1) + MOD - sum(l - 1)) % MOD;

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. dp更新.

BIT<LL> ft(N + 1);

repr(i, N - 1, 1){

// X (= 1 / a[i]) を計算.

LL X = mPow(a[i], MOD - 2);

// 区間[i + 1, i + a[i] + 1) の合計.

dp[i] += ft.sum(i + 1, i + a[i] + 1);

dp[i] %= MOD;

// 1 / a[i].

dp[i] *= X;

dp[i] %= MOD;

// 1 + X.

dp[i] += 1;

dp[i] %= MOD;

dp[i] += X;

dp[i] %= MOD;

// dp[i] を保存.

ft.add(i, dp[i]);

}

// 3. 出力.

printf("%lld\n", dp[1]);

return 0;

}

[入力例]
3
1 1

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

[入力例]
5
3 1 2 1

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

[入力例]
2
1

[出力例]
2

[入力例]
4
1 2 1

[出力例]
499122181

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

[出力例]
865145111

[入力例]
15
7 13 7 11 2 5 8 7 4 5 2 3 1 1

[出力例]
618977039

[入力例]
50
15 2 36 39 9 23 31 1 33 36 39 38 13 16 24 34 12 10 9 30 29 28 25 15 25 24 17 22 21 20 19 18 17 16 13 12 13 12 7 2 7 5 7 3 5 4 3 2 1

[出力例]
155141928

[入力例]

1 1

[出力例]

※AtCoderテストケースより

[入力例]

3 1 2 1

[出力例]

332748122

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

1 2 1

[出力例]

499122181

[入力例]

5 3 2 1 2 1

[出力例]

865145111

[入力例]

7 13 7 11 2 5 8 7 4 5 2 3 1 1

[出力例]

618977039

[入力例]

15 2 36 39 9 23 31 1 33 36 39 38 13 16 24 34 12 10 9 30 29 28 25 15 25 24 17 22 21 20 19 18 17 16 13 12 13 12 7 2 7 5 7 3 5 4 3 2 1

[出力例]

155141928

■参照サイト
LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）

2022年8月9日

C++ の動作確認をしてみた（７８２）

C++の練習を兼ねて, AtCoder Beginner Contest 263 の問題C (Monotonically Increasing) ～問題D (Left Right Operation) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 問題Cで, 再帰処理の復習が出来たので, 非常に, 良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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, M;
    scanf("%d %d", &N, &M);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, vi& cur, int d){
        // 2-1. 終了条件.
        if(cur.size() == N){
            if(cur.back() <= M) rep(i, N) printf("%d%s", cur[i], (i < N - 1) ? " " : "\n");
            return;
        }
        
        // 2-2. 次へ.
        repx(i, d, M - (N - d) + 1){
            vi nex = cur;
            nex.pb(i);
            self(self, nex, i + 1);
        }
    };
    
    // 3. 出力.
    vi v;
    dfs(dfs, v, 1);
    return 0;
    
}

// 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, M;

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

// 2. dfs.

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

auto dfs = [&](auto&& self, vi& cur, int d){

// 2-1. 終了条件.

if(cur.size() == N){

if(cur.back() <= M) rep(i, N) printf("%d%s", cur[i], (i < N - 1) ? " " : "\n");

return;

}

// 2-2. 次へ.

repx(i, d, M - (N - d) + 1){

vi nex = cur;

nex.pb(i);

self(self, nex, i + 1);

}

};

// 3. 出力.

vi v;

dfs(dfs, v, 1);

return 0;

}

[入力例]
2 3

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

[入力例]
3 5

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

[入力例]
3 3

[出力例]
1 2 3

[入力例]
5 6

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

[入力例]
5 8

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

100

101

102

[入力例]

2 3

[出力例]

1 2

1 3

2 3

※AtCoderテストケースより

[入力例]

3 5

[出力例]

1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

2 3 4

2 3 5

2 4 5

3 4 5

※AtCoderテストケースより

[入力例]

3 3

[出力例]

1 2 3

[入力例]

5 6

[出力例]

1 2 3 4 5

1 2 3 4 6

1 2 3 5 6

1 2 4 5 6

1 3 4 5 6

2 3 4 5 6

[入力例]

5 8

[出力例]

1 2 3 4 5

1 2 3 4 6

1 2 3 4 7

1 2 3 4 8

1 2 3 5 6

1 2 3 5 7

1 2 3 5 8

1 2 3 6 7

1 2 3 6 8

1 2 3 7 8

1 2 4 5 6

1 2 4 5 7

1 2 4 5 8

1 2 4 6 7

1 2 4 6 8

1 2 4 7 8

1 2 5 6 7

1 2 5 6 8

1 2 5 7 8

1 2 6 7 8

1 3 4 5 6

1 3 4 5 7

1 3 4 5 8

1 3 4 6 7

1 3 4 6 8

1 3 4 7 8

1 3 5 6 7

1 3 5 6 8

1 3 5 7 8

1 3 6 7 8

1 4 5 6 7

1 4 5 6 8

1 4 5 7 8

1 4 6 7 8

1 5 6 7 8

2 3 4 5 6

2 3 4 5 7

2 3 4 5 8

2 3 4 6 7

2 3 4 6 8

2 3 4 7 8

2 3 5 6 7

2 3 5 6 8

2 3 5 7 8

2 3 6 7 8

2 4 5 6 7

2 4 5 6 8

2 4 5 7 8

2 4 6 7 8

2 5 6 7 8

3 4 5 6 7

3 4 5 6 8

3 4 5 7 8

3 4 6 7 8

3 5 6 7 8

4 5 6 7 8

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

// 解き直し.
// https://atcoder.jp/contests/abc263/editorial/4549
// 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
LL a[202020], aCum[202020], f[202020], g[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    LL L, R;
    scanf("%d %lld %lld", &N, &L, &R);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 累積和.
    rep(i, N) aCum[i + 1] = aCum[i] + a[i];
    
    // 3. 事前準備.
    // 3-1. f.
    rep(i, N) f[i + 1] = min(f[i] + a[i], L * (i + 1));
    
    // 3-2. g.
    repr(i, N, 1) g[i - 1] = min(g[i] + a[i - 1], R * (N - i + 1));
    
    // 4. 最小値.
    LL ans = 202020202020202020;
    rep(i, N + 1) ans = min(ans, f[i] + g[i]);
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc263/editorial/4549

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

LL a[202020], aCum[202020], f[202020], g[202020];

int main(){

// 1. 入力情報.

int N;

LL L, R;

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

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

// 2. 累積和.

rep(i, N) aCum[i + 1] = aCum[i] + a[i];

// 3. 事前準備.

// 3-1. f.

rep(i, N) f[i + 1] = min(f[i] + a[i], L * (i + 1));

// 3-2. g.

repr(i, N, 1) g[i - 1] = min(g[i] + a[i - 1], R * (N - i + 1));

// 4. 最小値.

LL ans = 202020202020202020;

rep(i, N + 1) ans = min(ans, f[i] + g[i]);

// 5. 出力.

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

return 0;

}

[入力例]
5 4 3
5 5 0 6 3

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

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

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

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

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

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

[出力例]
50

[入力例]
20 55 66
31 102 123 64 -100 45 -53 84 26 -55 90 -68 107 -52 30 81 123 77 -66 93

[出力例]
555

[入力例]
50 543 345
549 274 1038 660 739 275 1021 -1230 964 -555 894 808 1119 -1169 714 -1245 1010 -564 -502 859 -1146 404 948 315 -1194 1138 356 84 306 -360 -381 693 594 -560 431 1219 -569 63 1123 1207 -773 1206 313 -1099 53 390 452 1172 423 430

[出力例]
11000

[入力例]

5 4 3

5 5 0 6 3

[出力例]

※AtCoderテストケースより

[入力例]

4 10 10

1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

10 -5 -3

9 -6 10 -1 2 10 -1 7 -15 5

[出力例]

-58

※AtCoderテストケースより

[入力例]

10 6 5

9 8 7 6 7 8 9 2 4 8

[出力例]

[入力例]

20 55 66

31 102 123 64 -100 45 -53 84 26 -55 90 -68 107 -52 30 81 123 77 -66 93

[出力例]

555

[入力例]

50 543 345

549 274 1038 660 739 275 1021 -1230 964 -555 894 808 1119 -1169 714 -1245 1010 -564 -502 859 -1146 404 948 315 -1194 1138 356 84 306 -360 -381 693 594 -560 431 1219 -569 63 1123 1207 -773 1206 313 -1099 53 390 452 1172 423 430

[出力例]

11000

■参照サイト
LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）

2022年8月7日

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

C++の練習を兼ねて, AtCoder Regular Contest 145 の問題D (Non Arithmetic Progression Set) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 階差数列的なものを考えると, 制約から, はみ出してしまうが, 解説のように, 3進数で考えると, 制約を満たすものを探し出せることが, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc145/editorial/4227
// 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. 入力情報.
    int N;
    LL M;
    scanf("%d %lld", &N, &M);
    
    // 2. 3 の 冪乗.
    vl cPow3;
    cPow3.pb(1);
    while(cPow3.size() < 20){
        // 2-1. 最大値 3倍.
        LL p = 3 * cPow3.back();
        
        // 2-2. 保存.
        cPow3.pb(p);
    }
    // for(auto &p : cPow3) printf("%lld\n", p);
    
    // 3. 良い集合.
    // 3-1. 桁数.
    int n = 0, d = -1;
    while(n < N) n = 1 << (++d);
    // printf("n=%d d=%d\n", n, d);
    
    // 3-2. 良い整数.
    vl S;
    LL t = 0;
    rep(i, N){
        LL cur = 0;
        rep(j, d + 1) if(i & (1 << j)) cur += cPow3[j + 1];
        S.pb(cur);
        t += cur;
    }
    // for(auto &p : S) printf("%lld\n", p);
    
    // 4. 総和の制約を考慮.
    // 4-1. M との 差分.
    LL g = M - t;
    LL q = g / N;
    LL r = g % N;
    if(g < 0 && r != 0){
        --q;
        r += N;
    }
    
    // 4-2. 平行移動.
    rep(i, N) S[i] += q;
    
    // 4-3. 下1桁調整.
    rep(i, r) ++S[i];
    
    // 5. 出力.
    rep(i, N) printf("%lld%s", S[i], (i < N - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc145/editorial/4227

// 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. 入力情報.

int N;

LL M;

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

// 2. 3 の冪乗.

vl cPow3;

cPow3.pb(1);

while(cPow3.size() < 20){

// 2-1. 最大値 3倍.

LL p = 3 * cPow3.back();

// 2-2. 保存.

cPow3.pb(p);

}

// for(auto &p : cPow3) printf("%lld\n", p);

// 3. 良い集合.

// 3-1. 桁数.

int n = 0, d = -1;

while(n < N) n = 1 << (++d);

// printf("n=%d d=%d\n", n, d);

// 3-2. 良い整数.

vl S;

LL t = 0;

rep(i, N){

LL cur = 0;

rep(j, d + 1) if(i & (1 << j)) cur += cPow3[j + 1];

S.pb(cur);

t += cur;

}

// for(auto &p : S) printf("%lld\n", p);

// 4. 総和の制約を考慮.

// 4-1. M との差分.

LL g = M - t;

LL q = g / N;

LL r = g % N;

if(g < 0 && r != 0){

--q;

r += N;

}

// 4-2. 平行移動.

rep(i, N) S[i] += q;

// 4-3. 下1桁調整.

rep(i, r) ++S[i];

// 5. 出力.

rep(i, N) printf("%lld%s", S[i], (i < N - 1) ? " " : "\n");

return 0;

}

[入力例]
3 9

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

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

[入力例]
5 -15

[出力例]
-15 -5 0 2 3
※AtCoderのテストケースより

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

[入力例]
7 0

[出力例]
-16 -13 -8 -5 10 13 19

[入力例]
20 2022

[出力例]
4 7 13 16 31 34 39 42 84 87 93 96 111 114 120 123 246 249 255 258

[入力例]
25 -123

[出力例]
-140 -137 -131 -128 -113 -110 -104 -101 -59 -56 -50 -47 -32 -29 -23 -20 103 106 111 114 129 132 138 141 183

[入力例]
50 20220807

[出力例]
404009 404012 404018 404021 404036 404039 404045 404048 404090 404093 404099 404102 404117 404120 404126 404129 404252 404255 404261 404264 404279 404282 404288 404291 404333 404336 404342 404345 404359 404362 404368 404371 404737 404740 404746 404749 404764 404767 404773 404776 404818 404821 404827 404830 404845 404848 404854 404857 404980 404983

[入力例]
100 1234567

[出力例]
11122 11125 11131 11134 11149 11152 11158 11161 11203 11206 11212 11215 11230 11233 11239 11242 11365 11368 11374 11377 11392 11395 11401 11404 11446 11449 11455 11458 11473 11476 11482 11485 11851 11854 11860 11863 11878 11881 11887 11890 11932 11935 11941 11943 11958 11961 11967 11970 12093 12096 12102 12105 12120 12123 12129 12132 12174 12177 12183 12186 12201 12204 12210 12213 13308 13311 13317 13320 13335 13338 13344 13347 13389 13392 13398 13401 13416 13419 13425 13428 13551 13554 13560 13563 13578 13581 13587 13590 13632 13635 13641 13644 13659 13662 13668 13671 14037 14040 14046 14049

[入力例]

3 9

[出力例]

1 2 6

※AtCoderのテストケースより

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

-1 2 8

[入力例]

5 -15

[出力例]

-15 -5 0 2 3

※AtCoderのテストケースより

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

-13 -10 -4 -1 13

[入力例]

7 0

[出力例]

-16 -13 -8 -5 10 13 19

[入力例]

20 2022

[出力例]

4 7 13 16 31 34 39 42 84 87 93 96 111 114 120 123 246 249 255 258

[入力例]

25 -123

[出力例]

-140 -137 -131 -128 -113 -110 -104 -101 -59 -56 -50 -47 -32 -29 -23 -20 103 106 111 114 129 132 138 141 183

[入力例]

50 20220807

[出力例]

404009 404012 404018 404021 404036 404039 404045 404048 404090 404093 404099 404102 404117 404120 404126 404129 404252 404255 404261 404264 404279 404282 404288 404291 404333 404336 404342 404345 404359 404362 404368 404371 404737 404740 404746 404749 404764 404767 404773 404776 404818 404821 404827 404830 404845 404848 404854 404857 404980 404983

[入力例]

100 1234567

[出力例]

11122 11125 11131 11134 11149 11152 11158 11161 11203 11206 11212 11215 11230 11233 11239 11242 11365 11368 11374 11377 11392 11395 11401 11404 11446 11449 11455 11458 11473 11476 11482 11485 11851 11854 11860 11863 11878 11881 11887 11890 11932 11935 11941 11943 11958 11961 11967 11970 12093 12096 12102 12105 12120 12123 12129 12132 12174 12177 12183 12186 12201 12204 12210 12213 13308 13311 13317 13320 13335 13338 13344 13347 13389 13392 13398 13401 13416 13419 13425 13428 13551 13554 13560 13563 13578 13581 13587 13590 13632 13635 13641 13644 13659 13662 13668 13671 14037 14040 14046 14049

■参照サイト
AtCoder Regular Contest 145

2022年8月6日

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

C++の練習を兼ねて, AtCoder Regular Contest 145 の問題C (Split and Maximize) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. カタラン数に触れることが出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc145/editorial/4225
// 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 = 998244353;
LL FAC[404040], INV[404040];

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, 404040) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, 404040)     INV[i] = mPow(FAC[i], MOD - 2);
    
    // 3. 集計(解説通り).
    LL ans = mPow(2LL, N);
    ans *= FAC[2 * N];
    ans %= MOD;
    ans *= INV[N + 1];
    ans %= MOD;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc145/editorial/4225

// 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 = 998244353;

LL FAC[404040], INV[404040];

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

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 事前計算.

FAC[0] = 1;

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

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

// 3. 集計(解説通り).

LL ans = mPow(2LL, N);

ans *= FAC[2 * N];

ans %= MOD;

ans *= INV[N + 1];

ans %= MOD;

// 4. 出力.

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

return 0;

}

[入力例]
2

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

[入力例]
10000

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

[入力例]
3

[出力例]
240

[入力例]
4

[出力例]
5376

[入力例]
5

[出力例]
161280

[入力例]
2022

[出力例]
569834140

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

10000

[出力例]

391163238

※AtCoderのテストケースより

[入力例]

[出力例]

240

[入力例]

[出力例]

5376

[入力例]

[出力例]

161280

[入力例]

2022

[出力例]

569834140

■参照サイト
AtCoder Regular Contest 145

2022年8月6日2022年8月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 262 の問題F (Erase and Rotate) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. スライド最小値（応用版）を, 確認できたので, 非常に良かったと思う.
3. 実装に苦労したものの, スライド最小値に対して, 理解を, 深めることが出来たので良かったと思う.
4. なお, 解説上の “回転を1回以上行う場合” について, “回転なし” のケースを参考に, スライド最小値で実装したものの, テストケース 05_hand_01.txt の WA を回避出来なかった.
解決方法が見えなかったため, スライド最小値と思われる実装されている上級者の方々のソースから, 変数(r[cur], k2) や処理(dq2.pob(), else) の組み合わせを特定して, 修正版として提出したものである.
5. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc262/editorial/4504
// 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 pub push_back
#define pob pop_back
int p[202020], r[202020];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%d", &p[i]);
    
    // 2. 回転なし.
    // 2-1. シミュレーション.
    int k1 = K;
    deque<int> dq1;
    rep(i, N){
        // スライド最小値.
        // https://phwinx.hatenablog.com/entry/2018/11/17/042646
        // -> 先頭要素に, 最小値が保存されている状態を目指す.
        // 削除.
        while(k1 && !dq1.empty()){
            if(dq1.back() <= p[i]) break;
            --k1;
            dq1.pob();
        }
        
        // 追加.
        dq1.pub(p[i]);
    }
    
    // 2-2. k1 の 残分.
    while(k1 && !dq1.empty()){
        --k1;
        dq1.pob();
    }
    // for(auto &x : dq1) printf("%d ", x);
    // puts("\n-----");
    
    // 3. 回転あり.
    // 3-1. 先頭の項が最小となる回転数.
    int rMin = 0, pMin = N + 1;
    repr(i, N - 1, 0){
        if(N - i <= K && pMin > p[i]){
            rMin = N - i;
            pMin = p[i];
        }
    }
    
    // 3-2. 操作対象の数列.
    vi p2;
    repx(i, N - rMin, N) p2.pub(p[i]), ++r[p[i]];
    rep(i, N - rMin) p2.pub(p[i]);
    
    // 3-3. シミュレーション.
    int k2 = K - rMin;
    deque<int> dq2;
    rep(i, N){
        // 削除.
        // -> スライド最小値 の 考え方を拡張する必要があるとのこと.
        while(!dq2.empty()){
            int cur = dq2.back();
            if(cur <= p2[i]) break;
            // ex.
            // 6 3
            // 4 5 6 1 3 2
            // -> r[cur] と dq2.pob() と --k2 の 処理条件の組み合わせに注意する.
            // -> 組み合わせを間違えると, 1 3 2 4 5 6 のような誤出力となる.
            // -> 05_hand_01.txt で WAとなった原因とみられるもの.
            // -> なお, 1 2 4 5 6 が 期待される出力.
            if(r[cur]){
                dq2.pob();
            }else if(k2){
                --k2;
                dq2.pob();
            }else{
                break;
            }
        }
        
        // 追加.
        dq2.pub(p2[i]);
    }
    
    // 3-4. k2 の 残分.
    while(k2 && !dq2.empty()){
        int cur = dq2.back();
        --k2;
        dq2.pob();
    }
    // for(auto &x : dq2) printf("%d ", x);
    // puts("\n-----");
    
    // 4. 比較.
    bool ok = (dq1 < dq2);
    
    // 5. 出力.
    int n = ok ? dq1.size() : dq2.size();
    rep(i, n) printf("%d%s", ok ? dq1[i] : dq2[i], (i < n - 1) ? " " : "\n");
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

// https://atcoder.jp/contests/abc262/editorial/4504

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

#define pob pop_back

int p[202020], r[202020];

int main(){

// 1. 入力情報.

int N, K;

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

rep(i, N) scanf("%d", &p[i]);

// 2. 回転なし.

// 2-1. シミュレーション.

int k1 = K;

deque<int> dq1;

rep(i, N){

// スライド最小値.

// https://phwinx.hatenablog.com/entry/2018/11/17/042646

// -> 先頭要素に, 最小値が保存されている状態を目指す.

// 削除.

while(k1 && !dq1.empty()){

if(dq1.back() <= p[i]) break;

--k1;

dq1.pob();

}

// 追加.

dq1.pub(p[i]);

}

// 2-2. k1 の残分.

while(k1 && !dq1.empty()){

--k1;

dq1.pob();

}

// for(auto &x : dq1) printf("%d ", x);

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

// 3. 回転あり.

// 3-1. 先頭の項が最小となる回転数.

int rMin = 0, pMin = N + 1;

repr(i, N - 1, 0){

if(N - i <= K && pMin > p[i]){

rMin = N - i;

pMin = p[i];

}

// 3-2. 操作対象の数列.

vi p2;

repx(i, N - rMin, N) p2.pub(p[i]), ++r[p[i]];

rep(i, N - rMin) p2.pub(p[i]);

// 3-3. シミュレーション.

int k2 = K - rMin;

deque<int> dq2;

rep(i, N){

// 削除.

// -> スライド最小値の考え方を拡張する必要があるとのこと.

while(!dq2.empty()){

int cur = dq2.back();

if(cur <= p2[i]) break;

// ex.

// 6 3

// 4 5 6 1 3 2

// -> r[cur] と dq2.pob() と --k2 の処理条件の組み合わせに注意する.

// -> 組み合わせを間違えると, 1 3 2 4 5 6 のような誤出力となる.

// -> 05_hand_01.txt で WAとなった原因とみられるもの.

// -> なお, 1 2 4 5 6 が期待される出力.

if(r[cur]){

dq2.pob();

}else if(k2){

--k2;

dq2.pob();

}else{

break;

}

// 追加.

dq2.pub(p2[i]);

}

// 3-4. k2 の残分.

while(k2 && !dq2.empty()){

int cur = dq2.back();

--k2;

dq2.pob();

}

// for(auto &x : dq2) printf("%d ", x);

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

// 4. 比較.

bool ok = (dq1 < dq2);

// 5. 出力.

int n = ok ? dq1.size() : dq2.size();

rep(i, n) printf("%d%s", ok ? dq1[i] : dq2[i], (i < n - 1) ? " " : "\n");

return 0;

}

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

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

[入力例]
3 0
3 2 1

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

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

[出力例]
1 3 4 7 2 8 11 9
※AtCoderのテストケースより

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

[出力例]
1 5 12 7 4 18 16 8 19 2 17 6 9 3 11

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

[出力例]
1 6 7 2 17 12 9 3 18 8 11 20 4 5

[入力例]
50 32
7 13 37 31 20 14 48 35 27 3 45 23 47 41 38 32 46 6 12 26 39 44 33 36 16 24 11 50 29 5 34 18 1 28 19 4 17 15 25 22 2 43 9 30 49 8 40 42 21 10

[出力例]
1 2 3 23 32 6 12 26 39 44 33 36 16 24 11 50 29 5 34 18

[入力例]
50 49
7 13 37 31 20 14 48 35 27 3 45 23 47 41 38 32 46 6 12 26 39 44 33 36 16 24 11 50 29 5 34 18 1 28 19 4 17 15 25 22 2 43 9 30 49 8 40 42 21 10

[出力例]
1

[入力例]
100 77
7 6 36 85 8 17 38 50 28 22 44 87 59 99 42 81 4 35 45 56 84 89 52 65 77 88 90 70 55 92 23 27 24 72 39 95 14 63 20 48 67 61 100 53 26 73 96 5 97 79 49 98 31 76 33 94 60 78 13 64 32 9 37 51 66 16 57 19 10 75 29 41 82 46 40 12 25 34 30 15 93 68 58 43 2 91 80 62 47 11 21 3 71 18 83 74 54 86 1 69

[出力例]
1 4 5 9 10 12 15 68 58 43 2 91 80 62 47 11 21 3 71 18 83 74 54 86

[入力例]
200 123
125 31 193 196 91 105 61 111 108 159 50 173 194 88 57 37 172 19 104 185 124 96 161 129 35 13 45 99 138 72 154 156 81 151 53 178 179 11 95 86 155 198 92 87 115 89 113 157 162 23 12 49 16 121 117 29 114 85 83 33 149 142 58 137 158 5 52 36 90 127 60 126 80 66 41 100 28 135 69 47 44 82 101 79 174 123 55 17 166 27 143 84 15 94 68 8 190 112 98 199 39 181 128 186 170 163 122 59 145 133 18 4 20 74 76 164 169 136 77 78 62 119 34 38 102 2 167 192 93 144 182 107 120 183 168 63 42 40 9 75 67 64 10 150 146 139 176 24 6 22 97 43 160 177 180 106 189 147 184 132 70 71 175 65 141 187 103 3 30 14 73 165 171 54 116 153 188 130 195 118 109 1 152 32 21 131 7 200 51 134 48 110 148 46 197 56 25 140 191 26

[出力例]
1 5 8 39 59 145 133 18 4 20 74 76 164 169 136 77 78 62 119 34 38 102 2 167 192 93 144 182 107 120 183 168 63 42 40 9 75 67 64 10 150 146 139 176 24 6 22 97 43 160 177 180 106 189 147 184 132 70 71 175 65 141 187 103 3 30 14 73 165 171 54 116 153 188 130 195 118 109

[入力例]
1000 567
692 605 661 39 9 936 931 368 906 789 127 37 583 910 530 886 865 10 788 2 170 814 226 46 996 513 866 228 547 266 357 260 844 701 114 526 815 802 468 17 308 284 19 755 681 898 582 741 31 278 584 14 413 984 479 900 481 631 911 647 889 539 376 434 212 738 419 418 438 415 54 847 319 509 751 854 51 712 965 141 256 850 795 611 868 528 327 962 386 606 769 414 332 679 596 929 77 538 264 25 836 768 321 206 607 722 832 267 499 915 163 125 469 916 586 55 950 123 667 708 43 156 590 143 576 307 207 511 884 378 158 442 353 555 940 373 685 118 627 422 562 171 999 253 448 101 969 841 251 409 370 345 683 806 903 761 358 364 492 752 213 554 662 172 506 658 478 410 956 715 91 563 641 305 926 826 403 666 1000 655 790 888 848 391 525 293 352 963 876 947 989 648 147 372 758 306 801 41 838 323 295 247 338 15 742 896 778 292 728 476 552 575 638 567 592 417 805 22 785 501 988 303 446 632 239 536 879 912 725 365 126 467 273 861 953 745 870 842 289 899 629 772 349 593 709 642 959 6 909 244 645 687 490 621 682 23 429 736 558 161 633 485 243 155 542 68 299 937 630 561 87 735 863 45 917 489 809 180 425 830 13 440 710 724 933 88 779 340 674 711 882 986 656 816 227 727 361 406 329 892 521 309 824 978 35 393 285 160 964 189 635 897 186 350 297 38 794 935 447 439 775 238 44 502 508 5 152 771 948 182 262 646 764 760 510 732 86 787 90 318 351 34 66 918 497 799 183 581 236 961 640 644 696 776 671 951 545 218 83 216 232 360 315 678 215 523 16 699 618 423 591 529 311 192 480 24 477 97 444 754 992 654 428 407 330 50 923 120 139 52 42 913 934 166 73 96 746 825 336 250 196 187 780 1 348 873 199 457 987 904 191 757 326 878 201 810 93 164 598 819 209 695 577 553 995 449 972 669 759 894 743 625 298 672 106 594 272 905 70 395 543 109 550 960 867 173 571 704 531 394 200 713 404 833 431 84 79 798 874 691 537 556 230 211 296 880 72 921 49 565 356 472 811 167 520 636 747 421 205 380 257 800 784 47 495 975 76 928 643 782 612 958 871 33 29 651 990 246 450 202 142 148 694 157 150 665 80 869 475 544 855 639 770 970 840 275 652 69 807 107 111 435 220 234 548 610 829 858 980 159 574 138 570 657 864 108 875 389 92 791 198 739 703 859 254 566 224 730 61 362 53 955 223 774 914 891 117 684 938 237 845 781 369 660 922 181 57 274 130 484 719 169 268 971 437 496 473 78 453 67 930 408 518 763 74 263 149 486 95 993 128 628 18 384 344 634 482 343 585 81 670 381 134 677 441 862 688 500 820 834 668 102 693 587 740 981 233 217 616 622 697 952 942 290 994 249 877 700 944 885 30 64 821 21 347 578 333 604 28 328 240 827 976 846 991 907 458 416 462 144 498 310 954 135 470 887 26 153 967 488 20 60 822 165 765 541 371 94 849 204 129 136 717 367 924 269 957 58 99 3 514 424 608 705 580 354 105 902 803 534 737 374 883 623 133 919 908 609 797 390 579 551 281 777 231 288 85 121 452 569 276 852 314 291 265 750 673 116 813 808 786 188 483 856 258 783 208 219 325 837 653 282 707 145 615 40 533 853 949 387 432 733 411 313 176 966 322 943 675 925 342 762 261 573 245 540 203 723 154 252 377 731 698 983 324 464 512 835 242 773 115 977 927 920 589 184 366 720 392 331 436 400 454 122 559 532 997 283 335 4 650 515 459 194 831 504 383 726 398 595 721 151 839 32 430 113 210 255 767 619 7 426 626 549 146 271 689 190 59 503 796 601 753 602 363 162 734 620 985 62 792 617 624 818 748 546 507 27 603 270 225 487 979 812 341 399 175 443 229 355 277 463 828 649 860 474 564 637 168 517 382 75 396 248 535 505 857 385 124 941 893 597 375 316 516 82 119 221 112 71 901 286 131 968 178 304 433 716 195 388 817 100 659 36 494 137 179 197 491 600 945 749 456 522 302 301 460 193 465 851 557 132 973 259 235 613 998 287 690 766 455 11 572 466 346 932 702 317 588 402 614 48 427 337 104 412 714 599 103 568 140 56 982 461 974 524 664 706 881 729 312 872 279 843 8 185 12 401 823 527 445 174 560 793 300 110 663 397 686 222 359 493 676 241 451 379 756 63 294 946 280 895 939 334 744 214 420 339 177 519 471 98 680 405 65 89 890 320 718 804

[出力例]
1 29 53 57 130 169 268 437 496 473 78 453 67 930 408 518 763 74 263 149 486 95 993 128 628 18 384 344 634 482 343 585 81 670 381 134 677 441 862 688 500 820 834 668 102 693 587 740 981 233 217 616 622 697 952 942 290 994 249 877 700 944 885 30 64 821 21 347 578 333 604 28 328 240 827 976 846 991 907 458 416 462 144 498 310 954 135 470 887 26 153 967 488 20 60 822 165 765 541 371 94 849 204 129 136 717 367 924 269 957 58 99 3 514 424 608 705 580 354 105 902 803 534 737 374 883 623 133 919 908 609 797 390 579 551 281 777 231 288 85 121 452 569 276 852 314 291 265 750 673 116 813 808 786 188 483 856 258 783 208 219 325 837 653 282 707 145 615 40 533 853 949 387 432 733 411 313 176 966 322 943 675 925 342 762 261 573 245 540 203 723 154 252 377 731 698 983 324 464 512 835 242 773 115 977 927 920 589 184 366 720 392 331 436 400 454 122 559 532 997 283 335 4 650 515 459 194 831 504 383 726 398 595 721 151 839 32 430 113 210 255 767 619 7 426 626 549 146 271 689 190 59 503 796 601 753 602 363 162 734 620 985 62 792 617 624 818 748 546 507 27 603 270 225 487 979 812 341 399 175 443 229 355 277 463 828 649 860 474 564 637 168 517 382 75 396 248 535 505 857 385 124 941 893 597 375 316 516 82 119 221 112 71 901 286 131 968 178 304 433 716 195 388 817 100 659 36 494 137 179 197 491 600 945 749 456 522 302 301 460 193 465 851 557 132 973 259 235 613 998 287 690 766 455 11 572 466 346 932 702 317 588 402 614 48 427 337 104 412 714 599 103 568 140 56 982 461 974 524 664 706 881 729 312 872 279 843 8 185 12 401 823 527 445 174 560 793 300 110 663 397 686 222 359 493 676 241 451 379 756 63 294 946 280 895 939 334 744 214 420 339 177 519 471 98 680 405 65 89 890 320 718 804

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

[出力例]
1 2 4 5 6

[入力例]

5 3

4 5 2 3 1

[出力例]

1 2 3

※AtCoderのテストケースより

[入力例]

3 0

3 2 1

[出力例]

3 2 1

※AtCoderのテストケースより

[入力例]

15 10

12 10 7 2 8 11 9 1 6 14 3 15 13 5 4

[出力例]

1 3 4 7 2 8 11 9

※AtCoderのテストケースより

[入力例]

20 5

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

[出力例]

1 5 12 7 4 18 16 8 19 2 17 6 9 3 11

[入力例]

20 7

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

[出力例]

1 6 7 2 17 12 9 3 18 8 11 20 4 5

[入力例]

50 32

7 13 37 31 20 14 48 35 27 3 45 23 47 41 38 32 46 6 12 26 39 44 33 36 16 24 11 50 29 5 34 18 1 28 19 4 17 15 25 22 2 43 9 30 49 8 40 42 21 10

[出力例]

1 2 3 23 32 6 12 26 39 44 33 36 16 24 11 50 29 5 34 18

[入力例]

50 49

7 13 37 31 20 14 48 35 27 3 45 23 47 41 38 32 46 6 12 26 39 44 33 36 16 24 11 50 29 5 34 18 1 28 19 4 17 15 25 22 2 43 9 30 49 8 40 42 21 10

[出力例]

[入力例]

100 77

7 6 36 85 8 17 38 50 28 22 44 87 59 99 42 81 4 35 45 56 84 89 52 65 77 88 90 70 55 92 23 27 24 72 39 95 14 63 20 48 67 61 100 53 26 73 96 5 97 79 49 98 31 76 33 94 60 78 13 64 32 9 37 51 66 16 57 19 10 75 29 41 82 46 40 12 25 34 30 15 93 68 58 43 2 91 80 62 47 11 21 3 71 18 83 74 54 86 1 69

[出力例]

1 4 5 9 10 12 15 68 58 43 2 91 80 62 47 11 21 3 71 18 83 74 54 86

[入力例]

200 123

125 31 193 196 91 105 61 111 108 159 50 173 194 88 57 37 172 19 104 185 124 96 161 129 35 13 45 99 138 72 154 156 81 151 53 178 179 11 95 86 155 198 92 87 115 89 113 157 162 23 12 49 16 121 117 29 114 85 83 33 149 142 58 137 158 5 52 36 90 127 60 126 80 66 41 100 28 135 69 47 44 82 101 79 174 123 55 17 166 27 143 84 15 94 68 8 190 112 98 199 39 181 128 186 170 163 122 59 145 133 18 4 20 74 76 164 169 136 77 78 62 119 34 38 102 2 167 192 93 144 182 107 120 183 168 63 42 40 9 75 67 64 10 150 146 139 176 24 6 22 97 43 160 177 180 106 189 147 184 132 70 71 175 65 141 187 103 3 30 14 73 165 171 54 116 153 188 130 195 118 109 1 152 32 21 131 7 200 51 134 48 110 148 46 197 56 25 140 191 26

[出力例]

1 5 8 39 59 145 133 18 4 20 74 76 164 169 136 77 78 62 119 34 38 102 2 167 192 93 144 182 107 120 183 168 63 42 40 9 75 67 64 10 150 146 139 176 24 6 22 97 43 160 177 180 106 189 147 184 132 70 71 175 65 141 187 103 3 30 14 73 165 171 54 116 153 188 130 195 118 109

[入力例]

1000 567

692 605 661 39 9 936 931 368 906 789 127 37 583 910 530 886 865 10 788 2 170 814 226 46 996 513 866 228 547 266 357 260 844 701 114 526 815 802 468 17 308 284 19 755 681 898 582 741 31 278 584 14 413 984 479 900 481 631 911 647 889 539 376 434 212 738 419 418 438 415 54 847 319 509 751 854 51 712 965 141 256 850 795 611 868 528 327 962 386 606 769 414 332 679 596 929 77 538 264 25 836 768 321 206 607 722 832 267 499 915 163 125 469 916 586 55 950 123 667 708 43 156 590 143 576 307 207 511 884 378 158 442 353 555 940 373 685 118 627 422 562 171 999 253 448 101 969 841 251 409 370 345 683 806 903 761 358 364 492 752 213 554 662 172 506 658 478 410 956 715 91 563 641 305 926 826 403 666 1000 655 790 888 848 391 525 293 352 963 876 947 989 648 147 372 758 306 801 41 838 323 295 247 338 15 742 896 778 292 728 476 552 575 638 567 592 417 805 22 785 501 988 303 446 632 239 536 879 912 725 365 126 467 273 861 953 745 870 842 289 899 629 772 349 593 709 642 959 6 909 244 645 687 490 621 682 23 429 736 558 161 633 485 243 155 542 68 299 937 630 561 87 735 863 45 917 489 809 180 425 830 13 440 710 724 933 88 779 340 674 711 882 986 656 816 227 727 361 406 329 892 521 309 824 978 35 393 285 160 964 189 635 897 186 350 297 38 794 935 447 439 775 238 44 502 508 5 152 771 948 182 262 646 764 760 510 732 86 787 90 318 351 34 66 918 497 799 183 581 236 961 640 644 696 776 671 951 545 218 83 216 232 360 315 678 215 523 16 699 618 423 591 529 311 192 480 24 477 97 444 754 992 654 428 407 330 50 923 120 139 52 42 913 934 166 73 96 746 825 336 250 196 187 780 1 348 873 199 457 987 904 191 757 326 878 201 810 93 164 598 819 209 695 577 553 995 449 972 669 759 894 743 625 298 672 106 594 272 905 70 395 543 109 550 960 867 173 571 704 531 394 200 713 404 833 431 84 79 798 874 691 537 556 230 211 296 880 72 921 49 565 356 472 811 167 520 636 747 421 205 380 257 800 784 47 495 975 76 928 643 782 612 958 871 33 29 651 990 246 450 202 142 148 694 157 150 665 80 869 475 544 855 639 770 970 840 275 652 69 807 107 111 435 220 234 548 610 829 858 980 159 574 138 570 657 864 108 875 389 92 791 198 739 703 859 254 566 224 730 61 362 53 955 223 774 914 891 117 684 938 237 845 781 369 660 922 181 57 274 130 484 719 169 268 971 437 496 473 78 453 67 930 408 518 763 74 263 149 486 95 993 128 628 18 384 344 634 482 343 585 81 670 381 134 677 441 862 688 500 820 834 668 102 693 587 740 981 233 217 616 622 697 952 942 290 994 249 877 700 944 885 30 64 821 21 347 578 333 604 28 328 240 827 976 846 991 907 458 416 462 144 498 310 954 135 470 887 26 153 967 488 20 60 822 165 765 541 371 94 849 204 129 136 717 367 924 269 957 58 99 3 514 424 608 705 580 354 105 902 803 534 737 374 883 623 133 919 908 609 797 390 579 551 281 777 231 288 85 121 452 569 276 852 314 291 265 750 673 116 813 808 786 188 483 856 258 783 208 219 325 837 653 282 707 145 615 40 533 853 949 387 432 733 411 313 176 966 322 943 675 925 342 762 261 573 245 540 203 723 154 252 377 731 698 983 324 464 512 835 242 773 115 977 927 920 589 184 366 720 392 331 436 400 454 122 559 532 997 283 335 4 650 515 459 194 831 504 383 726 398 595 721 151 839 32 430 113 210 255 767 619 7 426 626 549 146 271 689 190 59 503 796 601 753 602 363 162 734 620 985 62 792 617 624 818 748 546 507 27 603 270 225 487 979 812 341 399 175 443 229 355 277 463 828 649 860 474 564 637 168 517 382 75 396 248 535 505 857 385 124 941 893 597 375 316 516 82 119 221 112 71 901 286 131 968 178 304 433 716 195 388 817 100 659 36 494 137 179 197 491 600 945 749 456 522 302 301 460 193 465 851 557 132 973 259 235 613 998 287 690 766 455 11 572 466 346 932 702 317 588 402 614 48 427 337 104 412 714 599 103 568 140 56 982 461 974 524 664 706 881 729 312 872 279 843 8 185 12 401 823 527 445 174 560 793 300 110 663 397 686 222 359 493 676 241 451 379 756 63 294 946 280 895 939 334 744 214 420 339 177 519 471 98 680 405 65 89 890 320 718 804

[出力例]

1 29 53 57 130 169 268 437 496 473 78 453 67 930 408 518 763 74 263 149 486 95 993 128 628 18 384 344 634 482 343 585 81 670 381 134 677 441 862 688 500 820 834 668 102 693 587 740 981 233 217 616 622 697 952 942 290 994 249 877 700 944 885 30 64 821 21 347 578 333 604 28 328 240 827 976 846 991 907 458 416 462 144 498 310 954 135 470 887 26 153 967 488 20 60 822 165 765 541 371 94 849 204 129 136 717 367 924 269 957 58 99 3 514 424 608 705 580 354 105 902 803 534 737 374 883 623 133 919 908 609 797 390 579 551 281 777 231 288 85 121 452 569 276 852 314 291 265 750 673 116 813 808 786 188 483 856 258 783 208 219 325 837 653 282 707 145 615 40 533 853 949 387 432 733 411 313 176 966 322 943 675 925 342 762 261 573 245 540 203 723 154 252 377 731 698 983 324 464 512 835 242 773 115 977 927 920 589 184 366 720 392 331 436 400 454 122 559 532 997 283 335 4 650 515 459 194 831 504 383 726 398 595 721 151 839 32 430 113 210 255 767 619 7 426 626 549 146 271 689 190 59 503 796 601 753 602 363 162 734 620 985 62 792 617 624 818 748 546 507 27 603 270 225 487 979 812 341 399 175 443 229 355 277 463 828 649 860 474 564 637 168 517 382 75 396 248 535 505 857 385 124 941 893 597 375 316 516 82 119 221 112 71 901 286 131 968 178 304 433 716 195 388 817 100 659 36 494 137 179 197 491 600 945 749 456 522 302 301 460 193 465 851 557 132 973 259 235 613 998 287 690 766 455 11 572 466 346 932 702 317 588 402 614 48 427 337 104 412 714 599 103 568 140 56 982 461 974 524 664 706 881 729 312 872 279 843 8 185 12 401 823 527 445 174 560 793 300 110 663 397 686 222 359 493 676 241 451 379 756 63 294 946 280 895 939 334 744 214 420 339 177 519 471 98 680 405 65 89 890 320 718 804

[入力例]

6 3

4 5 6 1 3 2

[出力例]

1 2 4 5 6

■参照サイト
第三回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 262）

2022年8月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 262 の問題E (Red and Blue Graph) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 解説の方針で, 数え上げできることが, 非常に印象的と思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc262/editorial/4479
// 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 = 998244353;
const int LIMIT = 202020;
LL FAC[LIMIT];
LL 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);
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 事前準備.
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = mPow(FAC[i], MOD - 2) % MOD;
    
    // 3. 次数.
    LL e = 0, o = 0;
    rep(i, N){
        if(G[i].size() & 1) ++o;
        else                ++e;
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(i, K / 2 + 1){
        int r = 2 * i;
        if(K - r < 0) break;
        ans += combination(o, r) * combination(e, K - r);
        ans %= MOD;
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc262/editorial/4479

// 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 = 998244353;

const int LIMIT = 202020;

LL FAC[LIMIT];

LL 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);

vvi G(N);

rep(i, M){

int a, b;

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

--a, --b;

G[a].pb(b);

G[b].pb(a);

}

// 2. 事前準備.

FAC[0] = 1;

repx(i, 1, LIMIT) FAC[i] = i * FAC[i - 1] % MOD;

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

// 3. 次数.

LL e = 0, o = 0;

rep(i, N){

if(G[i].size() & 1) ++o;

else ++e;

}

// 4. 集計.

LL ans = 0;

rep(i, K / 2 + 1){

int r = 2 * i;

if(K - r < 0) break;

ans += combination(o, r) * combination(e, K - r);

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
56

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

[出力例]
2485

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

[出力例]
37742

100

[入力例]

4 4 2

1 2

1 3

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

10 10 3

1 2

2 4

1 5

3 6

3 9

4 10

7 8

9 10

5 9

3 4

[出力例]

※AtCoderテストケースより

[入力例]

10 15 3

1 9

1 10

1 2

1 3

1 4

2 3

2 4

3 4

4 5

4 6

4 7

4 8

5 8

6 7

7 8

[出力例]

[入力例]

15 18 6

1 2

1 3

3 2

15 2

15 14

14 13

4 5

4 6

5 6

5 7

7 6

8 9

9 12

8 10

8 12

11 9

11 10

11 12

[出力例]

2485

[入力例]

19 22 8

1 2

1 3

2 4

4 3

10 2

10 11

11 12

12 15

15 14

13 14

10 13

15 7

7 9

8 9

8 5

6 5

7 6

18 5

19 17

18 17

19 18

19 3

[出力例]

37742

■参照サイト
第三回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 262）

2022年8月3日

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

C++の練習を兼ねて, AtCoder Regular Contest 145 の問題B (AB Game) を解いてみた.

■感想.
1. 問題Bは, 方針を絞り込めたので, AC版に到達出来たと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N, A, B;
    scanf("%lld %lld %lld", &N, &A, &B);
    
    // 2. Alice が 勝つゲームの個数は？
    // 2-1. N < A
    LL ans = 0;
    if(N < A){}
    
    // 2-2. N >= A かつ A <= B.
    if(N >= A && A <= B) ans = N - A + 1;
    
    // 2-3. それ以外(N >= A かつ A > B).
    if(N >= A && A > B){
        LL q = N / A, r = N % A;
        ans = q * B - (r < B) * (B - 1 - r);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報.

LL N, A, B;

scanf("%lld %lld %lld", &N, &A, &B);

// 2. Alice が勝つゲームの個数は？

// 2-1. N < A

LL ans = 0;

if(N < A){}

// 2-2. N >= A かつ A <= B.

if(N >= A && A <= B) ans = N - A + 1;

// 2-3. それ以外(N >= A かつ A > B).

if(N >= A && A > B){

LL q = N / A, r = N % A;

ans = q * B - (r < B) * (B - 1 - r);

}

// 3. 出力.

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

return 0;

}

[入力例]
4 2 1

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

[入力例]
27182818284 59045 23356

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

[入力例]
1 1 1

[出力例]
1

[入力例]
1 2 1

[出力例]
0

[入力例]
10 3 7

[出力例]
8

[入力例]
10 7 3

[出力例]
3

[入力例]
47 7 5

[出力例]
30

[入力例]
50 7 5

[出力例]
32

[入力例]
20220803 2022 803

[出力例]
8030000

[入力例]
173205080 756887 729352

[出力例]
166197749

[入力例]

4 2 1

[出力例]

※AtCoderのテストケースより

[入力例]

27182818284 59045 23356

[出力例]

10752495144

※AtCoderのテストケースより

[入力例]

1 1 1

[出力例]

[入力例]

1 2 1

[出力例]

[入力例]

10 3 7

[出力例]

[入力例]

10 7 3

[出力例]

[入力例]

47 7 5

[出力例]

[入力例]

50 7 5

[出力例]

[入力例]

20220803 2022 803

[出力例]

8030000

[入力例]

173205080 756887 729352

[出力例]

166197749

■参照サイト
AtCoder Regular Contest 145

C++の練習を兼ねて, AtCoder Regular Contest 027 の 問題D (ぴょんぴょんトレーニング) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 140 の 問題C (ABS Permutation (LIS ver.)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 140 の 問題A (Right String) ～ 問題B (Shorten ARC) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 263 の 問題E (Sugoroku 3) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 263 の 問題C (Monotonically Increasing) ～ 問題D (Left Right Operation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 145 の 問題D (Non Arithmetic Progression Set) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 145 の 問題C (Split and Maximize) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 262 の 問題F (Erase and Rotate) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 262 の 問題E (Red and Blue Graph) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 145 の 問題B (AB Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題D (ぴょんぴょんトレーニング) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 140 の問題C (ABS Permutation (LIS ver.)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 140 の問題A (Right String) ～問題B (Shorten ARC) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 263 の問題E (Sugoroku 3) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 263 の問題C (Monotonically Increasing) ～問題D (Left Right Operation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 145 の問題D (Non Arithmetic Progression Set) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 145 の問題C (Split and Maximize) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 262 の問題F (Erase and Rotate) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 262 の問題E (Red and Blue Graph) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 145 の問題B (AB Game) を解いてみた.