個人用メモ帳

2023年11月23日

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

C++の練習を兼ねて, AtCoder Beginner Contest 328 の問題C (Consecutive) ～問題E (Modulo MST) を解いてみた.

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

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

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

// C++20(GCC 12.2)
#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 pCum[303030];

int main(){
    
    // 1. 入力情報.
    int N, Q;
    char c[303030];
    scanf("%d %d %s", &N, &Q, c);
    string S(c);
    S = '#' + S;
    
    // 2. 累積和.
    rep(i, N) pCum[i + 1] = pCum[i] + (S[i] == S[i + 1]);
    
    // 3. クエリ回答.
    rep(i, Q){
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", pCum[r] - pCum[l]);
    }
    return 0;
    
}

// C++20(GCC 12.2)

#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 pCum[303030];

int main(){

// 1. 入力情報.

int N, Q;

char c[303030];

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

string S(c);

S = '#' + S;

// 2. 累積和.

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

// 3. クエリ回答.

rep(i, Q){

int l, r;

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

printf("%d\n", pCum[r] - pCum[l]);

}

return 0;

}

[入力例]
11 4
mississippi
3 9
4 10
4 6
7 7

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

[入力例]
5 1
aaaaa
1 5

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

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

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

[入力例]

11 4

mississippi

3 9

4 10

4 6

7 7

[出力例]

※AtCoderテストケースより

[入力例]

5 1

aaaaa

1 5

[出力例]

※AtCoderテストケースより

[入力例]

15 7

xxxxyyyyyzzzzzz

1 3

3 3

2 5

4 8

7 11

12 13

1 15

[出力例]

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    char c[202020];
    scanf("%s", c);
    string S(c);
    int ss = S.size();
    
    // 2. "ABC" を 削除.
    stack<char> st;
    rep(i, ss){
        // 2文字未満 or 'C'以外.
        if(st.size() < 2 || S[i] != 'C'){
            st.push(S[i]);
            continue;
        }
        
        // "AB" が 出現済か？
        char c1 = st.top();
        st.pop();
        char c2 = st.top();
        st.pop();
        if(c2 == 'A' && c1 == 'B') continue;
        
        // 戻し & 追加.
        st.push(c2);
        st.push(c1);
        st.push(S[i]);
    }
    
    // 3. 最終的な S は？
    string ans;
    while(!st.empty()){
        ans.pb(st.top());
        st.pop();
    }
    reverse(all(ans));
    
    // 4. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

char c[202020];

scanf("%s", c);

string S(c);

int ss = S.size();

// 2. "ABC" を削除.

stack<char> st;

rep(i, ss){

// 2文字未満 or 'C'以外.

if(st.size() < 2 || S[i] != 'C'){

st.push(S[i]);

continue;

}

// "AB" が出現済か？

char c1 = st.top();

st.pop();

char c2 = st.top();

st.pop();

if(c2 == 'A' && c1 == 'B') continue;

// 戻し & 追加.

st.push(c2);

st.push(c1);

st.push(S[i]);

}

// 3. 最終的な S は？

string ans;

while(!st.empty()){

ans.pb(st.top());

st.pop();

}

reverse(all(ans));

// 4. 出力.

printf("%s\n", ans.c_str());

return 0;

}

[入力例]
BAABCBCCABCAC

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

[入力例]
ABCABC

[出力例]

※AtCoderテストケースより

[入力例]
AAABCABCABCAABCABCBBBAABCBCCCAAABCBCBCC

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

[入力例]
BBBAABACABCACCBCBCBAACBCCACAABCCCBABCABBAACACCBABC

[出力例]
BBBAABACACCBCBCBAACBCCACACCBABBAACACCB

[入力例]
ABCACABBABCBBABACAABCCCBAABACBABABCACBAABACABCACAAABCCBBCBAACCACCBACCAABCCABCCCABCCCCBBABBCAACABCABC

[出力例]
ACABBBBABACACCBAABACBABACBAABACACAACBBCBAACCACCBACCACCCCCCBBABBCAAC

[入力例]

BAABCBCCABCAC

[出力例]

BCAC

※AtCoderテストケースより

[入力例]

ABCABC

[出力例]

※AtCoderテストケースより

[入力例]

AAABCABCABCAABCABCBBBAABCBCCCAAABCBCBCC

[出力例]

AAABBBCCC

※AtCoderテストケースより

[入力例]

BBBAABACABCACCBCBCBAACBCCACAABCCCBABCABBAACACCBABC

[出力例]

BBBAABACACCBCBCBAACBCCACACCBABBAACACCB

[入力例]

ABCACABBABCBBABACAABCCCBAABACBABABCACBAABACABCACAAABCCBBCBAACCACCBACCAABCCABCCCABCCCCBBABBCAACABCABC

[出力例]

ACABBBBABACACCBAABACBABACBAABACACAACBBCBAACCACCBACCACCCCCCBBABBCAAC

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

// C++20(GCC 12.2)
#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 int INF = 2020202020;
int u[33], v[33];
LL w[33];

int main(){
    
    // 1. 入力情報.
    int N, M;
    LL K;
    scanf("%d %d %lld", &N, &M, &K);
    rep(i, M){
        scanf("%d %d %lld", &u[i], &v[i], &w[i]);
        --u[i];
        --v[i];
    }
    
    // 2. 全域木 T の 辺候補は？
    vi es;
    rep(i, 1 << M) if(__builtin_popcount(i) == N - 1) es.pb(i);
    // for(auto &e : es) printf("%d\n", e);
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索開始地点 s をキューに追加.
        q.push(s);
        
        // 探索開始地点 s は, 距離ゼロ.
        d[s] = 0;
        
        // キューを処理.
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &v : G[u]) if(d[v] == INF && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    
    // 4. 全域木のコストの最小値は？
    LL ans = 202020202020202020;
    for(auto &e : es){
        // グラフ構築 & コスト集計.
        vvi G(N);
        LL cost = 0;
        rep(i, M){
            if((1 << i) & e){
                G[u[i]].pb(v[i]);
                G[v[i]].pb(u[i]);
                cost += w[i];
                cost %= K;
            }
        }
        
        // グラフは, 木か？
        int d[N];
        rep(i, N) d[i] = INF;
        bfs(G, 0, d);
        bool ok = true;
        rep(i, N) if(d[i] == INF) ok = false;
        if(!ok) continue;
        
        // 最小値更新.
        // printf("%d %lld\n", e, cost);
        ans = min(ans, cost);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

#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 int INF = 2020202020;

int u[33], v[33];

LL w[33];

int main(){

// 1. 入力情報.

int N, M;

LL K;

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

rep(i, M){

scanf("%d %d %lld", &u[i], &v[i], &w[i]);

--u[i];

--v[i];

}

// 2. 全域木 T の辺候補は？

vi es;

rep(i, 1 << M) if(__builtin_popcount(i) == N - 1) es.pb(i);

// for(auto &e : es) printf("%d\n", e);

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

// 探索開始地点 s は, 距離ゼロ.

d[s] = 0;

// キューを処理.

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &v : G[u]) if(d[v] == INF && v != s) d[v] = d[u] + 1, q.push(v);

}

};

// 4. 全域木のコストの最小値は？

LL ans = 202020202020202020;

for(auto &e : es){

// グラフ構築 & コスト集計.

vvi G(N);

LL cost = 0;

rep(i, M){

if((1 << i) & e){

G[u[i]].pb(v[i]);

G[v[i]].pb(u[i]);

cost += w[i];

cost %= K;

}

// グラフは, 木か？

int d[N];

rep(i, N) d[i] = INF;

bfs(G, 0, d);

bool ok = true;

rep(i, N) if(d[i] == INF) ok = false;

if(!ok) continue;

// 最小値更新.

// printf("%d %lld\n", e, cost);

ans = min(ans, cost);

}

// 5. 出力.

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

return 0;

}

[入力例]
5 6 328
1 2 99
1 3 102
2 3 86
2 4 94
2 5 95
3 4 81

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

[入力例]
6 5 998244353
1 2 337361568
1 6 450343304
2 3 61477244
2 5 745383438
4 5 727360840

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

[入力例]
8 28 936294041850197
1 2 473294720906780
1 3 743030800139244
1 4 709363019414774
1 5 383643612490312
1 6 557102781022861
1 7 623179288538138
1 8 739618599410809
2 3 857687812294404
2 4 893923168139714
2 5 581822471860662
2 6 740549363586558
2 7 307226438833222
2 8 447399029952998
3 4 636318083622768
3 5 44548707643622
3 6 307262781240755
3 7 12070267388230
3 8 700247263184082
4 5 560567890325333
4 6 704726113717147
4 7 588263818615687
4 8 549007536393172
5 6 779230871080408
5 7 825982583786498
5 8 713928998174272
6 7 751331074538826
6 8 449873635430228
7 8 11298381761479

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

[入力例]
4 6 100
1 2 543
1 3 123
1 4 321
2 3 555
2 4 111
3 4 222

[出力例]
0
※実際, 辺 2, 4, 6 を 選択した場合, (123 + 555 + 222) % 100 = 0 となる

[入力例]
5 7 1234
1 2 86587
2 3 77532
3 4 84661
4 5 52062
1 5 63206
1 4 72092
3 5 82403

[出力例]
21
※実際, 辺 2, 4, 5, 7 を 選択した場合, (77532 + 52062 + 63206 + 82403) % 1234 = 21 となる

[入力例]
6 10 20231123
1 2 84117461
1 6 55841423
2 3 72564375
2 4 21686910
2 5 22158045
2 6 42781720
3 4 14540220
3 5 89483069
3 6 90561012
5 6 98083075

[出力例]
20000
※実際, 辺 1, 3, 6, 7, 8 を 選択した場合, (84117461 + 72564375 + 42781720 + 14540220 + 89483069) % 20231123 = 20000 となる

100

101

102

103

[入力例]

5 6 328

1 2 99

1 3 102

2 3 86

2 4 94

2 5 95

3 4 81

[出力例]

※AtCoderテストケースより

[入力例]

6 5 998244353

1 2 337361568

1 6 450343304

2 3 61477244

2 5 745383438

4 5 727360840

[出力例]

325437688

※AtCoderテストケースより

[入力例]

8 28 936294041850197

1 2 473294720906780

1 3 743030800139244

1 4 709363019414774

1 5 383643612490312

1 6 557102781022861

1 7 623179288538138

1 8 739618599410809

2 3 857687812294404

2 4 893923168139714

2 5 581822471860662

2 6 740549363586558

2 7 307226438833222

2 8 447399029952998

3 4 636318083622768

3 5 44548707643622

3 6 307262781240755

3 7 12070267388230

3 8 700247263184082

4 5 560567890325333

4 6 704726113717147

4 7 588263818615687

4 8 549007536393172

5 6 779230871080408

5 7 825982583786498

5 8 713928998174272

6 7 751331074538826

6 8 449873635430228

7 8 11298381761479

[出力例]

11360716373

※AtCoderテストケースより

[入力例]

4 6 100

1 2 543

1 3 123

1 4 321

2 3 555

2 4 111

3 4 222

[出力例]

※実際, 辺 2, 4, 6 を選択した場合, (123 + 555 + 222) % 100 = 0 となる

[入力例]

5 7 1234

1 2 86587

2 3 77532

3 4 84661

4 5 52062

1 5 63206

1 4 72092

3 5 82403

[出力例]

※実際, 辺 2, 4, 5, 7 を選択した場合, (77532 + 52062 + 63206 + 82403) % 1234 = 21 となる

[入力例]

6 10 20231123

1 2 84117461

1 6 55841423

2 3 72564375

2 4 21686910

2 5 22158045

2 6 42781720

3 4 14540220

3 5 89483069

3 6 90561012

5 6 98083075

[出力例]

20000

※実際, 辺 1, 3, 6, 7, 8 を選択した場合, (84117461 + 72564375 + 42781720 + 14540220 + 89483069) % 20231123 = 20000 となる

■参照サイト
トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)

