C++ | 個人用メモ帳

2022年4月23日

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

C++の練習を兼ねて, AtCoder Beginner Contest 245 の問題E (Wrapping Chocolate) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 個人的には, 解説のロジックで, 判定可能であることが, 興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc245/editorial/3635
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using T3 = tuple<int, int, int>;
using vt = vector<T3>;
#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 all(x) x.begin(), x.end()
int a[202020], b[202020], c[202020], d[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    rep(i, M) scanf("%d", &c[i]);
    rep(i, M) scanf("%d", &d[i]);
    
    // 2. sort.
    vt v;
    rep(i, N) v.emplace_back(a[i], b[i], 0);
    rep(i, M) v.emplace_back(c[i], d[i], 1);
    sort(all(v));
    reverse(all(v));
    
    // 3. 判定.
    multiset<int> mst;
    bool ok = true;
    for(auto &t : v){
        // 要素(チョコレート or 箱).
        int h = get<0>(t);
        int w = get<1>(t);
        int f = get<2>(t);
        
        // 箱.
        if(f){
            mst.insert(w);
            continue;
        }
        
        // チョコレート.
        auto it = mst.lower_bound(w);
        if(it == mst.end()){
            ok = false;
            break;
        }
        mst.erase(mst.find(*it));
    }
    
    // 4. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc245/editorial/3635

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using T3 = tuple<int, int, int>;

using vt = vector<T3>;

#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 all(x) x.begin(), x.end()

int a[202020], b[202020], c[202020], d[202020];

int main(){

// 1. 入力情報.

int N, M;

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

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

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

rep(i, M) scanf("%d", &c[i]);

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

// 2. sort.

vt v;

rep(i, N) v.emplace_back(a[i], b[i], 0);

rep(i, M) v.emplace_back(c[i], d[i], 1);

sort(all(v));

reverse(all(v));

// 3. 判定.

multiset<int> mst;

bool ok = true;

for(auto &t : v){

// 要素(チョコレート or 箱).

int h = get<0>(t);

int w = get<1>(t);

int f = get<2>(t);

// 箱.

if(f){

mst.insert(w);

continue;

}

// チョコレート.

auto it = mst.lower_bound(w);

if(it == mst.end()){

ok = false;

break;

}

mst.erase(mst.find(*it));

}

// 4. 出力.

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

return 0;

}

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

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

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

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

[入力例]
1 1
10
100
100
10

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

[入力例]
1 1
10
100
10
100

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

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

[出力例]
No

[入力例]
10 18
54 111 86 23 17 51 87 19 88 37
110 107 53 58 13 33 58 9 63 71
115 68 18 121 86 26 87 93 104 2 67 3 92 117 52 57 102 102
10 123 36 39 91 52 56 106 84 18 67 62 76 107 75 118 63 63

[出力例]
Yes

[入力例]
20 25
867 1461 1449 999 1542 1320 1193 942 1367 1507 1100 516 1226 1234 1092 1445 1216 857 1214 686
1348 1520 567 555 730 1300 1089 717 1488 739 890 959 566 863 1610 804 1731 940 1393 1030
1001 1574 1819 2022 1169 1729 1428 1339 1113 1648 535 697 1310 1088 1425 599 1444 999 1306 576 783 942 2020 1450 1320
713 999 1389 2023 555 1521 1381 628 1258 731 1693 999 594 1516 1527 1099 1359 1276 1393 1235 1591 1595 1688 732 1165

[出力例]
Yes

[入力例]

2 3

2 4

3 2

8 1 5

2 10 5

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 2

1 1

2 2

100 1

[出力例]

※AtCoderテストケースより

[入力例]

1 1

100

[出力例]

※AtCoderテストケースより

[入力例]

1 1

100

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 7

1 6 12 2 12

13 10 9 3 11

7 6 2 12 9 6 12

9 7 7 10 12 11 13

[出力例]

[入力例]

10 18

54 111 86 23 17 51 87 19 88 37

110 107 53 58 13 33 58 9 63 71

115 68 18 121 86 26 87 93 104 2 67 3 92 117 52 57 102 102

10 123 36 39 91 52 56 106 84 18 67 62 76 107 75 118 63 63

[出力例]

Yes

[入力例]

20 25

867 1461 1449 999 1542 1320 1193 942 1367 1507 1100 516 1226 1234 1092 1445 1216 857 1214 686

1348 1520 567 555 730 1300 1089 717 1488 739 890 959 566 863 1610 804 1731 940 1393 1030

1001 1574 1819 2022 1169 1729 1428 1339 1113 1648 535 697 1310 1088 1425 599 1444 999 1306 576 783 942 2020 1450 1320

713 999 1389 2023 555 1521 1381 628 1258 731 1693 999 594 1516 1527 1099 1359 1276 1393 1235 1591 1595 1688 732 1165

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 245

2022年4月22日2022年4月22日

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

C++の練習を兼ねて, AtCoder Beginner Contest 245 の問題C (Choose Elements) ～問題D (Polynomial division) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達出来た.
2. 問題Cで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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 a[202020], b[202020];
bool dp[202020][2];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. dp更新.
    dp[0][0] = dp[0][1] = true;
    repx(i, 1, N){
        // 2-1. 前回, a[i - 1] が, 条件を満たしていた.
        if(dp[i - 1][0]){
            if(abs(a[i] - a[i - 1]) <= K) dp[i][0] = true;
            if(abs(b[i] - a[i - 1]) <= K) dp[i][1] = true;
        }
        
        // 2-2. 前回, b[i - 1] が, 条件を満たしていた.
        if(dp[i - 1][1]){
            if(abs(a[i] - b[i - 1]) <= K) dp[i][0] = true;
            if(abs(b[i] - b[i - 1]) <= K) dp[i][1] = true;
        }
    }
    
    // 3. 出力.
    printf("%s\n", (dp[N - 1][0] || dp[N - 1][1]) ? "Yes" : "No");
    return 0;
    
}

// 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 a[202020], b[202020];

bool dp[202020][2];

int main(){

// 1. 入力情報.

int N, K;

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

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

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

// 2. dp更新.

dp[0][0] = dp[0][1] = true;

repx(i, 1, N){

// 2-1. 前回, a[i - 1] が, 条件を満たしていた.

if(dp[i - 1][0]){

if(abs(a[i] - a[i - 1]) <= K) dp[i][0] = true;

if(abs(b[i] - a[i - 1]) <= K) dp[i][1] = true;

}

// 2-2. 前回, b[i - 1] が, 条件を満たしていた.

if(dp[i - 1][1]){

if(abs(a[i] - b[i - 1]) <= K) dp[i][0] = true;

if(abs(b[i] - b[i - 1]) <= K) dp[i][1] = true;

}

// 3. 出力.

printf("%s\n", (dp[N - 1][0] || dp[N - 1][1]) ? "Yes" : "No");

return 0;

}

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

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

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

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

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

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

[入力例]
5 10
15 12 16 1 12
4 23 8 21 10

[出力例]
Yes

[入力例]
10 20
18 15 67 84 82 99 41 22 59 65
52 36 33 13 30 33 72 63 85 34

[出力例]
No

[入力例]
30 50
5 22 76 137 183 197 135 149 129 160 88 128 155 91 98 17 119 150 122 144 93 172 195 123 99 72 123 100 182 166
50 77 122 185 99 172 222 185 99 123 111 100 77 123 189 69 22 49 65 35 172 176 135 150 140 109 135 150 150 131

[出力例]
Yes

[入力例]

5 4

9 8 3 7 2

1 6 2 9 5

[出力例]

Yes

※AtCoderテストケースより

[入力例]

4 90

1 1 1 100

1 2 3 100

[出力例]

※AtCoderテストケースより

[入力例]

4 1000000000

1 1 1000000000 1000000000

1 1000000000 1 1000000000

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 10

15 12 16 1 12

4 23 8 21 10

[出力例]

Yes

[入力例]

10 20

18 15 67 84 82 99 41 22 59 65

52 36 33 13 30 33 72 63 85 34

[出力例]

[入力例]

30 50

5 22 76 137 183 197 135 149 129 160 88 128 155 91 98 17 119 150 122 144 93 172 195 123 99 72 123 100 182 166

50 77 122 185 99 172 222 185 99 123 111 100 77 123 189 69 22 49 65 35 172 176 135 150 140 109 135 150 150 131

[出力例]

Yes

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

// 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 a[303], b[303], c[606];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N + 1) scanf("%d", &a[i]);
    rep(i, N + M + 1) scanf("%d", &c[i]);
    
    // 2. b を 計算.
    rep(i, M + 1){
        // 計算済みの係数を除外.
        int d = c[N + M - i];
        rep(j, i) if(N + j >= i && M >= j) d -= a[N - i + j] * b[M - j];
        
        // 今回分更新.
        b[M - i] = d / a[N];
    }
    
    // 3. 出力.
    rep(i, M + 1) printf("%d%s", b[i], (i < M) ? " " : "\n");
    return 0;
    
}