2023年11月19日

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

C++の練習を兼ねて, AtCoder Grand Contest 048 の問題C (Penguin Skating) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 解説のロジックで, 解けることが興味深く思った.
3. 区間を抽出する処理で, 尺取り法の復習ができたので非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, L;
    scanf("%d %d", &N, &L);
    vi a(N), b(N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. 空きマスの個数(以下, 解説通り).
    vi x(N + 1), y(N + 1);
    x[0] = a[0] - 1;
    y[0] = b[0] - 1;
    repx(i, 1, N){
        x[i] = a[i] - a[i - 1] - 1;
        y[i] = b[i] - b[i - 1] - 1;
    }
    x[N] = L - a[N - 1];
    y[N] = L - b[N - 1];
    
    // 3. 区間[l, r].
    bool ok = true;
    vi l(N + 1, 0), r(N + 1, 0);
    int xl = 0;
    rep(i, N + 1){
        // y[i] が ゼロ.
        if(!y[i]) continue;
        
        // x[j] が ゼロとなるものを, 区間[l, r] から除外.
        repx(j, xl, N + 1){
            if(!x[j]) ++xl;
            else      break;
        }
        
        // y[i] が 正.
        int xr = 0, cur = 0;
        repx(j, xl, N + 1){
            // 加算.
            cur += x[j];
            
            // y[i] を 構成する x[l], ..., x[r] が 見つからなかった.
            if(cur > y[i]){
                ok = false;
                break;
            }
            
            // y[i] を 構成する x[l], ..., x[r] が 見つかった.
            if(cur == y[i]){
                xr = j;
                l[i] = xl;
                r[i] = xr;
                break;
            }
        }
        
        // 条件を満たさない場合.
        if(!ok) break;
        
        // 次へ.
        xl = xr + 1;
    }
    // rep(i, N + 1) printf("%d %d\n", l[i], r[i]);
    
    // 4. 達成不可能な場合.
    if(!ok){
        puts("-1");
        return 0;
    }
    
    // 5. 最小回数.
    LL ans = 0;
    rep(i, N + 1) if(y[i]) ans += max(i - l[i], 0) + max(r[i] - i, 0);
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/agc048/editorial/220

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

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

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

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

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

int main(){

// 1. 入力情報.

int N, L;

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

vi a(N), b(N);

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

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

// 2. 空きマスの個数(以下, 解説通り).

vi x(N + 1), y(N + 1);

x[0] = a[0] - 1;

y[0] = b[0] - 1;

repx(i, 1, N){

x[i] = a[i] - a[i - 1] - 1;

y[i] = b[i] - b[i - 1] - 1;

}

x[N] = L - a[N - 1];

y[N] = L - b[N - 1];

// 3. 区間[l, r].

bool ok = true;

vi l(N + 1, 0), r(N + 1, 0);

int xl = 0;

rep(i, N + 1){

// y[i] がゼロ.

if(!y[i]) continue;

// x[j] がゼロとなるものを, 区間[l, r] から除外.

repx(j, xl, N + 1){

if(!x[j]) ++xl;

else break;

}

// y[i] が正.

int xr = 0, cur = 0;

repx(j, xl, N + 1){

// 加算.

cur += x[j];

// y[i] を構成する x[l], ..., x[r] が見つからなかった.

if(cur > y[i]){

ok = false;

break;

}

// y[i] を構成する x[l], ..., x[r] が見つかった.

if(cur == y[i]){

xr = j;

l[i] = xl;

r[i] = xr;

break;

}

// 条件を満たさない場合.

if(!ok) break;

// 次へ.

xl = xr + 1;

}

// rep(i, N + 1) printf("%d %d\n", l[i], r[i]);

// 4. 達成不可能な場合.

if(!ok){

puts("-1");

return 0;

}

// 5. 最小回数.

LL ans = 0;

rep(i, N + 1) if(y[i]) ans += max(i - l[i], 0) + max(r[i] - i, 0);

// 6. 出力.

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

return 0;

}

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

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

[入力例]
1 3
1
2

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

[入力例]
10 1000000000
65110170 68805223 123016442 275946481 661490312 760727752 764540566 929355340 930658577 947099792
1 2 123016442 661490311 929355337 930658574 999999997 999999998 999999999 1000000000

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

[入力例]
6 25
4 7 12 15 18 23
1 5 8 13 16 25

[出力例]
6

[入力例]
10 60
5 12 18 19 27 28 35 39 47 55
1 2 7 19 20 21 22 30 54 60

[出力例]
11

[入力例]
20 80
1 2 3 4 5 8 10 17 22 23 30 32 33 40 48 52 55 60 69 75
1 4 5 6 14 15 16 21 28 29 37 38 39 50 51 54 72 73 79 80

[出力例]
21

[入力例]

4 11

3 4 6 10

1 5 6 11

[出力例]

※AtCoderのテストケースより

[入力例]

1 3

[出力例]

-1

※AtCoderのテストケースより

[入力例]

10 1000000000

65110170 68805223 123016442 275946481 661490312 760727752 764540566 929355340 930658577 947099792

1 2 123016442 661490311 929355337 930658574 999999997 999999998 999999999 1000000000

[出力例]

※AtCoderのテストケースより

[入力例]

6 25

4 7 12 15 18 23

1 5 8 13 16 25

[出力例]

[入力例]

10 60

5 12 18 19 27 28 35 39 47 55

1 2 7 19 20 21 22 30 54 60

[出力例]

[入力例]

20 80

1 2 3 4 5 8 10 17 22 23 30 32 33 40 48 52 55 60 69 75

1 4 5 6 14 15 16 21 28 29 37 38 39 50 51 54 72 73 79 80

[出力例]

■参照サイト
AtCoder Grand Contest 048

2023年11月16日

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

C++の練習を兼ねて, AtCoder Grand Contest 048 の問題A (atcoder < S) ～問題B (Bracket Score) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/agc048/editorial/197
// C++20(GCC 12.2)
#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 T;
    scanf("%d", &T);
    
    // 2. 各テストケース.
    rep(i, T){
        // 2-1. テストケース入力情報.
        char c[1010];
        scanf("%s", c);
        string S(c);
        int ss = S.size();
        
        // 2-2. S > atcoder.
        if(S > "atcoder"){
            puts("0");
            continue;
        }
        
        // 2-3. S で a 以外の文字が出現する位置は？
        int k = -1;
        rep(j, ss){
            if(S[j] != 'a'){
                k = j;
                break;
            }
        }
        
        // 2-4. 出力.
        printf("%d\n", k == -1 ? -1 : (S[k] <= 't' ? k : k - 1));
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/agc048/editorial/197

// C++20(GCC 12.2)

#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 T;

scanf("%d", &T);

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

rep(i, T){

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

char c[1010];

scanf("%s", c);

string S(c);

int ss = S.size();

// 2-2. S > atcoder.

if(S > "atcoder"){

puts("0");

continue;

}

// 2-3. S で a 以外の文字が出現する位置は？

int k = -1;

rep(j, ss){

if(S[j] != 'a'){

k = j;

break;

}

// 2-4. 出力.

printf("%d\n", k == -1 ? -1 : (S[k] <= 't' ? k : k - 1));

}

return 0;

}

[入力例]
3
atcodeer
codeforces
aaa

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

[入力例]
7
atcoder
btcoder
aaaaaaaaaa
aaaaaaaaaatcoder
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaucoder
aaaaaaaaaaucoder
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcoder

[出力例]
1
0
-1
10
99
9
100

[入力例]

atcodeer

codeforces

aaa

[出力例]

-1

※AtCoderのテストケースより

[入力例]

atcoder

btcoder

aaaaaaaaaa

aaaaaaaaaatcoder

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaucoder

aaaaaaaaaaucoder

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcoder

[出力例]

-1

100

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

// 解き直し.
// https://atcoder.jp/contests/agc048/editorial/198
// C++20(GCC 12.2)
#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 all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vl a(N), b(N);
    LL ans = 0;
    rep(i, N){
        scanf("%lld", &a[i]);
        ans += a[i];
    }
    rep(i, N) scanf("%lld", &b[i]);
    
    // 2. 整数列 B と 整数列 A の 差分(偶奇ごと).
    vl e(N / 2), o(N / 2);
    rep(i, N){
        if(i & 1) e[i / 2] = b[i] - a[i];
        else      o[i / 2] = b[i] - a[i];
    }
    
    // 3. sort.
    sort(all(e));
    sort(all(o));
    
    // 4. 最大値は？
    repr(c, N / 2 - 1, 0) ans = max(ans, ans + e[c] + o[c]);
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/agc048/editorial/198

// C++20(GCC 12.2)

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vl a(N), b(N);

LL ans = 0;

rep(i, N){

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

ans += a[i];

}

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

// 2. 整数列 B と整数列 A の差分(偶奇ごと).

vl e(N / 2), o(N / 2);

rep(i, N){

if(i & 1) e[i / 2] = b[i] - a[i];

else o[i / 2] = b[i] - a[i];

}

// 3. sort.

sort(all(e));

sort(all(o));

// 4. 最大値は？

repr(c, N / 2 - 1, 0) ans = max(ans, ans + e[c] + o[c]);

// 5. 出力.

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

return 0;

}

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

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

[入力例]
10
866111664 844917655 383133839 353498483 472381277 550309930 378371075 304570952 955719384 705445072
178537096 218662351 231371336 865935868 579910117 62731178 681212831 16537461 267238505 318106937

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

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

[出力例]
27

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

[出力例]
6666

[入力例]
300
1497 22535 51088 3833 46272 71399 21920 87631 18249 79764 22730 27792 70430 28366 50163 37724 18899 77601 16280 37406 82587 86790 48446 42083 63894 89207 89929 91109 32662 13409 80912 182 84805 77801 48836 17741 38512 8957 13578 96975 6720 38861 8687 83167 25803 13350 96905 22353 63001 82134 22955 81939 72242 75209 77403 50087 36155 82338 88775 57695 11783 17474 93991 24095 27836 64201 29920 978 41288 61844 13560 2107 83191 20755 25860 48209 79844 60622 70552 18126 87999 51854 32401 11282 67347 49714 76528 78991 38408 44771 78343 23167 99287 87237 48614 44543 12456 90952 32278 49918 16226 39892 73749 4043 45042 34810 73407 81909 88203 37231 93088 21120 41384 33504 46928 80731 92006 95356 66301 69287 94232 14719 93296 58848 51747 26187 2703 27173 43859 95848 72924 38186 7618 59671 79939 43541 41957 2825 30503 11315 6593 19971 93084 70871 65742 14873 34186 28109 94303 66760 23103 45500 95659 44466 18666 13733 44994 61956 5101 60992 17441 93228 33187 38733 98167 44203 70465 5327 83196 19584 94290 20092 27294 9317 47294 7660 61986 94143 57030 88977 56883 89753 15271 22536 85189 60593 16751 65367 27308 72640 20835 59805 35770 31466 58327 49999 25409 13945 77161 38901 21685 52686 22022 76159 1907 45834 56096 77784 12799 70166 84251 55526 38672 61646 51199 56936 53467 52265 39407 21984 87526 45830 40500 94725 79863 68811 96498 93540 60294 3381 3526 22798 92469 52558 99319 19599 96775 63750 83638 65323 50812 73008 9088 76559 69546 38331 89729 56868 86790 20163 80614 50181 77045 38597 75670 1861 40306 81731 69691 74791 48746 35917 39704 94389 80738 9335 8999 62402 20729 94495 88028 30810 25999 69987 70812 92949 39007 38799 5410 10004 57552 92378 76879 25312 35642 34076 56275 12385 5081 85033 55578 38736 37477 16161 42282 22911 60217 36192 84412 21168
89938 16998 73346 1658 94391 4704 31437 52022 78015 35675 90458 33892 92719 96691 65953 93810 80272 72529 89841 59057 97377 10888 19156 66809 33864 41198 66043 17403 87769 31944 78400 40696 16404 71111 48098 33300 78497 72401 51850 49834 47819 19689 73076 3595 67233 83491 79391 66106 68818 87472 18038 42207 62854 17992 80418 96032 81216 4042 96328 10505 57693 64220 66603 35605 99890 45971 96304 66770 43330 57562 51365 27376 8801 73637 12603 47494 70323 42134 70836 38414 43478 21149 19508 42754 63462 41928 38181 65637 49612 2482 47044 24539 74669 3883 39297 50329 22264 60083 10568 76183 53813 4775 43106 86767 84534 66585 49433 15432 24423 94604 11711 96738 81052 76192 37852 15232 11739 54775 61183 20897 24793 81922 30924 10663 66114 69916 54941 34876 18087 56346 24302 12482 14000 14680 18733 46896 20354 56340 50769 59123 2185 14786 37093 75098 96924 23029 9791 59628 85775 97437 76148 6093 92409 3136 86306 69557 84479 76226 15185 55762 6713 60033 80357 58674 47978 18793 98953 70945 69982 72396 17614 29067 44681 70979 61751 77956 77387 13206 956 77616 92025 17274 13966 88111 36654 31137 82652 44155 80674 36708 30829 67261 59420 28086 48158 74347 3463 14397 47097 77868 27406 61253 51071 12087 12222 74579 18937 67936 22861 63047 91023 71467 30971 98326 77160 65894 53202 25786 9222 94230 47471 23617 61639 70566 34945 11152 46616 38939 98592 40648 56798 29817 62872 70494 20569 48614 32514 76506 30963 20988 79207 86520 48286 18693 64757 33116 89125 98746 835 52439 44107 64870 16823 41030 65701 20604 41566 60004 73761 8702 26206 19110 84040 29538 37581 90008 65167 92372 44108 23895 58407 42769 85594 49813 73994 65328 57698 57605 64182 8456 16448 65809 91226 75823 23282 97387 51887 86015 70138 62478 92918 31674 3299 75507 43803 71928 97467 20218 64364 77766

[出力例]
20231116

[入力例]

4 2 3 1

2 3 2 4

[出力例]

※AtCoderのテストケースより

[入力例]

866111664 844917655 383133839 353498483 472381277 550309930 378371075 304570952 955719384 705445072

178537096 218662351 231371336 865935868 579910117 62731178 681212831 16537461 267238505 318106937

[出力例]

6629738472

※AtCoderのテストケースより

[入力例]

1 1 3 5 3 2

3 6 1 1 7 3

[出力例]

[入力例]

100

11 31 62 26 14 30 91 76 49 45 17 35 66 13 40 92 79 97 1 86 30 29 93 73 88 60 82 46 53 93 39 47 10 3 49 3 91 66 7 78 83 43 68 57 15 67 43 23 1 33 38 44 20 3 72 81 70 20 63 91 84 2 44 96 38 86 92 51 29 25 43 43 84 37 11 98 42 47 58 21 65 50 99 99 47 8 39 2 11 77 16 49 62 76 47 1 72 50 77 10

10 22 34 92 45 47 29 83 55 30 33 99 73 5 46 6 11 82 75 59 67 77 84 82 83 6 22 78 5 78 16 2 55 74 73 63 95 48 91 53 86 94 31 41 43 16 27 56 45 95 69 1 43 90 59 27 80 98 55 42 11 71 63 84 54 8 61 15 9 47 36 11 60 51 67 17 13 65 63 16 55 67 65 54 94 23 51 65 14 71 71 50 19 63 73 83 69 15 86 55

[出力例]

6666

[入力例]

300

1497 22535 51088 3833 46272 71399 21920 87631 18249 79764 22730 27792 70430 28366 50163 37724 18899 77601 16280 37406 82587 86790 48446 42083 63894 89207 89929 91109 32662 13409 80912 182 84805 77801 48836 17741 38512 8957 13578 96975 6720 38861 8687 83167 25803 13350 96905 22353 63001 82134 22955 81939 72242 75209 77403 50087 36155 82338 88775 57695 11783 17474 93991 24095 27836 64201 29920 978 41288 61844 13560 2107 83191 20755 25860 48209 79844 60622 70552 18126 87999 51854 32401 11282 67347 49714 76528 78991 38408 44771 78343 23167 99287 87237 48614 44543 12456 90952 32278 49918 16226 39892 73749 4043 45042 34810 73407 81909 88203 37231 93088 21120 41384 33504 46928 80731 92006 95356 66301 69287 94232 14719 93296 58848 51747 26187 2703 27173 43859 95848 72924 38186 7618 59671 79939 43541 41957 2825 30503 11315 6593 19971 93084 70871 65742 14873 34186 28109 94303 66760 23103 45500 95659 44466 18666 13733 44994 61956 5101 60992 17441 93228 33187 38733 98167 44203 70465 5327 83196 19584 94290 20092 27294 9317 47294 7660 61986 94143 57030 88977 56883 89753 15271 22536 85189 60593 16751 65367 27308 72640 20835 59805 35770 31466 58327 49999 25409 13945 77161 38901 21685 52686 22022 76159 1907 45834 56096 77784 12799 70166 84251 55526 38672 61646 51199 56936 53467 52265 39407 21984 87526 45830 40500 94725 79863 68811 96498 93540 60294 3381 3526 22798 92469 52558 99319 19599 96775 63750 83638 65323 50812 73008 9088 76559 69546 38331 89729 56868 86790 20163 80614 50181 77045 38597 75670 1861 40306 81731 69691 74791 48746 35917 39704 94389 80738 9335 8999 62402 20729 94495 88028 30810 25999 69987 70812 92949 39007 38799 5410 10004 57552 92378 76879 25312 35642 34076 56275 12385 5081 85033 55578 38736 37477 16161 42282 22911 60217 36192 84412 21168

89938 16998 73346 1658 94391 4704 31437 52022 78015 35675 90458 33892 92719 96691 65953 93810 80272 72529 89841 59057 97377 10888 19156 66809 33864 41198 66043 17403 87769 31944 78400 40696 16404 71111 48098 33300 78497 72401 51850 49834 47819 19689 73076 3595 67233 83491 79391 66106 68818 87472 18038 42207 62854 17992 80418 96032 81216 4042 96328 10505 57693 64220 66603 35605 99890 45971 96304 66770 43330 57562 51365 27376 8801 73637 12603 47494 70323 42134 70836 38414 43478 21149 19508 42754 63462 41928 38181 65637 49612 2482 47044 24539 74669 3883 39297 50329 22264 60083 10568 76183 53813 4775 43106 86767 84534 66585 49433 15432 24423 94604 11711 96738 81052 76192 37852 15232 11739 54775 61183 20897 24793 81922 30924 10663 66114 69916 54941 34876 18087 56346 24302 12482 14000 14680 18733 46896 20354 56340 50769 59123 2185 14786 37093 75098 96924 23029 9791 59628 85775 97437 76148 6093 92409 3136 86306 69557 84479 76226 15185 55762 6713 60033 80357 58674 47978 18793 98953 70945 69982 72396 17614 29067 44681 70979 61751 77956 77387 13206 956 77616 92025 17274 13966 88111 36654 31137 82652 44155 80674 36708 30829 67261 59420 28086 48158 74347 3463 14397 47097 77868 27406 61253 51071 12087 12222 74579 18937 67936 22861 63047 91023 71467 30971 98326 77160 65894 53202 25786 9222 94230 47471 23617 61639 70566 34945 11152 46616 38939 98592 40648 56798 29817 62872 70494 20569 48614 32514 76506 30963 20988 79207 86520 48286 18693 64757 33116 89125 98746 835 52439 44107 64870 16823 41030 65701 20604 41566 60004 73761 8702 26206 19110 84040 29538 37581 90008 65167 92372 44108 23895 58407 42769 85594 49813 73994 65328 57698 57605 64182 8456 16448 65809 91226 75823 23282 97387 51887 86015 70138 62478 92918 31674 3299 75507 43803 71928 97467 20218 64364 77766

[出力例]

20231116

■参照サイト
AtCoder Grand Contest 048

2023年11月12日

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

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

■感想.
1. 問題E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題E で, 完全二分木を復習が出来たので, 良かったとおもう.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++20(GCC 12.2)
#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 T;
    scanf("%d", &T);
    
    // 2. 2 の 冪乗.
    vl cPow;
    cPow.pb(1LL);
    rep(i, 60) cPow.pb(cPow.back() << 1LL);
    
    // 3. 各テストケース.
    rep(i, T){
        // 3-1. テストケース入力情報.
        LL N, X, K;
        scanf("%lld %lld %lld", &N, &X, &K);
        
        // 3-2. K が 大きい(2 の 60乗 = 1152921504606846976 > 1e18).
        if(K > (60 - 1) * 2){
            puts("0");
            continue;
        }
        
        // 3-3. 頂点 X から, 距離 k の 頂点数は？
        LL ans = 0;
        int k = (int)K;
        LL cur = X, bef = -1;
        while(cur){
            // 前回以前に, 頂点 1 に 到達済.
            if(k == -1){
                ++ans;
                break;
            }
            
            // 前回以前に, 子頂点(左 or 右)をベースに, 確認済みか？
            int f = 0;
            if(bef == cur * 2)     f = 1;
            if(bef == cur * 2 + 1) f = 2;
            
            // 区間[l, r].
            int d = 0;
            LL l = 0, r = 0;
            if(f == 0) l = cur;
            if(f == 1) l = cur * 2 + 1;
            if(f == 2) l = cur * 2;
            while(d < k && (l * 2) <= N){
                ++d;
                l *= 2;
            }
            
            // 加算.
            if(d == k){
                r = min(N, l + cPow[d] - 1);
                ans += r - l + 1;
            }
            
            // 親頂点へ移動.
            bef = cur;
            cur >>= 1;
            --k;
            
            // 親頂点へ移動したことが無い場合.
            if(f == 0) --k;
        }
        
        // 3-4. 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// C++20(GCC 12.2)

#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 T;

scanf("%d", &T);

// 2. 2 の冪乗.

vl cPow;

cPow.pb(1LL);

rep(i, 60) cPow.pb(cPow.back() << 1LL);

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

rep(i, T){

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

LL N, X, K;

scanf("%lld %lld %lld", &N, &X, &K);

// 3-2. K が大きい(2 の 60乗 = 1152921504606846976 > 1e18).

if(K > (60 - 1) * 2){

puts("0");

continue;

}

// 3-3. 頂点 X から, 距離 k の頂点数は？

LL ans = 0;

int k = (int)K;

LL cur = X, bef = -1;

while(cur){

// 前回以前に, 頂点 1 に到達済.

if(k == -1){

++ans;

break;

}

// 前回以前に, 子頂点(左 or 右)をベースに, 確認済みか？

int f = 0;

if(bef == cur * 2) f = 1;

if(bef == cur * 2 + 1) f = 2;

// 区間[l, r].

int d = 0;

LL l = 0, r = 0;

if(f == 0) l = cur;

if(f == 1) l = cur * 2 + 1;

if(f == 2) l = cur * 2;

while(d < k && (l * 2) <= N){

++d;

l *= 2;

}

// 加算.

if(d == k){

r = min(N, l + cPow[d] - 1);

ans += r - l + 1;

}

// 親頂点へ移動.

bef = cur;

cur >>= 1;

--k;

// 親頂点へ移動したことが無い場合.

if(f == 0) --k;

}

// 3-4. 出力.

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

}

return 0;

}

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

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

[入力例]
10
822981260158260522 52 20
760713016476190629 2314654 57
1312150450968417 1132551176249851 7
1000000000000000000 1083770654 79
234122432773361868 170290518806790 23
536187734191890310 61862 14
594688604155374934 53288633578 39
1000000000000000000 120160810 78
89013034180999835 14853481725739 94
463213054346948152 825589 73

[出力例]
1556480
140703128616960
8
17732923532771328
65536
24576
2147483640
33776997205278720
7881299347898368
27021597764222976
※AtCoderテストケースより

[入力例]
25
7 5 1
7 5 2
7 5 3
7 5 4
7 5 5
25 20 2
25 20 5
123 100 5
123 100 6
123 100 7
123 100 8
3300 25 6
3300 25 7
3300 25 8
20231112 12345 5
20231112 12345 8
20231112 12345 10
20231112 12345 12
20231112 12345 13
20231112 12345 15
202309232100 5555555 10
202309232100 5555555 13
202309232100 5555555 15
202309232100 5555555 18
202309232100 5555555 20

[出力例]
1
2
1
2
0
2
3
4
8
7
14
94
161
120
48
384
1536
2048
2048
4094
1536
12288
49152
65536
131072

[入力例]

10 2 0

10 2 1

10 2 2

10 2 3

10 2 4

[出力例]

※AtCoderテストケースより

[入力例]

822981260158260522 52 20

760713016476190629 2314654 57

1312150450968417 1132551176249851 7

1000000000000000000 1083770654 79

234122432773361868 170290518806790 23

536187734191890310 61862 14

594688604155374934 53288633578 39

1000000000000000000 120160810 78

89013034180999835 14853481725739 94

463213054346948152 825589 73

[出力例]

1556480

140703128616960

17732923532771328

65536

24576

2147483640

33776997205278720

7881299347898368

27021597764222976

※AtCoderテストケースより

[入力例]

7 5 1

7 5 2

7 5 3

7 5 4

7 5 5

25 20 2

25 20 5

123 100 5

123 100 6

123 100 7

123 100 8

3300 25 6

3300 25 7

3300 25 8

20231112 12345 5

20231112 12345 8

20231112 12345 10

20231112 12345 12

20231112 12345 13

20231112 12345 15

202309232100 5555555 10

202309232100 5555555 13

202309232100 5555555 15

202309232100 5555555 18

202309232100 5555555 20

[出力例]

161

120

384

1536

2048

4094

1536

12288

49152

65536

131072

■参照サイト
サントリープログラミングコンテスト2023（AtCoder Beginner Contest 321）

2023年11月11日

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

C++の練習を兼ねて, AtCoder Regular Contest 166 の問題C (LU / RD Marking) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 問題C で, Fibonacci数列の復習が出来たので, 良かったとおもう.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc166/editorial/7184
// C++20(GCC 12.2)
#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 f[2020202], g[2020202];

// 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 T;
    scanf("%d", &T);
    
    // 2. 事前準備.
    f[0] = f[1] = 1;
    repx(i, 2, 2020202) f[i] = (f[i - 1] + f[i - 2]) % MOD;
    g[0] = 1;
    repx(i, 1, 1010101 - 1) g[i] = (g[i - 1] * f[i * 2]) % MOD;
    
    // 3. テストケース.
    // ex. H = 3, W = 8
    // 上辺(左から右): 2, 4, 6, 7, 7, 7, 7, 7
    // 右辺(上から下): 6, 4, 2
    // -> 解説の数式に照らすと, n = 3, m = 5 が分かる.
    rep(i, T){
        // 3-1. 各テストケース.
        int H, W;
        scanf("%d %d", &H, &W);
        
        // 3-2. m, n.
        int m = abs(H - W), n = min(H, W);
        
        // 3-3. 計算.
        LL ans = g[n] * g[n] % MOD * mPow(f[2 * n + 1], (LL)m) % MOD;
        
        // 3-4. 出力.
        printf("%lld\n", ans);
    }
    return 0;
}

// 解き直し.

// https://atcoder.jp/contests/arc166/editorial/7184

// C++20(GCC 12.2)

#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 f[2020202], g[2020202];

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

scanf("%d", &T);

// 2. 事前準備.

f[0] = f[1] = 1;

repx(i, 2, 2020202) f[i] = (f[i - 1] + f[i - 2]) % MOD;

g[0] = 1;

repx(i, 1, 1010101 - 1) g[i] = (g[i - 1] * f[i * 2]) % MOD;

// 3. テストケース.

// ex. H = 3, W = 8

// 上辺(左から右): 2, 4, 6, 7, 7, 7, 7, 7

// 右辺(上から下): 6, 4, 2

// -> 解説の数式に照らすと, n = 3, m = 5 が分かる.

rep(i, T){

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

int H, W;

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

// 3-2. m, n.

int m = abs(H - W), n = min(H, W);

// 3-3. 計算.

LL ans = g[n] * g[n] % MOD * mPow(f[2 * n + 1], (LL)m) % MOD;

// 3-4. 出力.

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

}

return 0;

}