// 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 a[303], b[303], c[606];

int main(){

// 1. 入力情報.

int N, M;

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

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

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

// 2. b を計算.

rep(i, M + 1){

// 計算済みの係数を除外.

int d = c[N + M - i];

rep(j, i) if(N + j >= i && M >= j) d -= a[N - i + j] * b[M - j];

// 今回分更新.

b[M - i] = d / a[N];

}

// 3. 出力.

rep(i, M + 1) printf("%d%s", b[i], (i < M) ? " " : "\n");

return 0;

}

[入力例]
1 2
2 1
12 14 8 2

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

[入力例]
1 1
100 1
10000 0 -1

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

[入力例]
3 5
5 1 3 7
15 8 30 33 45 81 31 62 63

[出力例]
3 1 4 1 5 9

[入力例]
7 3
3 1 4 1 5 9 2 6
6 2 14 10 20 28 16 40 22 16 12

[出力例]
2 0 2 2

[入力例]
10 7
1 7 3 2 0 5 0 8 0 7 5
2 14 8 20 20 23 27 55 64 52 53 24 78 26 69 29 52 30

[出力例]
2 0 2 2 0 3 2 6

[入力例]

1 2

2 1

12 14 8 2

[出力例]

6 4 2

※AtCoderテストケースより

[入力例]

1 1

100 1

10000 0 -1

[出力例]

100 -1

※AtCoderテストケースより

[入力例]

3 5

5 1 3 7

15 8 30 33 45 81 31 62 63

[出力例]

3 1 4 1 5 9

[入力例]

7 3

3 1 4 1 5 9 2 6

6 2 14 10 20 28 16 40 22 16 12

[出力例]

2 0 2 2

[入力例]

10 7

1 7 3 2 0 5 0 8 0 7 5

2 14 8 20 20 23 27 55 64 52 53 24 78 26 69 29 52 30

[出力例]

2 0 2 2 0 3 2 6

■参照サイト
AtCoder Beginner Contest 245

2022年4月21日2022年4月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 242 の問題C (1111gal password) ～問題D (ABC Transform) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 問題Cで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 問題Dで, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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--)
const LL MOD = 998244353;
LL dp[10], pd[10];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 初期化.
    repx(j, 1, 10) pd[j] = 1;
    
    // 3. dp更新.
    repx(i, 1, N){
        // 初期化.
        repx(j, 1, 10) dp[j] = 0;
        
        // 今回分更新.
        repx(j, 1, 10){
            // 桁の数字が, 1 小さい.
            if(j > 1){
                dp[j - 1] += pd[j];
                dp[j - 1] %= MOD;
            }
            
            // 桁の数字が, 1 大きい.
            if(j < 9){
                dp[j + 1] += pd[j];
                dp[j + 1] %= MOD;
            }
            
            // 桁の数字が, 等しい.
            dp[j] += pd[j];
            dp[j] %= MOD;
        }
        
        // 前回分更新.
        repx(j, 1, 10) pd[j] = dp[j];
    }
    
    // 4. 集計.
    LL ans = 0;
    repx(j, 1, 10){
        ans += dp[j];
        ans %= MOD;
    }
    
    // 5. 出力.
    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--)

const LL MOD = 998244353;

LL dp[10], pd[10];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 初期化.

repx(j, 1, 10) pd[j] = 1;

// 3. dp更新.

repx(i, 1, N){

// 初期化.

repx(j, 1, 10) dp[j] = 0;

// 今回分更新.

repx(j, 1, 10){

// 桁の数字が, 1 小さい.

if(j > 1){

dp[j - 1] += pd[j];

dp[j - 1] %= MOD;

}

// 桁の数字が, 1 大きい.

if(j < 9){

dp[j + 1] += pd[j];

dp[j + 1] %= MOD;

}

// 桁の数字が, 等しい.

dp[j] += pd[j];

dp[j] %= MOD;

}

// 前回分更新.

repx(j, 1, 10) pd[j] = dp[j];

}

// 4. 集計.

LL ans = 0;

repx(j, 1, 10){

ans += dp[j];

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
4

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

[入力例]
2

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

[入力例]
1000000

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

[入力例]
3

[出力例]
71

[入力例]
5

[出力例]
583

[入力例]
2022

[出力例]
660740445

[入力例]

[出力例]

203

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

1000000

[出力例]

248860093

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

583

[入力例]

2022

[出力例]

660740445

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

// 解き直し.
// https://atcoder.jp/contests/abc242/editorial/3520
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using T3 = tuple<LL, LL, 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--)

int main(){
    
    // 1. 入力情報.
    char x[101010];
    scanf("%s", x);
    string S(x);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, LL t, LL k, LL d) -> T3 {
        // 終了条件(t = 0).
        if(!t) return {0, k, d};
        
        // 終了条件(k = 0).
        if(!k) return {t, 0, d};
        
        // 再帰処理.
        return self(self, t - 1, k / 2, d + 1 + (k % 2));
    };
    
    // 3. クエリ回答.
    int Q;
    scanf("%d", &Q);
    rep(i, Q){
        // クエリ入力情報.
        LL t, k;
        scanf("%lld %lld", &t, &k);
        
        // 変化分.
        T3 p = dfs(dfs, t, k - 1, 0);
        LL a = get<0>(p);
        LL b = get<1>(p);
        LL c = get<2>(p);
        // printf("t=%lld k=%lld a=%lld b=%lld c=%lld\n", t, k, a, b, c);
        
        // 出力.
        LL d = a ? (LL)(S[0] - 'A' + a + c) : (LL)(S[(int)b] - 'A' + c);
        printf("%c\n", (int)(d % 3) + 'A');
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc242/editorial/3520

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using T3 = tuple<LL, LL, 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--)

int main(){

// 1. 入力情報.

char x[101010];

scanf("%s", x);

string S(x);

// 2. dfs.

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

auto dfs = [&](auto&& self, LL t, LL k, LL d) -> T3 {

// 終了条件(t = 0).

if(!t) return {0, k, d};

// 終了条件(k = 0).

if(!k) return {t, 0, d};

// 再帰処理.

return self(self, t - 1, k / 2, d + 1 + (k % 2));

};

// 3. クエリ回答.

int Q;

scanf("%d", &Q);

rep(i, Q){

// クエリ入力情報.

LL t, k;

scanf("%lld %lld", &t, &k);

// 変化分.

T3 p = dfs(dfs, t, k - 1, 0);

LL a = get<0>(p);

LL b = get<1>(p);

LL c = get<2>(p);

// printf("t=%lld k=%lld a=%lld b=%lld c=%lld\n", t, k, a, b, c);

// 出力.

LL d = a ? (LL)(S[0] - 'A' + a + c) : (LL)(S[(int)b] - 'A' + c);

printf("%c\n", (int)(d % 3) + 'A');

}

return 0;

}

[入力例]
ABC
4
0 1
1 1
1 3
1 6

[出力例]
A
B
C
B
※AtCoderテストケースより

[入力例]
CBBAACCCCC
5
57530144230160008 659279164847814847
29622990657296329 861239705300265164
509705228051901259 994708708957785197
176678501072691541 655134104344481648
827291290937314275 407121144297426665

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

[入力例]
ACBCA
10
0 1
0 3
1 1
1 5
2 2
2 13
3 1
3 15
3 26
3 38

[出力例]
A
B
B
C
A
B
A
B
A
C

[入力例]
BBCAABCBCA
20
0 2
0 5
0 9
1 3
1 7
1 17
2 1
2 10
2 25
3 30
3 50
3 77
4 55
4 111
5 22
5 320
6 88
6 123
6 333
7 1111

[出力例]
B
A
C
C
B
A
A
C
B
C
A
B
A
A
A
B
C
C
A
B

100

101

102

103

[入力例]

ABC

0 1

1 1

1 3

1 6

[出力例]

※AtCoderテストケースより

[入力例]

CBBAACCCCC

57530144230160008 659279164847814847

29622990657296329 861239705300265164

509705228051901259 994708708957785197

176678501072691541 655134104344481648

827291290937314275 407121144297426665

[出力例]

※AtCoderテストケースより

[入力例]

ACBCA

0 1

0 3

1 1

1 5

2 2

2 13

3 1

3 15

3 26

3 38

[出力例]

[入力例]

BBCAABCBCA

0 2

0 5

0 9

1 3

1 7

1 17

2 1

2 10

2 25

3 30

3 50

3 77

4 55

4 111

5 22

5 320

6 88

6 123

6 333

7 1111

[出力例]

■参照サイト
AtCoder Beginner Contest 242

2022年4月19日2022年4月19日

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

C++の練習を兼ねて, AtCoder Regular Contest 051 の問題C (掛け算) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 数列の大小関係(※最大値が, 最小値の定数倍以下に収まるケース)が確定するまでシュミレーションして, 残り部分は, 高速累乗で, 計算可能という解説にあるロジックが, 目から鱗だった.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/051/editorial.pdf
// 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
#define all(x) x.begin(), x.end()
const LL MOD = 1e9 + 7;

// 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;
    LL A, B;
    scanf("%d %lld %lld", &N, &A, &B);
    vl a(N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. sort.
    sort(all(a));
    
    // 3. 例外.
    if(A == 1){
        for(auto &p : a) printf("%lld\n", p);
        return 0;
    }
    
    // 4. シュミレーション.
    LL s = a.front(), e = a.back(), C = 0;
    while(s * A < e){
        ++C;
        a.erase(a.begin());
        a.pb(s * A);
        sort(all(a));
        s = a.front();
        e = a.back();
        if(C == B) break;
    }
    // printf("C=%d\n", C);
    
    // 5. 例外.
    if(B == C){
        for(auto &p : a) printf("%lld\n", p);
        return 0;
    }
    
    // 6. 高速累乗.
    // 6-1. 商の部分.
    LL q = (B - C) / N;
    rep(i, N){
        a[i] *= mPow(A, q);
        a[i] %= MOD;
    }
    
    // 6-2. 余り部分.
    int r = (B - C) % N;
    while(r){
        s = a.front();
        a.erase(a.begin());
        a.pb(s * A % MOD);
        --r;
    }
    
    // 7. 出力.
    for(auto &p : a) printf("%lld\n", p);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/data/arc/051/editorial.pdf

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

#define all(x) x.begin(), x.end()

const LL MOD = 1e9 + 7;

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

LL A, B;

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

vl a(N);

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

// 2. sort.

sort(all(a));

// 3. 例外.

if(A == 1){

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

return 0;

}

// 4. シュミレーション.

LL s = a.front(), e = a.back(), C = 0;

while(s * A < e){

++C;

a.erase(a.begin());

a.pb(s * A);

sort(all(a));

s = a.front();

e = a.back();

if(C == B) break;

}

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

// 5. 例外.

if(B == C){

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

return 0;

}

// 6. 高速累乗.

// 6-1. 商の部分.

LL q = (B - C) / N;

rep(i, N){

a[i] *= mPow(A, q);

a[i] %= MOD;

}

// 6-2. 余り部分.

int r = (B - C) % N;

while(r){

s = a.front();

a.erase(a.begin());

a.pb(s * A % MOD);

--r;

}

// 7. 出力.

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

return 0;

}

[入力例]
3 10 3
1 99 10

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

[入力例]
2 100001 2
1 200000

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

[入力例]
10 123 1000000000
394632992 714094234 84420 5 3439891 3395 35 58 5001 730

[出力例]
954804718
385989482
948741792
268211139
100694402
492858064
955116743
68100851
154525400
479209143
※AtCoderのテストケースより

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

[出力例]
1
2
3
4
5

[入力例]
3 2 5
3 18 75

[出力例]
36
48
75

[入力例]
7 2 12
31 41 59 26 5 3 58

[出力例]
52
58
59
62
80
82
96

[入力例]
12 3 15
63 15 1 9 91 54 24 23 114 77 65 90

[出力例]
77
81
81
90
91
114
135
162
189
195
207
216

[入力例]
30 5 20220419
15 55 97 20 72 7 37 55 77 90 92 100 120 72 11 39 101 123 52 9 66 10 63 88 97 48 3 58 82 111

[出力例]
766349623
362346882
362346882
919945243
919945243
439144692
631139217
303934286
861532647
859904170
51898688
243893213
819876788
607868572
799863097
991857622
779849406
779849406
779849406
567841190
547827499
335819283
911802858
911802858
699794642
699794642
891789167
871775476
447759044
639753569

[入力例]
10 7 987654321
534272906 925848312 51921325 636258348 766724404 254864144 535929987 258927917 906007521 841903248

[出力例]
986918973
184630732
724343739
165436415
884949643
768125768
187543668
209626080
802753440
483131451

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

[入力例]

3 10 3

1 99 10

[出力例]

100

※AtCoderのテストケースより

[入力例]

2 100001 2

1 200000

[出力例]

200000

199931

※AtCoderのテストケースより

[入力例]

10 123 1000000000

394632992 714094234 84420 5 3439891 3395 35 58 5001 730

[出力例]

954804718

385989482

948741792

268211139

100694402

492858064

955116743

68100851

154525400

479209143

※AtCoderのテストケースより

[入力例]

5 1 3

1 2 3 4 5

[出力例]

[入力例]

3 2 5

3 18 75

[出力例]

[入力例]

7 2 12

31 41 59 26 5 3 58

[出力例]

[入力例]

12 3 15

63 15 1 9 91 54 24 23 114 77 65 90

[出力例]

114

135

162

189

195

207

216

[入力例]

30 5 20220419

15 55 97 20 72 7 37 55 77 90 92 100 120 72 11 39 101 123 52 9 66 10 63 88 97 48 3 58 82 111

[出力例]

766349623

362346882

919945243

439144692

631139217

303934286

861532647

859904170

51898688

243893213

819876788

607868572

799863097

991857622

779849406

567841190

547827499

335819283

911802858

699794642

891789167

871775476

447759044

639753569

[入力例]

10 7 987654321

534272906 925848312 51921325 636258348 766724404 254864144 535929987 258927917 906007521 841903248