[入力例]
2
1 1
2 3

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

[入力例]
3
123 456
654 321
1000000 1000000

[出力例]
60549740
298307903
656009181
※AtCoderのテストケースより

[入力例]
10
1 2
2 1
3 4
5 3
3 6
3 7
3 8
5 10
15 25
2023 1111

[出力例]
12
12
354900
7452900
156510900
291995841
142446543
546223419
631651090
451184128

[入力例]

1 1

2 3

[出力例]

800

※AtCoderのテストケースより

[入力例]

123 456

654 321

1000000 1000000

[出力例]

60549740

298307903

656009181

※AtCoderのテストケースより

[入力例]

1 2

2 1

3 4

5 3

3 6

3 7

3 8

5 10

15 25

2023 1111

[出力例]

354900

7452900

156510900

291995841

142446543

546223419

631651090

451184128

■参照サイト
AtCoder Regular Contest 166

2023年11月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 324 の問題E (Joint Two Strings) を解いてみた.

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

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

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
#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;
    char t[505050];
    scanf("%d %s", &N, t);
    int ts = strlen(t);
    vs v;
    rep(i, N){
        string s;
        cin >> s;
        v.pb(s);
    }
    
    // 2. 文字列 T と, 何文字一致するか？
    vi lCount, rCount;
    for(auto &s : v){
        // 文字列 S の 各文字の出現位置は？
        vvi idxs(26);
        rep(i, s.size()) idxs[s[i] - 'a'].pb(i);
        
        // 左から数える場合.
        int idx = -1, c = 0;
        rep(i, ts){
            int cur = t[i] - 'a';
            if(!idxs[cur].size()) break;
            int at = upper_bound(all(idxs[cur]), idx) - idxs[cur].begin();
            if(at == idxs[cur].size()) break;
            if(idx >= idxs[cur][at]) break;
            idx = idxs[cur][at];
            ++c;
        }
        lCount.pb(c);
        
        // 右から数える場合.
        idx = s.size(), c = 0;
        repr(i, ts - 1, 0){
            int cur = t[i] - 'a';
            if(!idxs[cur].size()) break;
            int at = lower_bound(all(idxs[cur]), idx) - idxs[cur].begin();
            if(!at && idx <= idxs[cur][at]) break;
            idx = idxs[cur][max(0, at - 1)];
            ++c;
        }
        rCount.pb(c);
    }
    
    // 3. sort.
    sort(all(lCount));
    sort(all(rCount));
    
    // 4. 集計.
    LL ans = 0;
    for(auto &l : lCount){
        int at = lower_bound(all(rCount), ts - l) - rCount.begin();
        ans += (LL)(rCount.size() - at);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

using vs = vector<string>;

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

char t[505050];

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

int ts = strlen(t);

vs v;

rep(i, N){

string s;

cin >> s;

v.pb(s);

}

// 2. 文字列 T と, 何文字一致するか？

vi lCount, rCount;

for(auto &s : v){

// 文字列 S の各文字の出現位置は？

vvi idxs(26);

rep(i, s.size()) idxs[s[i] - 'a'].pb(i);

// 左から数える場合.

int idx = -1, c = 0;

rep(i, ts){

int cur = t[i] - 'a';

if(!idxs[cur].size()) break;

int at = upper_bound(all(idxs[cur]), idx) - idxs[cur].begin();

if(at == idxs[cur].size()) break;

if(idx >= idxs[cur][at]) break;

idx = idxs[cur][at];

++c;

}

lCount.pb(c);

// 右から数える場合.

idx = s.size(), c = 0;

repr(i, ts - 1, 0){

int cur = t[i] - 'a';

if(!idxs[cur].size()) break;

int at = lower_bound(all(idxs[cur]), idx) - idxs[cur].begin();

if(!at && idx <= idxs[cur][at]) break;

idx = idxs[cur][max(0, at - 1)];

++c;

}

rCount.pb(c);

}

// 3. sort.

sort(all(lCount));

sort(all(rCount));

// 4. 集計.

LL ans = 0;

for(auto &l : lCount){

int at = lower_bound(all(rCount), ts - l) - rCount.begin();

ans += (LL)(rCount.size() - at);

}

// 5. 出力.

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

return 0;

}