[出力例]

986918973

184630732

724343739

165436415

884949643

768125768

187543668

209626080

802753440

483131451

■参照サイト
AtCoder Regular Contest 051

2022年4月18日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc247/editorial/3719
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL MOD = 998244353;
LL f[202020], g[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi p(N), q(N);
    rep(i, N) scanf("%d", &p[i]);
    rep(i, N) scanf("%d", &q[i]);
    
    // 2. 関数 f.
    f[1] = 2;
    f[2] = 3;
    repx(i, 3, 202020){
        f[i] = f[i - 1] + f[i - 2];
        f[i] %= MOD;
    }
    
    // 3. 関数 g.
    g[1] = 1;
    g[2] = 3;
    g[3] = 4;
    repx(i, 4, 202020){
        g[i] = f[i - 1] + f[i - 3];
        g[i] %= MOD;
    }
    
    // 4. グラフ作成.
    vvi G(N);
    rep(i, N){
        G[p[i] - 1].pb(q[i] - 1);
        G[q[i] - 1].pb(p[i] - 1);
    }
    
    // 5. 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);
        }
    };
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 6. 各連結成分のサイズ.
    int cs[idx + 1];
    rep(i, idx + 1) cs[i] = 0;
    rep(i, N) cs[c[i]]++;
    
    // 7. 集計.
    LL ans = 1;
    repx(i, 1, idx + 1){
        ans *= g[cs[i]];
        ans %= MOD;
    }
    
    // 8. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc247/editorial/3719

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using LL = long long;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

const LL MOD = 998244353;

LL f[202020], g[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi p(N), q(N);

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

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

// 2. 関数 f.

f[1] = 2;

f[2] = 3;

repx(i, 3, 202020){

f[i] = f[i - 1] + f[i - 2];

f[i] %= MOD;

}

// 3. 関数 g.

g[1] = 1;

g[2] = 3;

g[3] = 4;

repx(i, 4, 202020){

g[i] = f[i - 1] + f[i - 3];

g[i] %= MOD;

}

// 4. グラフ作成.

vvi G(N);

rep(i, N){

G[p[i] - 1].pb(q[i] - 1);

G[q[i] - 1].pb(p[i] - 1);

}

// 5. 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);

}

};

int c[N], idx = 0;

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

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

// 6. 各連結成分のサイズ.

int cs[idx + 1];

rep(i, idx + 1) cs[i] = 0;

rep(i, N) cs[c[i]]++;

// 7. 集計.

LL ans = 1;

repx(i, 1, idx + 1){

ans *= g[cs[i]];

ans %= MOD;

}

// 8. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
9

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

[出力例]
18

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

[出力例]
5742

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

[出力例]
2792548

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

[出力例]
695670925

[入力例]

1 2 3

2 1 3

[出力例]

※AtCoderテストケースより

[入力例]

2 3 5 4 1

4 2 1 3 5

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4 5 6 7 8

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4

4 3 2 1

[出力例]

[入力例]

3 1 4 7 5 2 6

2 6 3 4 5 1 7

[出力例]

[入力例]

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

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

[出力例]

5742

[入力例]

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

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

[出力例]

2792548

[入力例]

100

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

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

[出力例]

695670925

■参照サイト
AtCoder Beginner Contest 247

2022年4月17日2022年4月17日

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

C++の練習を兼ねて, AtCoder Beginner Contest 248 の問題C (Dice Sum) ～問題D (Range Count Query) を解いてみた.

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

■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--)
const LL MOD = 998244353;
LL dp[2525], pd[2525];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    
    // 2. dp更新.
    pd[0] = 1;
    rep(i, N){
        // 初期化.
        rep(k, 2525) dp[k] = 0;
        
        // 今回分更新.
        repx(j, 1, M + 1){
            rep(k, 2525 - j){
                dp[j + k] += pd[k];
                dp[j + k] %= MOD;
            }
        }
        
        // 前回分更新.
        rep(k, 2525) pd[k] = dp[k];
    }
    
    // 3. 集計.
    LL ans = 0;
    repx(k, 1, K + 1){
        ans += dp[k];
        ans %= MOD;
    }
    
    // 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--)

const LL MOD = 998244353;

LL dp[2525], pd[2525];

int main(){

// 1. 入力情報.

int N, M, K;

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

// 2. dp更新.

pd[0] = 1;

rep(i, N){

// 初期化.

rep(k, 2525) dp[k] = 0;

// 今回分更新.

repx(j, 1, M + 1){

rep(k, 2525 - j){

dp[j + k] += pd[k];

dp[j + k] %= MOD;

}

// 前回分更新.

rep(k, 2525) pd[k] = dp[k];

}

// 3. 集計.

LL ans = 0;

repx(k, 1, K + 1){

ans += dp[k];

ans %= MOD;

}

// 4. 出力.

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

return 0;

}

[入力例]
2 3 4

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

[入力例]
31 41 592

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

[入力例]
3 5 7

[出力例]
35

[入力例]
5 7 13

[出力例]
1257

[入力例]
10 3 17

[出力例]
9933

[入力例]
20 22 212

[出力例]
166114979

[入力例]

2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

31 41 592

[出力例]

798416518

※AtCoderテストケースより

[入力例]

3 5 7

[出力例]

[入力例]

5 7 13

[出力例]

1257

[入力例]

10 3 17

[出力例]

9933

[入力例]

20 22 212

[出力例]

166114979

■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
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi q(N + 1);
    rep(i, N){
        int a;
        scanf("%d", &a);
        
        // a に対応するインデックス.
        q[a].pb(i + 1);
    }
    
    // 2. クエリ回答.
    int Q;
    scanf("%d", &Q);
    rep(i, Q){
        // クエリ入力値.
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        ++r;
        
        // 値が, X に 等しいものに対するインデックスの範囲は？
        int s = lower_bound(all(q[x]), l) - q[x].begin();
        int g = lower_bound(all(q[x]), r) - q[x].begin();
        
        // 出力.
        printf("%d\n", g - s);
    }
    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

#define all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi q(N + 1);

rep(i, N){

int a;

scanf("%d", &a);

// a に対応するインデックス.

q[a].pb(i + 1);

}

// 2. クエリ回答.

int Q;

scanf("%d", &Q);

rep(i, Q){

// クエリ入力値.

int l, r, x;

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

++r;

// 値が, X に等しいものに対するインデックスの範囲は？

int s = lower_bound(all(q[x]), l) - q[x].begin();

int g = lower_bound(all(q[x]), r) - q[x].begin();

// 出力.

printf("%d\n", g - s);

}

return 0;

}

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

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

[入力例]
50
9 21 5 9 23 5 3 11 7 3 5 5 20 15 23 5 23 15 19 3 7 11 20 10 7 16 7 25 5 6 11 5 23 7 1 19 18 20 7 8 15 22 17 18 5 17 23 6 18 9
10
3 35 5
12 23 3
6 18 12
5 39 7
11 37 16
30 50 10
25 48 17
12 38 11
7 45 23
15 41 20

[出力例]
7
1
0
6
1
0
2
2
3
2

[入力例]

3 1 4 1 5

1 5 1

2 4 3

1 5 2

1 3 3

[出力例]

※AtCoderテストケースより

[入力例]

9 21 5 9 23 5 3 11 7 3 5 5 20 15 23 5 23 15 19 3 7 11 20 10 7 16 7 25 5 6 11 5 23 7 1 19 18 20 7 8 15 22 17 18 5 17 23 6 18 9

3 35 5

12 23 3

6 18 12

5 39 7

11 37 16

30 50 10

25 48 17

12 38 11

7 45 23

15 41 20

[出力例]

■参照サイト
ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248）

2022年4月16日

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