[入力例]
3 bac
abba
bcb
aaca

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

[入力例]
5 xx
x
x
x
x
x

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

[入力例]
10 ms
mkgn
m
hlms
vmsle
mxsm
nnzdhi
umsavxlb
ffnsybomr
yvmm
naouel

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

[入力例]
3 a
a
a
a

[出力例]
9

[入力例]
5 pqr
smcmwubocdxvlifbvncjmvrpyq
mhjzknucbwjyprclfyhlgrmhgp
vhmdqgdikfooemfqlgkeocqntw
uglthudqauvtlnvztvtopvukbr
xmdthyfzaeubkdmjapnplgnyyf

[出力例]
6

[入力例]
10 atcoder
swlazbtdveckiojddjvezrrsjzimjjog
noajutwvbcmuzoswnctqobguletpsq
xcfgesaszjcpetuyxufehuiffg
tkrvoawtwcyizodxbdwxeecrrdiadeezrckw
forgemtxmwnblzyhzpsjrcynhx
dkaawtxfkciqkogptdjzblukvgpqjn
pttmiajkmezpmmvyrdujkeqerynzm
dplzhanztxxcfoozvadexeiprlzrlklyui
qskedvmgavbtfdvcmecwerwjwgqoch
ditpzonoidultevbrzsddrueqarysfcbt

[出力例]
61

[入力例]
30 abracadabra
frlhabracacdavbacadyjotqfiajpfrsfalqmpqzm
pnsabraaasbboigplsbkqaytpztlty
dabrarenuxjbnmwejvumayzqmjacadyueir
vrafdksqwxwphvbabracxadyaubraxsnhiyimkgj
vopsvoomcfekesrqblqxjacaderhok
hephqdabrahgabrailbwcnykgnueerasxlz
dfdoqdncuaybkxabracxmzgjnmtkioc
apbiybracaudabirglrzehsfuhrhuoczuduwb
ruxxacadfdcacadizqzeefryriesteziip
xzqjtdewrnyabraquyjhabracaidabirayberuirmjf
hafudwmabracadabrampgdabraurlmyacdayrmezgrnkd
ccamcpjhmcinhabracadabrauubcytmtoyksr
rtgpyiaqqcthxabracadadbrdaduhazyiintogf
nciseywsrseoyiodabraskzmabraqsmknfc
qabracaydaubrasgnjpsyonenfehongsupwralz
xdsbjgybfbmiabraicaodabrayeetrlzqyikhxv
wopsvxldeemevmebagfmdabratnnabraodq
ccdsyjhxfmvltkgvdxdacadfzijmtk
pjrxhwalfpetfydzcabracieagtvswdabrah
egvbabacadaebrcrzxhqsxpxglqucndgzllk
wlpdpbvlhrleulaoahghgjlacadddz
qebhqkeksdiviwwabracadabrarvhwxlizrjx
vzifenabrabznwcwkcdblrwxbbzdabrajks
lpepabjpuxabrarhupexbcwivbapol
dwomabracaudaobrargvgrkfpodelkgzntgszzr
qwvbgaivdyummkaraptmdabrablkecktwm
ytguxctdeoclbpacadzybhumyzlxjo
ykxggshcsuxutqbupmqzpscrgdabrag
gixkvjvuimdfgmttdhabatinoxmbp
pzslmvoulsgxnxocjgmifdabraqfxym

[出力例]
606

100

101

102

103

104

105

106

107

108

109

110

[入力例]

3 bac

abba

bcb

aaca

[出力例]

※AtCoderテストケースより

[入力例]

5 xx

[出力例]

※AtCoderテストケースより

[入力例]

10 ms

mkgn

hlms

vmsle

mxsm

nnzdhi

umsavxlb

ffnsybomr

yvmm

naouel

[出力例]

※AtCoderテストケースより

[入力例]

3 a

[出力例]

[入力例]

5 pqr

smcmwubocdxvlifbvncjmvrpyq

mhjzknucbwjyprclfyhlgrmhgp

vhmdqgdikfooemfqlgkeocqntw

uglthudqauvtlnvztvtopvukbr

xmdthyfzaeubkdmjapnplgnyyf

[出力例]

[入力例]

10 atcoder

swlazbtdveckiojddjvezrrsjzimjjog

noajutwvbcmuzoswnctqobguletpsq

xcfgesaszjcpetuyxufehuiffg

tkrvoawtwcyizodxbdwxeecrrdiadeezrckw

forgemtxmwnblzyhzpsjrcynhx

dkaawtxfkciqkogptdjzblukvgpqjn

pttmiajkmezpmmvyrdujkeqerynzm

dplzhanztxxcfoozvadexeiprlzrlklyui

qskedvmgavbtfdvcmecwerwjwgqoch

ditpzonoidultevbrzsddrueqarysfcbt

[出力例]

[入力例]

30 abracadabra

frlhabracacdavbacadyjotqfiajpfrsfalqmpqzm

pnsabraaasbboigplsbkqaytpztlty

dabrarenuxjbnmwejvumayzqmjacadyueir

vrafdksqwxwphvbabracxadyaubraxsnhiyimkgj

vopsvoomcfekesrqblqxjacaderhok

hephqdabrahgabrailbwcnykgnueerasxlz

dfdoqdncuaybkxabracxmzgjnmtkioc

apbiybracaudabirglrzehsfuhrhuoczuduwb

ruxxacadfdcacadizqzeefryriesteziip

xzqjtdewrnyabraquyjhabracaidabirayberuirmjf

hafudwmabracadabrampgdabraurlmyacdayrmezgrnkd

ccamcpjhmcinhabracadabrauubcytmtoyksr

rtgpyiaqqcthxabracadadbrdaduhazyiintogf

nciseywsrseoyiodabraskzmabraqsmknfc

qabracaydaubrasgnjpsyonenfehongsupwralz

xdsbjgybfbmiabraicaodabrayeetrlzqyikhxv

wopsvxldeemevmebagfmdabratnnabraodq

ccdsyjhxfmvltkgvdxdacadfzijmtk

pjrxhwalfpetfydzcabracieagtvswdabrah

egvbabacadaebrcrzxhqsxpxglqucndgzllk

wlpdpbvlhrleulaoahghgjlacadddz

qebhqkeksdiviwwabracadabrarvhwxlizrjx

vzifenabrabznwcwkcdblrwxbbzdabrajks

lpepabjpuxabrarhupexbcwivbapol

dwomabracaudaobrargvgrkfpodelkgzntgszzr

qwvbgaivdyummkaraptmdabrablkecktwm

ytguxctdeoclbpacadzybhumyzlxjo

ykxggshcsuxutqbupmqzpscrgdabrag

gixkvjvuimdfgmttdhabatinoxmbp

pzslmvoulsgxnxocjgmifdabraqfxym

[出力例]

606

■参照サイト
日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324）

2023年10月29日2023年10月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 324 の問題C (Error Correction) ～問題D (Square Permutation) を解いてみた.

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

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

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vs = vector<string>;
#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 c[505050];
    scanf("%d %s", &N, c);
    string u(c);
    vs v;
    rep(i, N){
        string s;
        cin >> s;
        v.pb(s);
    }
    
    // 2. 集計.
    int us = u.size();
    vi ans;
    rep(i, N){
        // 2-1. T, T' の文字数が同じ.
        string t = v[i];
        int ts = t.size();
        if(ts == us){
            int diff = 0;
            rep(j, ts) if(t[j] != u[j]) ++diff;
            if(diff <= 1) ans.pb(i + 1);
            continue;
        }
        
        // 2-2. T が T' より 1文字多い.
        if(ts == us + 1){
            int idx = ts - 1;
            rep(j, us){
                if(t[j] != u[j]){
                    idx = j;
                    break;
                }
            }
            bool ok = true;
            repx(j, idx + 1, ts) if(t[j] != u[j - 1]) ok = false;
            if(ok) ans.pb(i + 1);
            continue;
        }
        
        // 2-3. T' が T より 1文字多い.
        if(us == ts + 1){
            int idx = us - 1;
            rep(j, ts){
                if(t[j] != u[j]){
                    idx = j;
                    break;
                }
            }
            bool ok = true;
            repx(j, idx + 1, us) if(u[j] != t[j - 1]) ok = false;
            if(ok) ans.pb(i + 1);
            continue;
        }
    }
    
    // 3. 出力.
    int n = ans.size();
    printf("%d\n", n);
    rep(i, n) printf("%d%s", ans[i], (i < n - 1) ? " " : "\n");
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vs = vector<string>;

#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 c[505050];

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

string u(c);

vs v;

rep(i, N){

string s;

cin >> s;

v.pb(s);

}

// 2. 集計.

int us = u.size();

vi ans;

rep(i, N){

// 2-1. T, T' の文字数が同じ.

string t = v[i];

int ts = t.size();

if(ts == us){

int diff = 0;

rep(j, ts) if(t[j] != u[j]) ++diff;

if(diff <= 1) ans.pb(i + 1);

continue;

}

// 2-2. T が T' より 1文字多い.

if(ts == us + 1){

int idx = ts - 1;

rep(j, us){

if(t[j] != u[j]){

idx = j;

break;

}

bool ok = true;

repx(j, idx + 1, ts) if(t[j] != u[j - 1]) ok = false;

if(ok) ans.pb(i + 1);

continue;

}

// 2-3. T' が T より 1文字多い.

if(us == ts + 1){

int idx = us - 1;

rep(j, ts){

if(t[j] != u[j]){

idx = j;

break;

}

bool ok = true;

repx(j, idx + 1, us) if(u[j] != t[j - 1]) ok = false;

if(ok) ans.pb(i + 1);

continue;

}

// 3. 出力.

int n = ans.size();

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

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

return 0;

}

[入力例]
5 ababc
ababc
babc
abacbc
abdbc
abbac

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

[入力例]
1 aoki
takahashi

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

[入力例]
9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

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

[入力例]
17 iroha
iroha
hiroha
ijroha
irsoha
iropha
irohia
irohab
roha
ioha
irha
iroa
iroh
zroha
izoha
irzha
iroza
irohz

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

[入力例]
25 beginner
eehccbkoonm
beginner
aiehciglanf
oahkoknoej
beganner
hbjgfdnfj
beginnerr
kcfkicnfgik
begnner
aljndjalikk
beginnner
mjojjddmoff
ihajahecfkdk
eginner
ccccmohebjjmk
kefohsdsdaghado
mjbclodfyguekdf
beginer
lgagnbecondbi
mgibkkakneeeffo
fhhoojmkjijctm
begannner
fggfjbnjbdddfju
cceefhmgiddhlqobi
biginner

[出力例]
8
2 5 7 9 11 14 18 25

[入力例]

5 ababc

ababc

babc

abacbc

abdbc

abbac

[出力例]

1 2 3 4

※AtCoderテストケースより

[入力例]

1 aoki

takahashi

[出力例]

※AtCoderテストケースより

[入力例]

9 atcoder

atoder

atcode

athqcoder

atcoder

tacoder

jttcoder

atoder

atceoder

atcoer

[出力例]

1 2 4 7 8 9

※AtCoderテストケースより

[入力例]

17 iroha

iroha

hiroha

ijroha

irsoha

iropha

irohia

irohab

roha

ioha

irha

iroa

iroh

zroha

izoha

irzha

iroza

irohz

[出力例]

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

[入力例]

25 beginner

eehccbkoonm

beginner

aiehciglanf

oahkoknoej

beganner

hbjgfdnfj

beginnerr

kcfkicnfgik

begnner

aljndjalikk

beginnner

mjojjddmoff

ihajahecfkdk

eginner

ccccmohebjjmk

kefohsdsdaghado

mjbclodfyguekdf

beginer

lgagnbecondbi

mgibkkakneeeffo

fhhoojmkjijctm

begannner

fggfjbnjbdddfju

cceefhmgiddhlqobi

biginner

[出力例]

2 5 7 9 11 14 18 25

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

int main(){
    
    // 1. 入力情報.
    int N;
    char s[22];
    scanf("%d %s", &N, s);
    
    // 2. 各数字の出現数は？
    vi cs(10, 0);
    rep(i, N) ++cs[s[i] - '0'];
    
    // 3. 全探索.
    int ans = 0;
    rep(i, 10000001){
        string t = to_string((LL)i * (LL)i);
        if(t.size() > N) break;
        while(t.size() < N) t = '0' + t;
        vi ct(10, 0);
        rep(j, N) ++ct[t[j] - '0'];
        if(cs == ct) ++ans;
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

char s[22];

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

// 2. 各数字の出現数は？

vi cs(10, 0);

rep(i, N) ++cs[s[i] - '0'];

// 3. 全探索.

int ans = 0;

rep(i, 10000001){

string t = to_string((LL)i * (LL)i);

if(t.size() > N) break;

while(t.size() < N) t = '0' + t;

vi ct(10, 0);

rep(j, N) ++ct[t[j] - '0'];

if(cs == ct) ++ans;

}

// 4. 出力.

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

return 0;

}

[入力例]
4
4320

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

[入力例]
3
010

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

[入力例]
13
8694027811503

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

[入力例]
5
57006

[出力例]
3

[入力例]
5
05920

[出力例]
3

[入力例]
8
112035

[出力例]
0

[入力例]
11
00123456789

[出力例]
260

[入力例]
14
00112234566789

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

[入力例]

4320

[出力例]

※AtCoderテストケースより

[入力例]

010

[出力例]

※AtCoderテストケースより

[入力例]

8694027811503

[出力例]

840

※AtCoderテストケースより

[入力例]

57006

[出力例]

[入力例]

05920

[出力例]

[入力例]

112035

[出力例]

[入力例]

00123456789

[出力例]

260

[入力例]

00112234566789

[出力例]

2077

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

■参照サイト
日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324）

2023年10月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 166 の問題A (Replace C or Swap AB) ～問題B (Make Multiples) を解いてみた.

■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, 解説のロジックで, 計算可能であることが, 非常に不思議な印象を受けた.
3. 問題Bで, 苦手な動的計画法の訓練が積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc166/editorial/7182
// C++20(GCC 12.2)
#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
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        int N;
        scanf("%d ", &N);
        char x[N + 1], y[N + 1];
        scanf("%s %s", x, y);
        string X(x), Y(y);
        
        // 2-2. 'C' の 位置をチェック.
        bool ok = true;
        vi yc;
        rep(j, N){
            if(Y[j] == 'C'){
                yc.pb(j);
                if(X[j] != 'C') ok = false;
            }
        }
        yc.pb(N);
        
        // 2-3. 例外.
        if(!ok){
            puts("No");
            continue;
        }
        
        // 2-4. 各区切りごとに判定.
        int s = 0;
        for(auto &e : yc){
            vi xa, xc, ya;
            repx(j, s, e){
                // 'A', 'C' の インデックスを集める.
                if(X[j] == 'A') xa.pb(j);
                if(X[j] == 'C') xc.pb(j);
                if(Y[j] == 'A') ya.pb(j);
            }
            
            // 次へ.
            s = e + 1;
            
            // 文字列 X に含まれる 'A' が 多い.
            if(xa.size() > ya.size()){
                ok = false;
                continue;
            }
            
            // 文字列 X に含まれる 'A' が 少ない.
            if(xa.size() + xc.size() < ya.size()){
                ok = false;
                continue;
            }
            
            // 文字列 X に 含まれる 'A' を 調整.
            int cur = -1;
            while(xa.size() < ya.size()) xa.pb(xc[++cur]);
            
            // sort.
            sort(all(xa));
            
            // 比較.
            rep(j, xa.size()) if(xa[j] > ya[j]) ok = false;
        }
        
        // 2-5. 出力.
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc166/editorial/7182

// C++20(GCC 12.2)

#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

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

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

// 2-1. 各テストケース.

int N;

scanf("%d ", &N);

char x[N + 1], y[N + 1];

scanf("%s %s", x, y);

string X(x), Y(y);

// 2-2. 'C' の位置をチェック.

bool ok = true;

vi yc;

rep(j, N){

if(Y[j] == 'C'){

yc.pb(j);

if(X[j] != 'C') ok = false;

}

yc.pb(N);

// 2-3. 例外.

if(!ok){

puts("No");

continue;

}

// 2-4. 各区切りごとに判定.

int s = 0;

for(auto &e : yc){

vi xa, xc, ya;

repx(j, s, e){

// 'A', 'C' のインデックスを集める.

if(X[j] == 'A') xa.pb(j);

if(X[j] == 'C') xc.pb(j);

if(Y[j] == 'A') ya.pb(j);

}

// 次へ.

s = e + 1;

// 文字列 X に含まれる 'A' が多い.

if(xa.size() > ya.size()){

ok = false;

continue;

}

// 文字列 X に含まれる 'A' が少ない.

if(xa.size() + xc.size() < ya.size()){

ok = false;

continue;

}

// 文字列 X に含まれる 'A' を調整.

int cur = -1;

while(xa.size() < ya.size()) xa.pb(xc[++cur]);

// sort.

sort(all(xa));

// 比較.

rep(j, xa.size()) if(xa[j] > ya[j]) ok = false;

}

// 2-5. 出力.

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

}

return 0;

}

[入力例]
6
3 ABC ABC
1 C B
1 B C
2 AB BA
2 BA AB
3 CCB ABA

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

[入力例]
7
5 ABABA BABAB
5 ABCBC BBABA
5 CCCCC CBABC
5 BBAAA AAABB
5 AAABB BBAAA
5 ACACB BAACB
5 ACACB BBACA

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

[入力例]
10
1 C B
2 AB BA
3 ACB ACC
4 ACBC ABAA
5 ACAAC ABBAA
6 ACBBCC BCBAAB
7 ABCABCB BACABCB
8 BACCABAA BBAABBAA
9 ABCABCABC ABCBABAAA
10 ABCBCABBCA BACBABBAAA

[出力例]
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes

[入力例]

3 ABC ABC

1 C B

1 B C

2 AB BA

2 BA AB

3 CCB ABA

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

5 ABABA BABAB

5 ABCBC BBABA

5 CCCCC CBABC

5 BBAAA AAABB

5 AAABB BBAAA

5 ACACB BAACB

5 ACACB BBACA

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 C B

2 AB BA

3 ACB ACC

4 ACBC ABAA

5 ACAAC ABBAA

6 ACBBCC BCBAAB

7 ABCABCB BACABCB

8 BACCABAA BBAABBAA

9 ABCABCABC ABCBABAAA

10 ABCBCABBCA BACBABBAAA

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/arc166/editorial/7183
// C++20(GCC 12.2)
#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
const LL INF = 2e18;
LL A[202020], dp[202020][8];

int main(){
    
    // 1. 入力情報.
    int N;
    LL a, b, c;
    scanf("%d %lld %lld %lld", &N, &a, &b, &c);
    rep(i, N) scanf("%lld", &A[i]);
    
    // 2. 事前準備.
    LL gAB = __gcd(a, b);
    LL gBC = __gcd(b, c);
    LL gCA = __gcd(c, a);
    LL gABC = __gcd(gAB, c);
    LL lAB = a / gAB * b;
    LL lBC = b / gBC * c;
    LL lCA = c / gCA * a;
    LL lABC = lAB / __gcd(lAB, lBC) * lBC;
    
    // 3. 倍数チェック.
    auto f = [&](LL n, LL a, LL b, LL c) -> int {
        int ret = 0;
        if(n % a == 0) ret |= 1;
        if(n % b == 0) ret |= 2;
        if(n % c == 0) ret |= 4;
        return ret;
    };
    
    // 4. dp更新.
    // -> 第二成分は, 以下のルールを, ORでとった結果をインデックスに指定.
    // a の 倍数 => 1
    // b の 倍数 => 2
    // c の 倍数 => 4
    rep(i, N + 1) rep(j, 8) dp[i][j] = INF;
    dp[0][0] = 0;
    rep(i, N){
        // 何もしない.
        vl op;
        op.pb(A[i]);
        
        // a の倍数.
        op.pb((A[i] + a - 1) / a * a);
        
        // b の倍数.
        op.pb((A[i] + b - 1) / b * b);
        
        // c の倍数.
        op.pb((A[i] + c - 1) / c * c);
        
        // lcm(a, b) の倍数.
        op.pb((A[i] + lAB - 1) / lAB * lAB);
        
        // lcm(b, c) の倍数.
        op.pb((A[i] + lBC - 1) / lBC * lBC);
        
        // lcm(c, a) の倍数.
        op.pb((A[i] + lCA - 1) / lCA * lCA);
        
        // lcm(a, b, c) の倍数.
        op.pb((A[i] + lABC - 1) / lABC * lABC);
        
        // 4-2. 各状態ごとに, dp更新.
        rep(j, 8){
            // 状態.
            int s = f(op[j], a, b, c);
            
            // 遷移(状態 k からの遷移先は, 状態 (s | k)).
            rep(k, 8){
                //  状態 s が 状態 k の 部分集合の場合.
                if((k & s) == s){
                    dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k]);
                    continue;
                }
                
                //  状態 s が 状態 k の 部分集合でない場合.
                // -> 操作回数(op[j] - A[i]) を 考慮する必要がある.
                dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k] + op[j] - A[i]);
            }
        }
    }
    
    // 5. 出力.
    printf("%lld\n", dp[N][7]);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc166/editorial/7183