C++の練習を兼ねて, AtCoder Beginner Contest 247 の問題E (Max Min) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc247/editorial/3736
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    vvi bs;
    vi cur;
    rep(i, N){
        int a;
        scanf("%d", &a);
        if(a >= Y && a <= X){
            cur.pb(a);
        }else{
            bs.pb(cur);
            cur.clear();
        }
    }
    if(cur.size()) bs.pb(cur);
    
    // 2. カウント.
    LL ans = 0;
    for(auto &b : bs){
        // 要素が存在するか？
        int n = b.size();
        if(!n) continue;
        
        // 初期化.
        int r = 0;
        map<int, int> m;
        m[X] = m[Y] = 0;
        ++m[b[r]];
        
        // 尺取り法.
        rep(l, n){
            // 区間[l, r] が 条件を満たさない.
            while((r < n) && (!m[X] || !m[Y])) m[b[++r]]++;
            
            // 区間[l, r] が 見つかった.
            if(m[X] && m[Y]) ans += (LL)(n - r);
            
            // 次へ.
            --m[b[l]];
        }
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc247/editorial/3736

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using LL = long long;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

int main(){

// 1. 入力情報.

int N, X, Y;

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

vvi bs;

vi cur;

rep(i, N){

int a;

scanf("%d", &a);

if(a >= Y && a <= X){

cur.pb(a);

}else{

bs.pb(cur);

cur.clear();

}

if(cur.size()) bs.pb(cur);

// 2. カウント.

LL ans = 0;

for(auto &b : bs){

// 要素が存在するか？

int n = b.size();

if(!n) continue;

// 初期化.

int r = 0;

map<int, int> m;

m[X] = m[Y] = 0;

++m[b[r]];

// 尺取り法.

rep(l, n){

// 区間[l, r] が条件を満たさない.

while((r < n) && (!m[X] || !m[Y])) m[b[++r]]++;

// 区間[l, r] が見つかった.

if(m[X] && m[Y]) ans += (LL)(n - r);

// 次へ.

--m[b[l]];

}

// 3. 出力.

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

return 0;

}

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

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

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

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

[入力例]
5 1 1
1 1 1 1 1

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

[入力例]
10 8 1
2 7 1 8 2 8 1 8 2 8

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

[入力例]
2 3 1
1 3

[出力例]
1

[入力例]
2 2 1
1 3

[出力例]
0

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

[出力例]
3

[入力例]
25 12 5
1 17 13 12 11 8 9 5 10 12 20 13 4 9 14 3 9 23 10 4 5 10 5 7 12

[出力例]
10

[入力例]
100 321 123
199 123 191 123 246 222 300 321 252 321 317 333 284 199 321 172 123 90 166 277 123 119 205 321 124 299 123 296 196 138 319 184 145 124 205 110 331 209 163 123 318 209 361 223 321 150 269 123 182 276 193 245 129 334 278 332 189 174 302 374 233 296 248 123 341 196 127 318 270 271 183 333 296 373 110 135 123 183 272 221 321 260 123 110 333 321 227 123 321 313 87 321 155 319 141 123 339 251 321 123

[出力例]
69

[入力例]
500 3030 2020
3793 1694 2053 3838 3167 3304 3176 2960 1733 1762 2973 3982 3455 2532 3646 2976 2503 3502 2057 2137 3073 2160 3370 2931 2134 2462 2286 1819 3078 3689 3519 1808 3148 2227 3340 3813 3449 1560 2794 2363 3304 3030 2297 2068 2940 1577 2784 2111 3545 3293 1970 3285 3841 2697 3030 2020 2810 3453 2521 2437 2020 3230 3239 2151 2545 3726 2107 3522 3290 1678 3746 2692 3444 1514 3489 1574 1970 3699 2989 1862 2354 3449 1660 3590 2615 3447 1799 1836 3839 2650 2020 2516 3030 3710 3024 3902 3590 3952 3305 2877 3553 3732 3434 2184 3030 3044 3731 1997 1681 2386 2207 2587 2745 3740 1991 3429 3996 3950 3643 3718 3030 1848 3074 3452 2132 1889 2410 2256 2449 2621 1936 1871 3614 2807 3338 3701 3014 2938 1994 3121 2228 3525 3744 3140 3618 1923 3502 3277 3743 1654 3399 2992 2020 1848 3015 2637 2988 2672 3427 3130 2715 2157 2136 3874 2848 2418 3023 2970 2494 2194 3974 2035 3613 3091 1602 1718 3289 1504 2298 2256 1870 2629 3709 2057 3844 3999 2092 3239 1940 3670 3090 2598 1503 3938 2614 3712 2811 2149 1538 2004 1691 1592 1754 2516 3996 3961 3441 3230 1500 2512 2112 2020 2931 3376 3525 1956 1605 2519 2082 3907 3355 1976 2213 3168 1768 2320 1805 1714 1853 2224 3209 3519 2580 2027 3508 3030 3613 2295 1911 3875 2674 2253 3961 2647 1812 2207 1600 3646 3528 1963 1618 3382 3258 3289 2020 3479 2038 2863 2247 3534 3096 1642 3718 2725 2463 1673 2022 2457 3482 2020 2598 2626 3030 3030 3003 2929 2020 2714 3061 2020 2021 2022 2699 3030 3030 1858 2525 3905 3617 3401 2462 3781 2020 2620 1806 2333 1932 3507 3803 1547 2076 1530 3759 3879 2394 3076 2793 3159 3588 1913 2194 1634 3583 2647 2226 2779 3250 3340 3822 2134 1723 1854 2697 3828 1764 2766 2240 2513 3410 2951 1563 3034 3797 3643 2905 3397 2461 3935 3265 2215 3132 1571 1808 3507 2257 1976 3719 2813 3239 3284 2062 1749 3904 3099 3406 3412 2961 2294 2640 3215 3245 3190 3012 3569 3874 2545 2762 2611 3030 1802 2499 2463 3278 1812 3749 1803 3430 3464 3525 2755 2616 3806 3059 2431 3776 2064 3146 3030 2603 2020 3030 2662 2444 2125 2975 2020 2901 3030 2733 2952 2863 2154 2020 3386 2536 2020 3410 3030 3030 2020 2623 2492 2020 2716 2020 2020 2384 3030 2020 3150 3729 3464 3664 3030 3035 1522 1688 2858 1962 1944 1762 1538 2828 3704 2757 2020 2676 1668 1997 3682 3761 3834 2763 3538 2473 3809 3177 2237 3759 2674 2927 1999 1860 3815 1616 2141 1779 3259 3394 3064 3030 2505 1652 3432 1553 3986 2934 3956 2020 2718 2884 2179 2134 2020 3030 3030 2020 2788 2428 3214 2638 2453 1641 2123 2362 2958 2933 1511 1509 3030 2959 2020 2203 3030 2922 2020 2025 2290 3000 2587

[出力例]
207

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

[出力例]
124745

[入力例]

4 3 1

1 2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

5 2 1

1 3 2 4 1

[出力例]

※AtCoderテストケースより

[入力例]

5 1 1

1 1 1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

10 8 1

2 7 1 8 2 8 1 8 2 8

[出力例]

※AtCoderテストケースより

[入力例]

2 3 1

1 3

[出力例]

[入力例]

2 2 1

1 3

[出力例]

[入力例]

10 7 3

6 3 11 3 7 2 7 7 4 3

[出力例]

[入力例]

25 12 5

1 17 13 12 11 8 9 5 10 12 20 13 4 9 14 3 9 23 10 4 5 10 5 7 12

[出力例]

[入力例]

100 321 123

199 123 191 123 246 222 300 321 252 321 317 333 284 199 321 172 123 90 166 277 123 119 205 321 124 299 123 296 196 138 319 184 145 124 205 110 331 209 163 123 318 209 361 223 321 150 269 123 182 276 193 245 129 334 278 332 189 174 302 374 233 296 248 123 341 196 127 318 270 271 183 333 296 373 110 135 123 183 272 221 321 260 123 110 333 321 227 123 321 313 87 321 155 319 141 123 339 251 321 123

[出力例]

[入力例]

500 3030 2020

3793 1694 2053 3838 3167 3304 3176 2960 1733 1762 2973 3982 3455 2532 3646 2976 2503 3502 2057 2137 3073 2160 3370 2931 2134 2462 2286 1819 3078 3689 3519 1808 3148 2227 3340 3813 3449 1560 2794 2363 3304 3030 2297 2068 2940 1577 2784 2111 3545 3293 1970 3285 3841 2697 3030 2020 2810 3453 2521 2437 2020 3230 3239 2151 2545 3726 2107 3522 3290 1678 3746 2692 3444 1514 3489 1574 1970 3699 2989 1862 2354 3449 1660 3590 2615 3447 1799 1836 3839 2650 2020 2516 3030 3710 3024 3902 3590 3952 3305 2877 3553 3732 3434 2184 3030 3044 3731 1997 1681 2386 2207 2587 2745 3740 1991 3429 3996 3950 3643 3718 3030 1848 3074 3452 2132 1889 2410 2256 2449 2621 1936 1871 3614 2807 3338 3701 3014 2938 1994 3121 2228 3525 3744 3140 3618 1923 3502 3277 3743 1654 3399 2992 2020 1848 3015 2637 2988 2672 3427 3130 2715 2157 2136 3874 2848 2418 3023 2970 2494 2194 3974 2035 3613 3091 1602 1718 3289 1504 2298 2256 1870 2629 3709 2057 3844 3999 2092 3239 1940 3670 3090 2598 1503 3938 2614 3712 2811 2149 1538 2004 1691 1592 1754 2516 3996 3961 3441 3230 1500 2512 2112 2020 2931 3376 3525 1956 1605 2519 2082 3907 3355 1976 2213 3168 1768 2320 1805 1714 1853 2224 3209 3519 2580 2027 3508 3030 3613 2295 1911 3875 2674 2253 3961 2647 1812 2207 1600 3646 3528 1963 1618 3382 3258 3289 2020 3479 2038 2863 2247 3534 3096 1642 3718 2725 2463 1673 2022 2457 3482 2020 2598 2626 3030 3030 3003 2929 2020 2714 3061 2020 2021 2022 2699 3030 3030 1858 2525 3905 3617 3401 2462 3781 2020 2620 1806 2333 1932 3507 3803 1547 2076 1530 3759 3879 2394 3076 2793 3159 3588 1913 2194 1634 3583 2647 2226 2779 3250 3340 3822 2134 1723 1854 2697 3828 1764 2766 2240 2513 3410 2951 1563 3034 3797 3643 2905 3397 2461 3935 3265 2215 3132 1571 1808 3507 2257 1976 3719 2813 3239 3284 2062 1749 3904 3099 3406 3412 2961 2294 2640 3215 3245 3190 3012 3569 3874 2545 2762 2611 3030 1802 2499 2463 3278 1812 3749 1803 3430 3464 3525 2755 2616 3806 3059 2431 3776 2064 3146 3030 2603 2020 3030 2662 2444 2125 2975 2020 2901 3030 2733 2952 2863 2154 2020 3386 2536 2020 3410 3030 3030 2020 2623 2492 2020 2716 2020 2020 2384 3030 2020 3150 3729 3464 3664 3030 3035 1522 1688 2858 1962 1944 1762 1538 2828 3704 2757 2020 2676 1668 1997 3682 3761 3834 2763 3538 2473 3809 3177 2237 3759 2674 2927 1999 1860 3815 1616 2141 1779 3259 3394 3064 3030 2505 1652 3432 1553 3986 2934 3956 2020 2718 2884 2179 2134 2020 3030 3030 2020 2788 2428 3214 2638 2453 1641 2123 2362 2958 2933 1511 1509 3030 2959 2020 2203 3030 2922 2020 2025 2290 3000 2587

[出力例]

207

[入力例]

1000 1000 1

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

[出力例]

124745

■参照サイト
AtCoder Beginner Contest 247

2022年4月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 247 の問題C (1 2 1 3 1 2 1) ～問題D (Cylinder) を解いてみた.

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

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

■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;
    scanf("%d", &N);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, vi& v, int d) -> vi {
        // 終了条件.
        if(d == N) return v;
        
        // 結合.
        vi res = v;
        res.pb(d + 1);
        for(auto &p : v) res.pb(p);
        
        // 再帰処理.
        return self(self, res, d + 1);
    };
    vi a = {};
    vi ans = dfs(dfs, a, 0);
    
    // 3. 出力.
    int l = ans.size();
    rep(i, l) printf("%d%s", ans[i], (i < l - 1) ? " " : "\n");
    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;

scanf("%d", &N);

// 2. dfs.

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

auto dfs = [&](auto&& self, vi& v, int d) -> vi {

// 終了条件.

if(d == N) return v;

// 結合.

vi res = v;

res.pb(d + 1);

for(auto &p : v) res.pb(p);

// 再帰処理.

return self(self, res, d + 1);

};

vi a = {};

vi ans = dfs(dfs, a, 0);

// 3. 出力.

int l = ans.size();

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

return 0;

}

[入力例]
2

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

[入力例]
1

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

[入力例]
4

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

[入力例]
5

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

[入力例]
8

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

[入力例]
10

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

[入力例]

[出力例]

1 2 1

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

※AtCoderテストケースより

[入力例]

[出力例]

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

[入力例]

[出力例]

[入力例]

[出力例]

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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
#define pof pop_front
#define pob pop_back
#define puf push_front
#define pub push_back

int main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. クエリ回答.
    deque<P> dq;
    rep(i, Q){
        int t;
        scanf("%d", &t);
        
        // クエリ 1.
        if(t == 1){
            int x, c;
            scanf("%d %d", &x, &c);
            dq.pub({x, c});
        }
        
        // クエリ 2.
        if(t == 2){
            int c;
            scanf("%d", &c);
            LL ans = 0;
            while(c > 0){
                // 先頭要素.
                P p = dq.front();
                dq.pof();
                
                // 取り出すボールの個数が, 先頭要素よりも少ない.
                if(c < p.b){
                    ans += (LL)p.a * (LL)c;
                    dq.puf({p.a, p.b - c});
                    break;
                }
                
                // 上記以外.
                ans += (LL)p.a * (LL)p.b;
                c -= p.b;
            }
            
            // 出力.
            printf("%lld\n", ans);
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

#define pof pop_front

#define pob pop_back

#define puf push_front

#define pub push_back

int main(){

// 1. 入力情報.

int Q;

scanf("%d", &Q);

// 2. クエリ回答.

deque<P> dq;

rep(i, Q){

int t;

scanf("%d", &t);

// クエリ 1.

if(t == 1){

int x, c;

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

dq.pub({x, c});

}

// クエリ 2.

if(t == 2){

int c;

scanf("%d", &c);

LL ans = 0;

while(c > 0){

// 先頭要素.

P p = dq.front();

dq.pof();

// 取り出すボールの個数が, 先頭要素よりも少ない.

if(c < p.b){

ans += (LL)p.a * (LL)c;

dq.puf({p.a, p.b - c});

break;

}

// 上記以外.

ans += (LL)p.a * (LL)p.b;

c -= p.b;

}

// 出力.

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

}

return 0;

}

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

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

[入力例]
2
1 1000000000 1000000000
2 1000000000

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

[入力例]
5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

[出力例]

※AtCoderテストケースより

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

[出力例]
2
7
20
34
14

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

[出力例]
9
9
4
57
45
64
5
19
76
165

[入力例]

1 2 3

2 2

1 3 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 1000000000 1000000000

2 1000000000

[出力例]

1000000000000000000

※AtCoderテストケースより

[入力例]

1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

1 1 7

2 2

1 2 5

2 6

1 3 10

2 8

1 4 5

2 10

1 5 7

2 3

[出力例]

[入力例]

1 3 3

2 3

1 1 1

1 4 4

2 3

1 1 1

2 1

1 5 5

1 9 9

2 10

1 2 2

1 6 6

2 5

1 5 5

1 3 3

2 12

1 5 5

2 1

1 8 8

2 5

1 9 9

2 11

1 7 7

1 9 9

2 20

[出力例]

165

■参照サイト
AtCoder Beginner Contest 247

2022年4月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 150 の問題F (Xor Shift) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. クヌース–モリス–プラット(Knuth–Morris–Pratt algorithm)法を学習できたので, 非常に良かったと思う.
3. 本問では, 周期を知る必要が出てきたため, KMP法を, 最大2回まで実施する形で対応した.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc150/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vi = vector<int>;
using vp = vector<P>;
#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
#define all(x) x.begin(), x.end()
#define pb push_back

// https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法
// -> 照合が一致する複数の箇所を抽出するように拡張した版.
template<typename T>
struct KMP{
    vi M;  // 部分マッチテーブル.
    T S;   // テキスト.
    T W;   // 単語.
    int E; // 実行回数.
    KMP(T s, T w, int e = 1): S(s), W(w), E(e) {}
    void makeTable(){
        int i = 2, j = 0, n = W.size();
        vi t(n + 1);
        t[0] = -1;
        t[1] = 0;
        while(i < n){
            // 第一のケース.
            if(W[i - 1] == W[j]){
                t[i] = j + 1;
                ++i;
                ++j;
                continue;
            }
            
            // 第二のケース.
            if(j){
                j = t[j];
                continue;
            }
            
            // 第三のケース.
            t[i] = 0;
            ++i;
        }
        
        // 生成結果.
        M = t;
    }
    vi search(){
        vi ret;    // マッチした位置を保存.
        int m = 0; // S 内 の 現在照合中の開始位置.
        int i = 0; // W 内 の 現在位置.
        while(m + i < S.size() && E){
            if(W[i] == S[m + i]){
                ++i;
                if(i == W.size()){
                    ret.pb(m); // マッチした位置を保存.
                    ++m;       // 次へ.
                    i = 0;     // 初期化.
                    --E;       // デクリメント.
                }
                continue;
            }
            m += (i - M[i]);
            if(i) i = M[i];
        }
        return ret;
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi a(N), b(N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. 数列 c, d 作成.
    vi c, d;
    rep(i, N * 2 - 1) c.pb(a[i % N] ^ a[(i + 1) % N]);
    rep(i, N * 1 - 0) d.pb(b[i % N] ^ b[(i + 1) % N]);
    
    // ex. 
    // 以下の場合, 11 77 111 123 150 が出力される.
    // KMP<string> kmp("aopqrssttuuabracadabrapqrabra cadabrapqrpqrsabraceadabraroutxowiystabrcadabraabracadabraabdracadabraxyzabcdefghabracadabraiabracadabra deded xyzdeded abracadabraopqtdhg abracadabrajjtxhg", "abracadabra", 5);
    // kmp.makeTable();
    // vi v = kmp.search();
    // for(auto &p : v) printf("%d ", p);
    // puts("");
    
    // 3. KMP法(k の 抽出).
    KMP<vi> kmp(c, d, 2);
    kmp.makeTable();
    vi ks = kmp.search();
    // for(auto &k : ks) printf("%d ", k);
    // puts("");
    
    // 4. 周期を考慮.
    if(ks.size() == 2){
        int f = ks[1] - ks[0];
        while(f + ks.back() < N) ks.pb(f + ks.back());
    }
    
    // 5. x の 抽出.
    vp ans;
    for(auto &k : ks) ans.pb({k, a[k] ^ b[0]});
    
    // 6. sort.
    sort(all(ans));
    
    // 7. 出力.
    for(auto &p : ans) printf("%d %d\n", p.a, p.b);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vi = vector<int>;

using vp = vector<P>;

#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

#define all(x) x.begin(), x.end()

#define pb push_back

// https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法

// -> 照合が一致する複数の箇所を抽出するように拡張した版.

template<typename T>

struct KMP{

vi M; // 部分マッチテーブル.

T S; // テキスト.

T W; // 単語.

int E; // 実行回数.

KMP(T s, T w, int e = 1): S(s), W(w), E(e) {}

void makeTable(){

int i = 2, j = 0, n = W.size();

vi t(n + 1);

t[0] = -1;

t[1] = 0;

while(i < n){

// 第一のケース.

if(W[i - 1] == W[j]){

t[i] = j + 1;

++i;

++j;

continue;

}

// 第二のケース.

if(j){

j = t[j];

continue;

}

// 第三のケース.

t[i] = 0;

++i;

}

// 生成結果.

M = t;

}

vi search(){

vi ret; // マッチした位置を保存.

int m = 0; // S 内の現在照合中の開始位置.

int i = 0; // W 内の現在位置.

while(m + i < S.size() && E){

if(W[i] == S[m + i]){

++i;

if(i == W.size()){

ret.pb(m); // マッチした位置を保存.

++m; // 次へ.

i = 0; // 初期化.

--E; // デクリメント.

}

continue;

}

m += (i - M[i]);

if(i) i = M[i];

}

return ret;

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi a(N), b(N);

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

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

// 2. 数列 c, d 作成.

vi c, d;

rep(i, N * 2 - 1) c.pb(a[i % N] ^ a[(i + 1) % N]);

rep(i, N * 1 - 0) d.pb(b[i % N] ^ b[(i + 1) % N]);

// ex.

// 以下の場合, 11 77 111 123 150 が出力される.

// KMP<string> kmp("aopqrssttuuabracadabrapqrabra cadabrapqrpqrsabraceadabraroutxowiystabrcadabraabracadabraabdracadabraxyzabcdefghabracadabraiabracadabra deded xyzdeded abracadabraopqtdhg abracadabrajjtxhg", "abracadabra", 5);

// kmp.makeTable();

// vi v = kmp.search();

// for(auto &p : v) printf("%d ", p);

// puts("");

// 3. KMP法(k の抽出).

KMP<vi> kmp(c, d, 2);

kmp.makeTable();

vi ks = kmp.search();

// for(auto &k : ks) printf("%d ", k);

// puts("");

// 4. 周期を考慮.

if(ks.size() == 2){

int f = ks[1] - ks[0];

while(f + ks.back() < N) ks.pb(f + ks.back());

}

// 5. x の抽出.

vp ans;

for(auto &k : ks) ans.pb({k, a[k] ^ b[0]});

// 6. sort.

sort(all(ans));

// 7. 出力.

for(auto &p : ans) printf("%d %d\n", p.a, p.b);

return 0;

}

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

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

[入力例]
5
0 0 0 0 0
2 2 2 2 2

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

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

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

[入力例]
2
1 2
0 0

[出力例]

※AtCoderテストケースより

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

[出力例]
0 2
1 2
2 2

[入力例]
4
1 0 1 0
0 1 0 1

[出力例]
0 1
1 0
2 1
3 0

[入力例]
15
1 0 2 1 0 2 1 0 2 1 0 2 1 0 2
0 2 1 0 2 1 0 2 1 0 2 1 0 2 1

[出力例]
1 0
4 0
7 0
10 0
13 0

[入力例]
18
0 1 2 8 5 7 0 1 2 8 5 7 0 1 2 8 5 7
6 5 15 2 0 7 6 5 15 2 0 7 6 5 15 2 0 7

[出力例]
1 7
7 7
13 7

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

[出力例]
1 1
5 1
9 1
13 1
17 1
21 1

[入力例]

0 2 1

1 2 3

[出力例]

1 3

※AtCoderテストケースより

[入力例]

0 0 0 0 0

2 2 2 2 2

[出力例]

0 2

1 2

2 2

3 2

4 2

※AtCoderテストケースより

[入力例]

0 1 3 7 6 4

1 5 4 6 2 3

[出力例]

2 2

5 5

※AtCoderテストケースより

[入力例]

1 2

0 0

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1

3 3 3

[出力例]

0 2

1 2

2 2

[入力例]

1 0 1 0

0 1 0 1

[出力例]

0 1

1 0

2 1

3 0

[入力例]

1 0 2 1 0 2 1 0 2 1 0 2 1 0 2

0 2 1 0 2 1 0 2 1 0 2 1 0 2 1

[出力例]

1 0

4 0

7 0

10 0

13 0

[入力例]

0 1 2 8 5 7 0 1 2 8 5 7 0 1 2 8 5 7

6 5 15 2 0 7 6 5 15 2 0 7 6 5 15 2 0 7

[出力例]

1 7

7 7

13 7

[入力例]

1 2 5 2 1 2 5 2 1 2 5 2 1 2 5 2 1 2 5 2 1 2 5 2

3 4 3 0 3 4 3 0 3 4 3 0 3 4 3 0 3 4 3 0 3 4 3 0

[出力例]

1 1

5 1

9 1

13 1

17 1

21 1

■参照サイト
AtCoder Beginner Contest 150

2022年4月11日

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

C++の練習を兼ねて, AtCoder Regular Contest 006 の問題B (あみだくじ) を解いてみた.

■感想.
1. 問題Bは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 入力情報に半角スペースがあったため, getchar関数を使って実装した.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

// 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 a[33][33]; // i行目で, j列目 と (j + 1)列目 を 入れ替えるか？

int main(){
    
    // 1. 入力情報.
    int N, L, ans = 0;
    scanf("%d %d", &N, &L);
    getchar();
    rep(i, L + 1){
        int j = 0;
        while(1){
            int c = getchar();
            if(c == '\n' || c == EOF) break;
            if(c == '-') a[i][(j + 1) / 2] = 1;
            if(c == 'o') ans = (j / 2) + 1;
            ++j;
        }
    }
    
    // 2. あみだくじを辿る.
    repr(i, L - 1, 0){
        // 左端.
        if(ans == 1){
            if(a[i][1]) ++ans;
            continue;
        }
        
        // 中央.
        if(ans > 1 && ans < N){
            int d = 0;
            if(a[i][ans - 1]) --d;
            if(a[i][ans + 0]) ++d;
            ans += d;
            continue;
        }
        
        // 右端.
        if(ans == N){
            if(a[i][N - 1]) --ans;
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 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 a[33][33]; // i行目で, j列目と (j + 1)列目を入れ替えるか？

int main(){

// 1. 入力情報.

int N, L, ans = 0;

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

getchar();

rep(i, L + 1){

int j = 0;

while(1){

int c = getchar();

if(c == '\n' || c == EOF) break;

if(c == '-') a[i][(j + 1) / 2] = 1;

if(c == 'o') ans = (j / 2) + 1;

++j;

}

// 2. あみだくじを辿る.

repr(i, L - 1, 0){

// 左端.

if(ans == 1){

if(a[i][1]) ++ans;

continue;

}

// 中央.

if(ans > 1 && ans < N){

int d = 0;

if(a[i][ans - 1]) --d;

if(a[i][ans + 0]) ++d;

ans += d;

continue;

}

// 右端.

if(ans == N){

if(a[i][N - 1]) --ans;

}

// 3. 出力.

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

return 0;

}

[入力例]
3 2
| |-|
|-| |
o    

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

[入力例]
10 2
| |-| |-| |-| |-| |
|-| |-| |-| |-| |-|
            o      

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

[入力例]
1 5
|
|
|
|
|
o

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

[入力例]
4 2
| | | |
| | | |
      o

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

[入力例]
9 8
| | | | | | | | |
|-| | |-| | |-| |
| | |-| | |-| | |
| |-| | | | | |-|
| | | |-| | | |-|
| | |-| |-| | | |
|-| | |-| | |-| |
| | | | | |-| | |
            o    

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

[入力例]
3 3
| |-|
|-| |
| |-|
    o

[出力例]
1

[入力例]
5 7
| |-| | |
|-| |-| |
| |-| |-|
| | |-| |
| |-| |-|
|-| |-| |
| |-| |-|
  o      

[出力例]
2

[入力例]
10 11
| |-| | | |-| | | |
| |-| | | | |-| | |
| | |-| | | |-| | |
| |-| |-| |-| |-| |
| |-| | |-| | |-| |
| | |-| |-| | | |-|
|-| |-| | | |-| | |
| | | |-| |-| |-| |
| | |-| |-| | |-| |
|-| |-| | |-| | |-|
| | | |-| | | | | |
        o          

[出力例]
3

100

[入力例]

3 2

| |-|

|-| |

[出力例]

※AtCoderテストケースより

[入力例]

10 2

| |-| |-| |-| |-| |

|-| |-| |-| |-| |-|

[出力例]

※AtCoderテストケースより

[入力例]

1 5

[出力例]

※AtCoderテストケースより

[入力例]

4 2

| | | |

[出力例]

※AtCoderテストケースより

[入力例]

9 8

| | | | | | | | |

|-| | |-| | |-| |

| | |-| | |-| | |

| |-| | | | | |-|

| | | |-| | | |-|

| | |-| |-| | | |

|-| | |-| | |-| |

| | | | | |-| | |

[出力例]

※AtCoderテストケースより

[入力例]

3 3

| |-|

|-| |

| |-|

[出力例]

[入力例]

5 7

| |-| | |

|-| |-| |

| |-| |-|

| | |-| |

| |-| |-|

|-| |-| |

| |-| |-|

[出力例]

[入力例]

10 11

| |-| | | |-| | | |

| |-| | | | |-| | |

| | |-| | | |-| | |

| |-| |-| |-| |-| |

| |-| | |-| | |-| |

| | |-| |-| | | |-|

|-| |-| | | |-| | |

| | | |-| |-| |-| |

| | |-| |-| | |-| |

|-| |-| | |-| | |-|

| | | |-| | | | | |

[出力例]

■参照サイト
AtCoder Regular Contest 006

C++の練習を兼ねて, AtCoder Beginner Contest 245 の 問題E (Wrapping Chocolate) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 245 の 問題C (Choose Elements) ～ 問題D (Polynomial division) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 242 の 問題C (1111gal password) ～ 問題D (ABC Transform) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 051 の 問題C (掛け算) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 248 の 問題C (Dice Sum) ～ 問題D (Range Count Query) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 247 の 問題E (Max Min) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 247 の 問題C (1 2 1 3 1 2 1) ～ 問題D (Cylinder) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 150 の 問題F (Xor Shift) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 006 の 問題B (あみだくじ) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 245 の問題E (Wrapping Chocolate) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 245 の問題C (Choose Elements) ～問題D (Polynomial division) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 242 の問題C (1111gal password) ～問題D (ABC Transform) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 051 の問題C (掛け算) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 248 の問題C (Dice Sum) ～問題D (Range Count Query) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 247 の問題E (Max Min) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 247 の問題C (1 2 1 3 1 2 1) ～問題D (Cylinder) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 150 の問題F (Xor Shift) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 006 の問題B (あみだくじ) を解いてみた.