// C++20(GCC 12.2)

#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

const LL INF = 2e18;

LL A[202020], dp[202020][8];

int main(){

// 1. 入力情報.

int N;

LL a, b, c;

scanf("%d %lld %lld %lld", &N, &a, &b, &c);

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

// 2. 事前準備.

LL gAB = __gcd(a, b);

LL gBC = __gcd(b, c);

LL gCA = __gcd(c, a);

LL gABC = __gcd(gAB, c);

LL lAB = a / gAB * b;

LL lBC = b / gBC * c;

LL lCA = c / gCA * a;

LL lABC = lAB / __gcd(lAB, lBC) * lBC;

// 3. 倍数チェック.

auto f = [&](LL n, LL a, LL b, LL c) -> int {

int ret = 0;

if(n % a == 0) ret |= 1;

if(n % b == 0) ret |= 2;

if(n % c == 0) ret |= 4;

return ret;

};

// 4. dp更新.

// -> 第二成分は, 以下のルールを, ORでとった結果をインデックスに指定.

// a の倍数 => 1

// b の倍数 => 2

// c の倍数 => 4

rep(i, N + 1) rep(j, 8) dp[i][j] = INF;

dp[0][0] = 0;

rep(i, N){

// 何もしない.

vl op;

op.pb(A[i]);

// a の倍数.

op.pb((A[i] + a - 1) / a * a);

// b の倍数.

op.pb((A[i] + b - 1) / b * b);

// c の倍数.

op.pb((A[i] + c - 1) / c * c);

// lcm(a, b) の倍数.

op.pb((A[i] + lAB - 1) / lAB * lAB);

// lcm(b, c) の倍数.

op.pb((A[i] + lBC - 1) / lBC * lBC);

// lcm(c, a) の倍数.

op.pb((A[i] + lCA - 1) / lCA * lCA);

// lcm(a, b, c) の倍数.

op.pb((A[i] + lABC - 1) / lABC * lABC);

// 4-2. 各状態ごとに, dp更新.

rep(j, 8){

// 状態.

int s = f(op[j], a, b, c);

// 遷移(状態 k からの遷移先は, 状態 (s | k)).

rep(k, 8){

// 状態 s が状態 k の部分集合の場合.

if((k & s) == s){

dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k]);

continue;

}

// 状態 s が状態 k の部分集合でない場合.

// -> 操作回数(op[j] - A[i]) を考慮する必要がある.

dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k] + op[j] - A[i]);

}

// 5. 出力.

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

return 0;

}

[入力例]
3 3 4 5
8 9 11

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

[入力例]
3 3 4 5
14 11 59

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

[入力例]
6 10 20 30
8 17 5 28 39 13

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

[入力例]
1 999997 999998 999999
123456789123456789

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

[入力例]
5 3 5 12
79 83 59 111 98

[出力例]
1

[入力例]
10 7 13 31
79 54 3 65 88 51 38 73 123 78

[出力例]
3

[入力例]
100 2022 2023 2024
2981 4736 3411 8068 10584 389 2608 9985 684 11830 172 7465 1191 11411 5304 7646 1078 2925 6130 5694 411 6933 11928 3835 2154 8225 5906 3628 2216 10621 3409 7540 10503 11075 10477 2243 6708 412 11670 4915 11346 2017 5480 12087 9548 8264 7241 1148 509 4393 4078 9366 11422 6376 9437 5159 2238 5775 6517 3782 9302 7383 2867 3699 8125 2688 3944 6273 9013 7226 2275 5231 804 5789 5393 5683 10756 2671 6203 233 4354 7395 12073 3130 8366 995 5174 387 10195 393 11277 4502 7461 10823 10032 9122 3627 3388 6191 2374

[出力例]
76

[入力例]
300 31415 92653 58979
95878 11042 74842 71977 8434 71909 4719 71599 5217 115259 40165 40023 73330 14444 43158 40431 69014 46069 3575 48234 111675 76805 119595 120108 48976 99043 115430 73364 68890 45442 46584 42696 16106 39204 56507 87346 71220 65320 28459 22532 120425 51503 123041 104636 86123 24584 31166 49145 51897 85658 112667 16456 46553 31285 40940 96766 112717 15172 82933 96285 35222 84816 105328 123100 98971 70784 81388 25100 35509 26758 84449 96854 115706 47557 93362 2091 50288 17447 119007 23813 56200 69886 28646 51117 69959 80929 48759 115929 102536 33102 101192 98958 33201 17629 31347 83487 100317 3081 115347 37719 97540 92178 110187 22675 88385 9638 93384 46722 69302 64303 84737 29052 109422 114147 67049 54142 89624 41003 63736 40848 44403 69120 74396 32825 31020 20000 13853 42940 110681 105457 122320 65108 27384 30617 53446 86286 39140 58644 33762 55193 110992 51746 73785 34559 13628 59067 56068 34389 108449 22996 3143 100820 85122 11175 85321 113463 31329 86003 114600 80049 78543 95285 70209 21235 79741 104283 404 102283 38151 97825 12259 8721 9886 111445 116702 94793 18335 72040 76328 26314 43995 109237 120473 110066 50128 118544 30007 93924 20116 119344 59713 118653 61229 5823 106022 58536 12814 110755 14807 82060 11455 31816 55103 44137 109484 73331 65863 97384 93461 70888 83773 78645 91691 26985 19185 26087 53981 43703 43333 101604 69706 18417 85362 64956 34082 117355 28363 92691 118224 79433 52262 19876 12428 89844 65977 57152 43797 73580 13914 108756 18039 24535 21199 64947 9724 121639 88604 64034 101861 55770 27244 6891 74806 113840 68011 76634 51062 13570 106890 121794 89934 32532 45758 17043 111584 31058 60756 36975 62134 98955 93366 56236 45379 119759 97802 75866 58850 30659 90726 21983 3572 3959 14085 85735 64424 112289 36558 10951 19387 53368 58845 11335 106045 93872 13491 18563 42606 84514 99811 10140

[出力例]
672

[入力例]

3 3 4 5

8 9 11

[出力例]

※AtCoderのテストケースより

[入力例]

3 3 4 5

14 11 59

[出力例]

※AtCoderのテストケースより

[入力例]

6 10 20 30

8 17 5 28 39 13

[出力例]

※AtCoderのテストケースより

[入力例]

1 999997 999998 999999

123456789123456789

[出力例]

876537210887543205

※AtCoderのテストケースより

[入力例]

5 3 5 12

79 83 59 111 98

[出力例]

[入力例]

10 7 13 31

79 54 3 65 88 51 38 73 123 78

[出力例]

[入力例]

100 2022 2023 2024

2981 4736 3411 8068 10584 389 2608 9985 684 11830 172 7465 1191 11411 5304 7646 1078 2925 6130 5694 411 6933 11928 3835 2154 8225 5906 3628 2216 10621 3409 7540 10503 11075 10477 2243 6708 412 11670 4915 11346 2017 5480 12087 9548 8264 7241 1148 509 4393 4078 9366 11422 6376 9437 5159 2238 5775 6517 3782 9302 7383 2867 3699 8125 2688 3944 6273 9013 7226 2275 5231 804 5789 5393 5683 10756 2671 6203 233 4354 7395 12073 3130 8366 995 5174 387 10195 393 11277 4502 7461 10823 10032 9122 3627 3388 6191 2374

[出力例]

[入力例]

300 31415 92653 58979

95878 11042 74842 71977 8434 71909 4719 71599 5217 115259 40165 40023 73330 14444 43158 40431 69014 46069 3575 48234 111675 76805 119595 120108 48976 99043 115430 73364 68890 45442 46584 42696 16106 39204 56507 87346 71220 65320 28459 22532 120425 51503 123041 104636 86123 24584 31166 49145 51897 85658 112667 16456 46553 31285 40940 96766 112717 15172 82933 96285 35222 84816 105328 123100 98971 70784 81388 25100 35509 26758 84449 96854 115706 47557 93362 2091 50288 17447 119007 23813 56200 69886 28646 51117 69959 80929 48759 115929 102536 33102 101192 98958 33201 17629 31347 83487 100317 3081 115347 37719 97540 92178 110187 22675 88385 9638 93384 46722 69302 64303 84737 29052 109422 114147 67049 54142 89624 41003 63736 40848 44403 69120 74396 32825 31020 20000 13853 42940 110681 105457 122320 65108 27384 30617 53446 86286 39140 58644 33762 55193 110992 51746 73785 34559 13628 59067 56068 34389 108449 22996 3143 100820 85122 11175 85321 113463 31329 86003 114600 80049 78543 95285 70209 21235 79741 104283 404 102283 38151 97825 12259 8721 9886 111445 116702 94793 18335 72040 76328 26314 43995 109237 120473 110066 50128 118544 30007 93924 20116 119344 59713 118653 61229 5823 106022 58536 12814 110755 14807 82060 11455 31816 55103 44137 109484 73331 65863 97384 93461 70888 83773 78645 91691 26985 19185 26087 53981 43703 43333 101604 69706 18417 85362 64956 34082 117355 28363 92691 118224 79433 52262 19876 12428 89844 65977 57152 43797 73580 13914 108756 18039 24535 21199 64947 9724 121639 88604 64034 101861 55770 27244 6891 74806 113840 68011 76634 51062 13570 106890 121794 89934 32532 45758 17043 111584 31058 60756 36975 62134 98955 93366 56236 45379 119759 97802 75866 58850 30659 90726 21983 3572 3959 14085 85735 64424 112289 36558 10951 19387 53368 58845 11335 106045 93872 13491 18563 42606 84514 99811 10140

[出力例]

672

■参照サイト
AtCoder Regular Contest 166

2023年10月17日

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

C++の練習を兼ねて, AtCoder Grand Contest 045 の問題B (01 Unbalanced) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/agc045/editorial.pdf
// C++20(GCC 12.2)
#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--)
const int INF = 2020202020;
int cum[1010101], rMaxCum[1010101], u1[1010101], u1Cum[1010101], u2[1010101], u2Cum[1010101];

int main(){
    
    // 1. 入力情報.
    char c[1010101];
    scanf("%s", c);
    string s(c);
    int n = s.size();
    
    // 2. 事前準備(以降, 解説通り).
    // 2-1. 初期化.
    rep(i, n) u1[i] = u2[i] = (s[i] == '1') ? +1 : -1;
    
    // 2-2. 累積和(左から計算).
    // -> cum[0] = 0 も 考慮する.
    rep(i, n) cum[i + 1] = (s[i] == '1') ? cum[i] + 1 : cum[i] - 1;
    
    // 2-3. 累積和の最大値(右から計算).
    rep(i, 1010101) rMaxCum[i] = -INF;
    repr(i, n, 0) rMaxCum[i] = max(rMaxCum[i + 1], cum[i]);
    
    // 3. z.
    int z = -INF;
    rep(i, n + 1) z = max(z, cum[i]);
    
    // 4. 貪欲アルゴリズム.
    // 4-1. z 基準.
    int cnt = 0;
    rep(i, n){
        // 次へ.
        if(s[i] != '?') continue;
        
        // '?' を '1' に 変更できるか？
        // 累積和(左側).
        if(cum[i + 1] + 2 * (cnt + 1) > z) continue;
        
        // 累積和(右側).
        if(rMaxCum[i + 1] + 2 * (cnt + 1) > z) continue;
        
        // '?' を '1' に 変更.
        u1[i] = +1;
        
        // インクリメント.
        ++cnt;
    }
    
    // 4-2. (z + 1) 基準.
    cnt = 0;
    rep(i, n){
        // 次へ.
        if(s[i] != '?') continue;
        
        // '?' を '1' に 変更できるか？
        // 累積和(左側).
        if(cum[i + 1] + 2 * (cnt + 1) > z + 1) continue;
        
        // 累積和(右側).
        if(rMaxCum[i + 1] + 2 * (cnt + 1) > z + 1) continue;
        
        // '?' を '1' に 変更.
        u2[i] = +1;
        
        // インクリメント.
        ++cnt;
    }
    
    // 5. 計算準備(アンバランス度).
    // 5-1. f(z).
    int f1 = INF;
    rep(i, n) u1Cum[i + 1] = u1Cum[i] + u1[i];
    rep(i, n + 1) f1 = min(f1, u1Cum[i]);
    
    // 5-2. f(z + 1).
    int f2 = INF;
    rep(i, n) u2Cum[i + 1] = u2Cum[i] + u2[i];
    rep(i, n + 1) f2 = min(f2, u2Cum[i]);
    
    // 6. 出力.
    printf("%d\n", min(z - f1, z + 1 - f2));
    return 0;
    
}

// 解き直し.

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

// C++20(GCC 12.2)

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

const int INF = 2020202020;

int cum[1010101], rMaxCum[1010101], u1[1010101], u1Cum[1010101], u2[1010101], u2Cum[1010101];

int main(){

// 1. 入力情報.

char c[1010101];

scanf("%s", c);

string s(c);

int n = s.size();

// 2. 事前準備(以降, 解説通り).

// 2-1. 初期化.

rep(i, n) u1[i] = u2[i] = (s[i] == '1') ? +1 : -1;

// 2-2. 累積和(左から計算).

// -> cum[0] = 0 も考慮する.

rep(i, n) cum[i + 1] = (s[i] == '1') ? cum[i] + 1 : cum[i] - 1;

// 2-3. 累積和の最大値(右から計算).

rep(i, 1010101) rMaxCum[i] = -INF;

repr(i, n, 0) rMaxCum[i] = max(rMaxCum[i + 1], cum[i]);

// 3. z.

int z = -INF;

rep(i, n + 1) z = max(z, cum[i]);

// 4. 貪欲アルゴリズム.

// 4-1. z 基準.

int cnt = 0;

rep(i, n){

// 次へ.

if(s[i] != '?') continue;

// '?' を '1' に変更できるか？

// 累積和(左側).

if(cum[i + 1] + 2 * (cnt + 1) > z) continue;

// 累積和(右側).

if(rMaxCum[i + 1] + 2 * (cnt + 1) > z) continue;

// '?' を '1' に変更.

u1[i] = +1;

// インクリメント.

++cnt;

}

// 4-2. (z + 1) 基準.

cnt = 0;

rep(i, n){

// 次へ.

if(s[i] != '?') continue;

// '?' を '1' に変更できるか？

// 累積和(左側).

if(cum[i + 1] + 2 * (cnt + 1) > z + 1) continue;

// 累積和(右側).

if(rMaxCum[i + 1] + 2 * (cnt + 1) > z + 1) continue;

// '?' を '1' に変更.

u2[i] = +1;

// インクリメント.

++cnt;

}

// 5. 計算準備(アンバランス度).

// 5-1. f(z).

int f1 = INF;

rep(i, n) u1Cum[i + 1] = u1Cum[i] + u1[i];

rep(i, n + 1) f1 = min(f1, u1Cum[i]);

// 5-2. f(z + 1).

int f2 = INF;

rep(i, n) u2Cum[i + 1] = u2Cum[i] + u2[i];

rep(i, n + 1) f2 = min(f2, u2Cum[i]);

// 6. 出力.

printf("%d\n", min(z - f1, z + 1 - f2));

return 0;

}

[入力例]
0??

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

[入力例]
0??0

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

[入力例]
??00????0??0????0?0??00??1???11?1?1???1?11?111???1

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

[入力例]
01??10?1?0

[出力例]
2

[入力例]
10?0??101??

[出力例]
1

[入力例]
0010??0???01010?00110?101011?0?101111?0??0?111?010

[出力例]
4

[入力例]
??111110100000000???1100??0???11110???0000??1100111110000111??11??1110111111??001111?111100111110000

[出力例]
16

[入力例]
00?11??011111?0101000??11???01??10?10??0?1?0011??1?00?00???10?0011?0?1001011?110000??0010?001010?1??1110?01011?00111?10?1?1??00?10?00??111?000?11?001?01??11?0100?00111???1???????1?001011011?0?0?1?0?0?

[出力例]
5

[入力例]
010?00??10?001????1111??0110111?101?0111001?1?10?11?1??1?01?10?0100000001?101??1?1?????00????1?1??00?0111?1?11?000?011????0000100001010?110?0??100110?0001100???100?000111?00?110?0?10011?011010??01?0001?01??1001010??1???1?00110?10000?0100????1001?110101?1?11000?000011010101?????01?01110???1?010110011101?000??1?010110100?0?1?10101001?01???11100?110100110?11?11100100101?101110?11110?010?1??0?00??0010001?010??10?1000?01?1010???00000?111?1??101??00100??0???1???0001011001101010?0011?1111?0??1001110?0?1?1?1?1??00?0??100?001011??10??10010???1??100?0?0?0?1110?00?111??101???11011000001?100?1??1000?111?1?01110101101?1?1??011?010?1?01011?11??001?110?10?10?1011?0?1?10????110?100100100100?0??00101???111000?10?011?0?0?????1?1010??0011000??0???01?10?1?1001?00??0??0?011011?00??10?011??1?100110?1??011010?101?1??10011?111100??111101111?1???1?101?1?110?1?01101?1???1011101?111001?0????0??011?0?000???01?11?001?011?0?11001001101?0??0??0?1011?1111???101100?1?01??0110101011?1??10?1????00???01?1?11000100?10?0??

[出力例]
8

[入力例]

0??

[出力例]

※AtCoderのテストケースより

[入力例]

0??0

[出力例]

※AtCoderのテストケースより

[入力例]

??00????0??0????0?0??00??1???11?1?1???1?11?111???1

[出力例]

※AtCoderのテストケースより

[入力例]

01??10?1?0

[出力例]

[入力例]

10?0??101??

[出力例]

[入力例]

0010??0???01010?00110?101011?0?101111?0??0?111?010

[出力例]

[入力例]

??111110100000000???1100??0???11110???0000??1100111110000111??11??1110111111??001111?111100111110000

[出力例]

[入力例]

00?11??011111?0101000??11???01??10?10??0?1?0011??1?00?00???10?0011?0?1001011?110000??0010?001010?1??1110?01011?00111?10?1?1??00?10?00??111?000?11?001?01??11?0100?00111???1???????1?001011011?0?0?1?0?0?

[出力例]

[入力例]

010?00??10?001????1111??0110111?101?0111001?1?10?11?1??1?01?10?0100000001?101??1?1?????00????1?1??00?0111?1?11?000?011????0000100001010?110?0??100110?0001100???100?000111?00?110?0?10011?011010??01?0001?01??1001010??1???1?00110?10000?0100????1001?110101?1?11000?000011010101?????01?01110???1?010110011101?000??1?010110100?0?1?10101001?01???11100?110100110?11?11100100101?101110?11110?010?1??0?00??0010001?010??10?1000?01?1010???00000?111?1??101??00100??0???1???0001011001101010?0011?1111?0??1001110?0?1?1?1?1??00?0??100?001011??10??10010???1??100?0?0?0?1110?00?111??101???11011000001?100?1??1000?111?1?01110101101?1?1??011?010?1?01011?11??001?110?10?10?1011?0?1?10????110?100100100100?0??00101???111000?10?011?0?0?????1?1010??0011000??0???01?10?1?1001?00??0??0?011011?00??10?011??1?100110?1??011010?101?1??10011?111100??111101111?1???1?101?1?110?1?01101?1???1011101?111001?0????0??011?0?000???01?11?001?011?0?11001001101?0??0??0?1011?1111???101100?1?01??0110101011?1??10?1????00???01?1?11000100?10?0??

[出力例]

■参照サイト
AtCoder Grand Contest 045

2023年10月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 321 の問題C (321-like Searcher) ～問題D (Set Menu) を解いてみた.

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

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

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

int main(){
    
    // 1. 入力情報.
    int K;
    scanf("%d", &K);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    set<LL> st;
    auto dfs = [&](auto&& self, LL d){
        // 2-1. 保存.
        st.insert(d);
        
        // 2-2. 終了条件.
        int r = d % 10;
        if(r == 0) return;
        
        // 2-3. 追加(1 の 位).
        rep(i, r) self(self, 10 * d + i);
    };
    
    // 3. 321-like Number 生成(1022個).
    repx(i, 1, 10) dfs(dfs, i);
    // printf("st.size()=%d\n", st.size());
    
    // 4. K 番目は？
    LL ans = 0;
    for(auto &x : st){
        ans = x;
        if(--K == 0) break;
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

// 2. dfs.

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

set<LL> st;

auto dfs = [&](auto&& self, LL d){

// 2-1. 保存.

st.insert(d);

// 2-2. 終了条件.

int r = d % 10;

if(r == 0) return;

// 2-3. 追加(1 の位).

rep(i, r) self(self, 10 * d + i);

};

// 3. 321-like Number 生成(1022個).

repx(i, 1, 10) dfs(dfs, i);

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

// 4. K 番目は？

LL ans = 0;

for(auto &x : st){

ans = x;

if(--K == 0) break;

}

// 5. 出力.

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

return 0;

}

[入力例]
15

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

[入力例]
321

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

[入力例]
777

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

[入力例]
20

[出力例]
50

[入力例]
100

[出力例]
750

[入力例]
753

[出力例]
975421

[入力例]
1022

[出力例]
9876543210

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

321

[出力例]

9610

※AtCoderテストケースより

[入力例]

777

[出力例]

983210

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

100

[出力例]

750

[入力例]

753

[出力例]

975421

[入力例]

1022

[出力例]

9876543210

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

// C++20(GCC 12.2)
#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 all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, M, P;
    scanf("%d %d %d", &N, &M, &P);
    vl a(N), b(M);
    rep(i, N) scanf("%lld", &a[i]);
    rep(i, M) scanf("%lld", &b[i]);
    
    // 2. sort.
    sort(all(a));
    sort(all(b));
    
    // 3. 累積和.
    vl bCum(M + 1, 0);
    rep(i, M) bCum[i + 1] = bCum[i] + b[i];
    
    // 4. 定食の価格の総和.
    LL ans = 0;
    rep(i, N){
        int at = lower_bound(all(b), P - a[i]) - b.begin();
        ans += bCum[at] + a[i] * at;
        ans += (LL)P * (LL)(M - at);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

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

int main(){

// 1. 入力情報.

int N, M, P;

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

vl a(N), b(M);

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

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

// 2. sort.

sort(all(a));

sort(all(b));

// 3. 累積和.

vl bCum(M + 1, 0);

rep(i, M) bCum[i + 1] = bCum[i] + b[i];

// 4. 定食の価格の総和.

LL ans = 0;

rep(i, N){

int at = lower_bound(all(b), P - a[i]) - b.begin();

ans += bCum[at] + a[i] * at;

ans += (LL)P * (LL)(M - at);

}

// 5. 出力.

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

return 0;

}

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

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

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

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

[入力例]
7 12 25514963
2436426 24979445 61648772 23690081 33933447 76190629 62703497
11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857

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

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

[出力例]
150

[入力例]
5 3 10
11 12 13 14 15
16 17 18

[出力例]
150

[入力例]
12 15 100000
64871 99252 11934 88203 110776 8275 1116 81869 16238 6552 17514 71649
47327 17873 111561 24780 17782 18870 51552 44546 113673 91382 32723 10999 103361 53973 64043

[出力例]
14227081

[入力例]
30 50 2500
2453 1367 2387 1093 613 1649 1990 910 101 913 1745 1644 2016 1796 1518 2112 2492 1139 2145 703 2225 959 2408 691 1529 864 821 951 2030 2364
1319 857 921 1939 2203 1884 1799 565 2018 1595 12 1638 996 1197 740 1038 2449 1073 1580 2449 1871 870 111 1576 2410 769 1711 2475 1634 2354 1884 1919 943 446 385 803 1618 348 358 1904 2045 2310 1782 1419 1126 1067 1535 64 2161 121

[出力例]
3402202

[入力例]
100 120 33333
14021 11206 4523 11383 704 21471 18313 12778 19149 10164 17165 10474 9934 2338 7657 12326 24422 6017 7482 7051 11148 13353 9444 16507 22077 21448 71255 20038 11640 17509 20149 7140 11280 327 22036 7580 8152 8686 15626 2617 21718 24964 9124 2813 13294 7855 24045 33238 13222 17043 13099 13126 18103 11068 22719 18441 1408 3640 7297 17074 4026 19471 20520 16667 10446 10834 12555 23445 1400 9644 24859 5472 222 23622 5946 23745 1440 1177 11130 8323 6627 24306 2669 229 18585 22270 5108 3641 4965 7130 11704 12396 19223 20115 17845 15612 10896 28 16299 12696
5280 16707 19516 17340 17379 56449 5037 11102 13189 13580 21477 22974 4607 17792 23474 23608 13913 18909 16060 3294 24606 6395 10719 10251 5608 22507 468 14804 8974 1357 4676 2748 111 18762 22817 9519 22569 14121 2198 13482 8642 4809 12622 23327 21821 6910 7153 19971 88783 4436 2067 20006 24267 9989 12288 2916 897 13812 205 14842 3604 6621 13595 932 11239 2238 176 20816 52247 12707 12895 71897 23032 8565 158 11641 21871 15146 6251 14621 2671 19909 21476 15272 5099 18902 16681 12731 3174 3155 4544 11628 23976 18968 3208 4721 24082 13040 4900 5015 5437 133 23114 20152 24286 8952 7540 11692 19253 20774 22949 20821 21565 3656 12576 6234 2845 1739 6693 728

[出力例]
282120162

[入力例]

2 2 7

3 5

6 1

[出力例]

※AtCoderテストケースより

[入力例]

1 3 2

1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

7 12 25514963

2436426 24979445 61648772 23690081 33933447 76190629 62703497

11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857

[出力例]

2115597124

※AtCoderテストケースより

[入力例]

5 3 123

1 2 3 4 5

6 7 8

[出力例]

150

[入力例]

5 3 10

11 12 13 14 15

16 17 18

[出力例]

150

[入力例]

12 15 100000

64871 99252 11934 88203 110776 8275 1116 81869 16238 6552 17514 71649

47327 17873 111561 24780 17782 18870 51552 44546 113673 91382 32723 10999 103361 53973 64043

[出力例]

14227081

[入力例]

30 50 2500

2453 1367 2387 1093 613 1649 1990 910 101 913 1745 1644 2016 1796 1518 2112 2492 1139 2145 703 2225 959 2408 691 1529 864 821 951 2030 2364

1319 857 921 1939 2203 1884 1799 565 2018 1595 12 1638 996 1197 740 1038 2449 1073 1580 2449 1871 870 111 1576 2410 769 1711 2475 1634 2354 1884 1919 943 446 385 803 1618 348 358 1904 2045 2310 1782 1419 1126 1067 1535 64 2161 121

[出力例]

3402202

[入力例]

100 120 33333

14021 11206 4523 11383 704 21471 18313 12778 19149 10164 17165 10474 9934 2338 7657 12326 24422 6017 7482 7051 11148 13353 9444 16507 22077 21448 71255 20038 11640 17509 20149 7140 11280 327 22036 7580 8152 8686 15626 2617 21718 24964 9124 2813 13294 7855 24045 33238 13222 17043 13099 13126 18103 11068 22719 18441 1408 3640 7297 17074 4026 19471 20520 16667 10446 10834 12555 23445 1400 9644 24859 5472 222 23622 5946 23745 1440 1177 11130 8323 6627 24306 2669 229 18585 22270 5108 3641 4965 7130 11704 12396 19223 20115 17845 15612 10896 28 16299 12696

5280 16707 19516 17340 17379 56449 5037 11102 13189 13580 21477 22974 4607 17792 23474 23608 13913 18909 16060 3294 24606 6395 10719 10251 5608 22507 468 14804 8974 1357 4676 2748 111 18762 22817 9519 22569 14121 2198 13482 8642 4809 12622 23327 21821 6910 7153 19971 88783 4436 2067 20006 24267 9989 12288 2916 897 13812 205 14842 3604 6621 13595 932 11239 2238 176 20816 52247 12707 12895 71897 23032 8565 158 11641 21871 15146 6251 14621 2671 19909 21476 15272 5099 18902 16681 12731 3174 3155 4544 11628 23976 18968 3208 4721 24082 13040 4900 5015 5437 133 23114 20152 24286 8952 7540 11692 19253 20774 22949 20821 21565 3656 12576 6234 2845 1739 6693 728

[出力例]

282120162

■参照サイト
サントリープログラミングコンテスト2023（AtCoder Beginner Contest 321）

C++の練習を兼ねて, AtCoder Beginner Contest 328 の 問題C (Consecutive) ～ 問題E (Modulo MST) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 048 の 問題C (Penguin Skating) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 048 の 問題A (atcoder < S) ～ 問題B (Bracket Score) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 166 の 問題C (LU / RD Marking) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 324 の 問題E (Joint Two Strings) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 324 の 問題C (Error Correction) ～ 問題D (Square Permutation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 166 の 問題A (Replace C or Swap AB) ～ 問題B (Make Multiples) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 045 の 問題B (01 Unbalanced) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 321 の 問題C (321-like Searcher) ～ 問題D (Set Menu) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 328 の問題C (Consecutive) ～問題E (Modulo MST) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 048 の問題C (Penguin Skating) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 048 の問題A (atcoder < S) ～問題B (Bracket Score) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 166 の問題C (LU / RD Marking) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 324 の問題E (Joint Two Strings) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 324 の問題C (Error Correction) ～問題D (Square Permutation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 166 の問題A (Replace C or Swap AB) ～問題B (Make Multiples) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 045 の問題B (01 Unbalanced) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 321 の問題C (321-like Searcher) ～問題D (Set Menu) を解いてみた.