C++ | 個人用メモ帳

2023年1月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 284 の問題C (Count Connected Components) ～問題D (Happy New Year 2023) を解いてみた.

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

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

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

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

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

rep(i, M){

int u, v;

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

--u;

--v;

G[u].pb(v);

G[v].pb(u);

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

int c[N], idx = 0;

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

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

// 3. 出力.

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

return 0;

}

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

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

[入力例]
5 0

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

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

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

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

[出力例]
3

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

[出力例]
5

[入力例]

5 3

1 2

1 3

4 5

[出力例]

※AtCoderテストケースより

[入力例]

5 0

[出力例]

※AtCoderテストケースより

[入力例]

4 6

1 2

1 3

1 4

2 3

2 4

3 4

[出力例]

※AtCoderテストケースより

[入力例]

10 9

1 2

1 3

1 4

4 5

5 3

8 6

6 7

8 7

10 9

[出力例]

[入力例]

15 13

1 2

3 2

3 1

5 4

8 6

7 8

7 6

14 9

10 11

10 12

12 13

13 11

12 15

[出力例]

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

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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. 各テストケース.
    rep(i, T){
        // 2-1. テストケース入力情報.
        LL N;
        scanf("%lld", &N);
        
        // 2-2. 全探索①.
        LL p = 0, q = 0;
        repx(j, 2, 3e6){
            p = (LL)j * (LL)j;
            if(N % p == 0){
                q = N / p;
                p = (LL)j;
                break;
            }
        }
        
        // 2-3. 全探索②.
        if(q == 0){
            repx(j, 2, 3e6){
                if(N % j == 0){
                    q = j;
                    p = sqrt(N / j);
                    break;
                }
            }
        }
        
        // 2-4. 出力.
        printf("%lld %lld\n", p, q);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

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

rep(i, T){

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

LL N;

scanf("%lld", &N);

// 2-2. 全探索①.

LL p = 0, q = 0;

repx(j, 2, 3e6){

p = (LL)j * (LL)j;

if(N % p == 0){

q = N / p;

p = (LL)j;

break;

}

// 2-3. 全探索②.

if(q == 0){

repx(j, 2, 3e6){

if(N % j == 0){

q = j;

p = sqrt(N / j);

break;

}

// 2-4. 出力.

printf("%lld %lld\n", p, q);

}

return 0;

}

[入力例]
3
2023
63
1059872604593911

[出力例]
17 7
3 7
104149 97711
※AtCoderテストケースより

[入力例]
10
63
3751
367993
39222097
3496614446479897
6007566492867211
3171141802799143
45724737732053043
275110496206371005
563923222347365761

[出力例]
3 7
11 31
71 73
733 73
118081 250777
900349 7411
99901 317743
123456791 3
234567899 5
778777 929809

[入力例]

2023

1059872604593911

[出力例]

17 7

3 7

104149 97711

※AtCoderテストケースより

[入力例]

3751

367993

39222097

3496614446479897

6007566492867211

3171141802799143

45724737732053043

275110496206371005

563923222347365761

[出力例]

3 7

11 31

71 73

733 73

118081 250777

900349 7411

99901 317743

123456791 3

234567899 5

778777 929809

■参照サイト
AtCoder Beginner Contest 284

2023年1月17日

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

C++の練習を兼ねて, AtCoder Beginner Contest 215 の問題G (Colorful Candies 2) を解いてみた.

■感想.
1. 問題Gは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 期待値の性質について, 学習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc215/editorial/2497
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
const LL MOD = 998244353;
const int LIMIT = 50505;
LL FAC[LIMIT], INV[LIMIT];

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<LL, LL> n;
    rep(i, N){
        LL c;
        scanf("%lld", &c);
        ++n[c];
    }
    
    // 2. 事前準備.
    FAC[0] = INV[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = (LL)i * FAC[i - 1] % MOD;
        INV[i] = mPow(FAC[i], MOD - 2);
    }
    
    // 3. n = x となる種類数 の 個数.
    map<LL, LL> a;
    for(auto &x : n) ++a[x.b];
    
    // 4. 各ケースの期待値.
    repx(k, 1, N + 1){
        // 4-1. 集計(分子).
        LL ans = 0, C = combination(N, k);
        for(auto &p : a){
            ans += p.b * (C + MOD - combination(N - p.a, k)) % MOD;
            ans %= MOD;
        }
        
        // 4-2. 集計(分母).
        ans *= mPow(C, MOD - 2);
        ans %= MOD;
        
        // 4-3. 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc215/editorial/2497

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

#define b second

const LL MOD = 998244353;

const int LIMIT = 50505;

LL FAC[LIMIT], INV[LIMIT];

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

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

// @param b: 指数.

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

LL mPow(LL a, LL b){

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t;

}

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

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

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

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

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

LL combination(LL n, LL k){

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

if(n == k || k == 0LL) return 1LL;

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

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<LL, LL> n;

rep(i, N){

LL c;

scanf("%lld", &c);

++n[c];

}

// 2. 事前準備.

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

repx(i, 1, LIMIT){

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

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

}

// 3. n = x となる種類数の個数.

map<LL, LL> a;

for(auto &x : n) ++a[x.b];

// 4. 各ケースの期待値.

repx(k, 1, N + 1){

// 4-1. 集計(分子).

LL ans = 0, C = combination(N, k);

for(auto &p : a){

ans += p.b * (C + MOD - combination(N - p.a, k)) % MOD;

ans %= MOD;

}

// 4-2. 集計(分母).

ans *= mPow(C, MOD - 2);

ans %= MOD;

// 4-3. 出力.

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

}

return 0;

}

[入力例]
3
1 2 2

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

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

[出力例]
1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7
※AtCoderテストケースより

[入力例]
5
1 2 3 2 1

[出力例]
1
399297743
199648873
399297744
3

[入力例]
30
11 13 17 11 15 13 16 17 12 14 15 15 15 15 10 16 15 15 16 16 16 14 14 14 10 15 10 17 13 12

[出力例]
1
562229580
319389021
415434298
975870615
53715478
501543505
339533645
154451006
238429014
173030800
653731178
429089161
262362724
934047753
339060528
788588261
758430204
295930312
450468204
118934339
752164850
486064297
256002128
597156160
842379096
517070913
800890305
8
8

[入力例]
50
11 13 10 20 21 17 20 14 21 11 13 12 18 21 14 11 15 11 17 15 13 18 16 11 14 18 15 12 14 21 21 20 15 14 15 15 10 17 10 18 17 19 17 18 10 18 12 10 17 18

[出力例]
1
224095673
671981431
633115787
595544474
547699361
900336322
276842986
392056943
288893097
135364271
844271167
751503079
571334287
894503529
452728420
378573628
722948910
448621936
139198593
673557343
99923386
926211909
113495582
941823113
68601316
927699740
800024195
707229517
432983203
870852727
959336993
422426853
567436911
383072599
154361806
853215869
540561324
994916051
847242386
415883070
510878726
436585674
421512894
727120358
668008835
775931273
359367979
678806172
12

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

[入力例]

1 2 2

[出力例]

665496237

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2 6 5 3 5

[出力例]

725995895

532396991

768345657

786495555

937744700

574746754

48399732

707846002

907494873

※AtCoderテストケースより

[入力例]

1 2 3 2 1

[出力例]

399297743

199648873

399297744

[入力例]

11 13 17 11 15 13 16 17 12 14 15 15 15 15 10 16 15 15 16 16 16 14 14 14 10 15 10 17 13 12

[出力例]

562229580

319389021

415434298

975870615

53715478

501543505

339533645

154451006

238429014

173030800

653731178

429089161

262362724

934047753

339060528

788588261

758430204

295930312

450468204

118934339

752164850

486064297

256002128

597156160

842379096

517070913

800890305

[入力例]

11 13 10 20 21 17 20 14 21 11 13 12 18 21 14 11 15 11 17 15 13 18 16 11 14 18 15 12 14 21 21 20 15 14 15 15 10 17 10 18 17 19 17 18 10 18 12 10 17 18

[出力例]

224095673

671981431

633115787

595544474

547699361

900336322

276842986

392056943

288893097

135364271

844271167

751503079

571334287

894503529

452728420

378573628

722948910

448621936

139198593

673557343

99923386

926211909

113495582

941823113

68601316

927699740

800024195

707229517

432983203

870852727

959336993

422426853

567436911

383072599

154361806

853215869

540561324

994916051

847242386

415883070

510878726

436585674

421512894

727120358

668008835

775931273

359367979

678806172

■参照サイト
AtCoder Beginner Contest 215

2023年1月16日2023年1月16日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc215/editorial/2492
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
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 pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp v(N);
    rep(i, N) scanf("%lld %lld", &v[i].a, &v[i].b);
    
    // 2. sort.
    sort(all(v));
    
    // 3. 評価関数.
    // -> 距離 K 以上 の ペアがあるか？
    auto f = [&](LL K) -> bool {
        int l = 0;
        LL yMin = 1e9 + 1, yMax = -1;
        rep(r, N){
            int cur = l;
            // 各座標情報(右側).
            LL sx = v[r].a;
            LL sy = v[r].b;
            repx(j, cur, r + 1){
                // 各座標情報(左側).
                LL gx = v[j].a;
                LL gy = v[j].b;
                
                // 終了.
                if(sx - gx < K) break;
                
                // 最小値, 最大値更新.
                yMin = min(yMin, gy);
                yMax = max(yMax, gy);
                
                // 見つかった場合.
                if(yMin <= sy - K || yMax >= sy + K) return true;
                
                // 次へ.
                l = j;
            }
        }
        
        // 見つからなかった場合.
        return false;
    };
    
    // 4. 二分探索で確認してみる.
    LL l = -1, h = 2e9 + 1, m;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
    }
    
    // 5. 出力.
    printf("%lld\n", l);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc215/editorial/2492

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

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 pb push_back

#define a first

#define b second

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp v(N);

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

// 2. sort.

sort(all(v));

// 3. 評価関数.

// -> 距離 K 以上のペアがあるか？

auto f = [&](LL K) -> bool {

int l = 0;

LL yMin = 1e9 + 1, yMax = -1;

rep(r, N){

int cur = l;

// 各座標情報(右側).

LL sx = v[r].a;

LL sy = v[r].b;

repx(j, cur, r + 1){

// 各座標情報(左側).

LL gx = v[j].a;

LL gy = v[j].b;

// 終了.

if(sx - gx < K) break;

// 最小値, 最大値更新.

yMin = min(yMin, gy);

yMax = max(yMax, gy);

// 見つかった場合.

if(yMin <= sy - K || yMax >= sy + K) return true;

// 次へ.

l = j;

}

// 見つからなかった場合.

return false;

};

// 4. 二分探索で確認してみる.

LL l = -1, h = 2e9 + 1, m;

while(l + 1 < h){

LL m = (h + l) >> 1;

if(f(m)) l = m;

else h = m;

}

// 5. 出力.

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

return 0;

}

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

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

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

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

[入力例]
8
897 729
802 969
765 184
992 887
1 104
521 641
220 909
380 378

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

[入力例]
20
94 47
81 102
1 9
45 82
49 5
4 0
110 100
104 66
44 35
30 104
50 90
9 19
34 109
2 116
121 60
89 83
94 20
37 113
63 94
89 55

[出力例]
100

[入力例]
50
85 448
943 216
761 879
224 293
768 664
617 775
106 1166
252 798
921 811
611 746
545 289
162 1177
30 1117
530 913
766 858
988 297
404 207
80 149
878 1056
162 490
0 927
402 1069
871 322
380 1041
345 1131
1189 446
607 1135
643 1066
694 344
474 1162
50 514
1054 1106
37 1056
1090 1218
474 76
912 906
865 166
853 200
283 870
414 343
183 180
1099 733
1056 230
692 1074
1011 914
691 1143
728 251
964 1017
588 1142
239 1062

[出力例]
1010

[入力例]
100
286033 1217893
664787 230009
947285 1162937
750486 116732
79391 988295
639738 364720
868752 369477
254524 222021
966435 870148
778311 1166200
388526 988972
894196 31825
436771 261880
1077274 249524
716297 1152108
746185 556348
93283 1087575
1111088 438298
596568 22609
524686 855060
382247 861072
36078 388585
194112 429271
782995 138807
1172838 632330
591733 692833
978763 405768
620759 802057
1010149 942025
1180449 978699
972169 731259
101210 998916
970443 574502
389234 498472
43488 393092
1141701 928848
974239 332735
307946 735292
700332 530765
105892 902668
1096578 189964
972122 16451
802819 1078840
757005 953590
69424 137776
1148394 457930
646654 681723
576772 531513
411683 1062036
1177876 1039889
1116350 876345
811266 930392
485282 498721
435481 29193
281045 863100
141626 231940
145172 1037358
612239 1040466
605107 735442
688082 1183399
1103928 333561
27995 1048724
346709 656492
652222 979437
507995 437219
903619 21833
913903 1053229
850703 485558
312095 313053
464226 852029
396691 634270
1003024 1030050
104968 1025267
242293 960715
484993 828327
250189 29449
960538 50219
385467 965721
479300 462724
483741 785154
1098644 1137776
155363 867808
1172060 97921
560779 858203
1091400 1127842
86940 1084870
1124662 196631
864314 752303
1218237 739770
355224 582086
185230 1153750
196179 352570
916618 13590
851336 1147358
562513 230921
562686 499132
705064 621079
313336 526612
306605 772850
258570 797791

[出力例]
1000000

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

[入力例]

0 3

3 1

4 10

[出力例]

※AtCoderテストケースより

[入力例]

0 1

0 4

0 10

0 6

[出力例]

※AtCoderテストケースより

[入力例]

897 729

802 969

765 184

992 887

1 104

521 641

220 909

380 378

[出力例]

801

※AtCoderテストケースより

[入力例]

94 47

81 102

1 9

45 82

49 5

4 0

110 100

104 66

44 35

30 104

50 90

9 19

34 109

2 116

121 60

89 83

94 20

37 113

63 94

89 55

[出力例]

100

[入力例]

85 448

943 216

761 879

224 293

768 664

617 775

106 1166

252 798

921 811

611 746

545 289

162 1177

30 1117

530 913

766 858

988 297

404 207

80 149

878 1056

162 490

0 927

402 1069

871 322

380 1041

345 1131

1189 446

607 1135

643 1066

694 344

474 1162

50 514

1054 1106

37 1056

1090 1218

474 76

912 906

865 166

853 200

283 870

414 343

183 180

1099 733

1056 230

692 1074

1011 914

691 1143

728 251

964 1017

588 1142

239 1062

[出力例]

1010

[入力例]

100

286033 1217893

664787 230009

947285 1162937

750486 116732

79391 988295

639738 364720

868752 369477

254524 222021

966435 870148

778311 1166200

388526 988972

894196 31825

436771 261880

1077274 249524

716297 1152108

746185 556348

93283 1087575

1111088 438298

596568 22609

524686 855060

382247 861072

36078 388585

194112 429271

782995 138807

1172838 632330

591733 692833

978763 405768

620759 802057

1010149 942025

1180449 978699

972169 731259

101210 998916

970443 574502

389234 498472

43488 393092

1141701 928848

974239 332735

307946 735292

700332 530765

105892 902668

1096578 189964

972122 16451

802819 1078840

757005 953590

69424 137776

1148394 457930

646654 681723

576772 531513

411683 1062036

1177876 1039889

1116350 876345

811266 930392

485282 498721

435481 29193

281045 863100

141626 231940

145172 1037358

612239 1040466

605107 735442

688082 1183399

1103928 333561

27995 1048724

346709 656492

652222 979437

507995 437219

903619 21833

913903 1053229

850703 485558

312095 313053

464226 852029

396691 634270

1003024 1030050

104968 1025267

242293 960715

484993 828327

250189 29449

960538 50219

385467 965721

479300 462724

483741 785154

1098644 1137776

155363 867808

1172060 97921

560779 858203

1091400 1127842

86940 1084870

1124662 196631

864314 752303

1218237 739770

355224 582086

185230 1153750

196179 352570

916618 13590

851336 1147358

562513 230921

562686 499132

705064 621079

313336 526612

306605 772850

258570 797791

[出力例]

1000000

■参照サイト
AtCoder Beginner Contest 215

2023年1月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 215 の問題E (Chain Contestant) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc215/editorial/2483
// 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[2][1 << 10][11];

int main(){
    
    // 1. 入力情報.
    int N;
    char c[1010];
    scanf("%d %s", &N, c);
    string s(c);
    
    // 2. dp更新.
    rep(i, N){
        // 前回分反映.
        rep(u, 1 << 10) rep(j, 10) dp[1][u][j] = dp[0][u][j];
        
        // 今回分反映.
        // コンテストの種類 x.
        int x = s[i] - 'A';
        
        // 全ての集合 U, 任意のコンテストの種類 j.
        rep(u, 1 << 10) rep(j, 10) if(j == x) dp[1][u][j] = (dp[1][u][j] + dp[0][u][j]) % MOD;
        
        // x を含まない全ての集合 V, 任意のコンテストの種類 j.
        rep(v, 1 << 10){
            if(v & (1 << x)) continue;
            rep(j, 10) dp[1][v | (1 << x)][x] = (dp[1][v | (1 << x)][x] + dp[0][v][j]) % MOD;
        }
        
        // x のみ含む集合 W.
        dp[1][1 << x][x] = (dp[1][1 << x][x] + 1) % MOD;
        
        // 前回分保存.
        rep(u, 1 << 10) rep(j, 10) dp[0][u][j] = dp[1][u][j];
    }
    
    // 3. 集計.
    LL ans = 0;
    rep(u, 1 << 10) rep(j, 10) ans = (ans + dp[1][u][j]) % MOD;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc215/editorial/2483

// 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[2][1 << 10][11];

int main(){

// 1. 入力情報.

int N;

char c[1010];

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

string s(c);

// 2. dp更新.

rep(i, N){

// 前回分反映.

rep(u, 1 << 10) rep(j, 10) dp[1][u][j] = dp[0][u][j];

// 今回分反映.

// コンテストの種類 x.

int x = s[i] - 'A';

// 全ての集合 U, 任意のコンテストの種類 j.

rep(u, 1 << 10) rep(j, 10) if(j == x) dp[1][u][j] = (dp[1][u][j] + dp[0][u][j]) % MOD;

// x を含まない全ての集合 V, 任意のコンテストの種類 j.

rep(v, 1 << 10){

if(v & (1 << x)) continue;

rep(j, 10) dp[1][v | (1 << x)][x] = (dp[1][v | (1 << x)][x] + dp[0][v][j]) % MOD;

}

// x のみ含む集合 W.

dp[1][1 << x][x] = (dp[1][1 << x][x] + 1) % MOD;

// 前回分保存.

rep(u, 1 << 10) rep(j, 10) dp[0][u][j] = dp[1][u][j];

}

// 3. 集計.

LL ans = 0;

rep(u, 1 << 10) rep(j, 10) ans = (ans + dp[1][u][j]) % MOD;

// 4. 出力.

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

return 0;

}

[入力例]
4
BGBH

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

[入力例]
100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

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

[入力例]
5
ABABA

[出力例]
20

[入力例]
10
DIBFDECJCG

[出力例]
699

[入力例]
20
ABIFIJFGCJCABBAFFDIG

[出力例]
50479

[入力例]
30
ABCDEFGHIJABCDEEDCBAJIHGFEDCBA

[出力例]
1311156

[入力例]
500
ABCDEFGHIJFGADFEHBGCCBCFCCAABIBIFCDCHFCIAHDCGFIJIHCAEHBCADHBGGFBBFDGHECDBGGDDFDADDICEABCABBFFFEDAHAECFBBJFGEJFGAEACIGFIAACDEIHFJABFJBCDCCDEDFFFDAIBHCEFFIAJHDEBJBEFEDHIDHIBEIDDDFBCBIDDIAJEGBEBJGIAFDGCJGHHCBDIEHGJCBAEEIIHGEGBGJEIECGBGIEADABEJDCHDFHBHBHFBJFFBIAFBJJCJHJCJDDICHCGFCIHBAFJDIFJHFGJCCIHAJEBGHFFEFHADGIHCAJBHHHCHHDEIAFICHECGHIIIFJHACHJCEAECJDDHICJGDIDAAIGECJFCGCCCIBJBBAGGACBEBAGIEBGCEJCCEIGGEEAEICFFDECHCDBEEHEADDEDGACHDEGFCGEBADIIFEDHFEHDHHHBFGAJCHFHDJIAIAGEFHAECCFGJADBEIBCFFFFCFIBGFEACEFF

[出力例]
519844312

[入力例]

BGBH

[出力例]

※AtCoderテストケースより

[入力例]

100

BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

[出力例]

330219020

※AtCoderテストケースより

[入力例]

ABABA

[出力例]

[入力例]

DIBFDECJCG

[出力例]

699

[入力例]

ABIFIJFGCJCABBAFFDIG

[出力例]

50479

[入力例]

ABCDEFGHIJABCDEEDCBAJIHGFEDCBA

[出力例]

1311156

[入力例]

500

ABCDEFGHIJFGADFEHBGCCBCFCCAABIBIFCDCHFCIAHDCGFIJIHCAEHBCADHBGGFBBFDGHECDBGGDDFDADDICEABCABBFFFEDAHAECFBBJFGEJFGAEACIGFIAACDEIHFJABFJBCDCCDEDFFFDAIBHCEFFIAJHDEBJBEFEDHIDHIBEIDDDFBCBIDDIAJEGBEBJGIAFDGCJGHHCBDIEHGJCBAEEIIHGEGBGJEIECGBGIEADABEJDCHDFHBHBHFBJFFBIAFBJJCJHJCJDDICHCGFCIHBAFJDIFJHFGJCCIHAJEBGHFFEFHADGIHCAJBHHHCHHDEIAFICHECGHIIIFJHACHJCEAECJDDHICJGDIDAAIGECJFCGCCCIBJBBAGGACBEBAGIEBGCEJCCEIGGEEAEICFFDECHCDBEEHEADDEDGACHDEGFCGEBADIIFEDHFEHDHHHBFGAJCHFHDJIAIAGEFHAECCFGJADBEIBCFFFFCFIBGFEACEFF

[出力例]

519844312

■参照サイト
AtCoder Beginner Contest 215

2023年1月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 282 の問題E (Choose Two and Eat One) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc282/editorial/5398
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vl = vector<LL>;
using T3 = tuple<LL, 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 all(x) x.begin(), x.end()

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

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    LL M;
    scanf("%d %lld", &N, &M);
    vl a(N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 辺情報.
    vector<T3> t;
    rep(u, N) repx(v, u + 1, N) t.emplace_back((mPow(a[u], a[v], M) + mPow(a[v], a[u], M)) % M, u, v);
    
    // 3. sort.
    // -> 最大全域木 を 構築するため, 降順で並び替える.
    sort(all(t));
    reverse(all(t));
    
    // 4. 最大全域木.
    // -> 最小全域木(Kruskal's Algorithm) の アルゴリズム を 流用.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    UnionFind uf(N + 2);
    LL ans = 0;
    rep(i, t.size()){
        // 4-1. グラフ情報.
        int u = get<1>(t[i]);
        int v = get<2>(t[i]);
        LL cost = get<0>(t[i]);
        
        // 4-2. 辺 を 追加.
        if(!uf.same(u, v)){
            uf.unite(u, v);
            ans += cost;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/abc282/editorial/5398

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vl = vector<LL>;

using T3 = tuple<LL, 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 all(x) x.begin(), x.end()

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

// -> 引数 MOD は, 素数と限らないので, 逆元の計算には, 使用しない.

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

// @param b: 指数.

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

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

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t;

}

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N;

LL M;

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

vl a(N);

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

// 2. 辺情報.

vector<T3> t;

rep(u, N) repx(v, u + 1, N) t.emplace_back((mPow(a[u], a[v], M) + mPow(a[v], a[u], M)) % M, u, v);

// 3. sort.

// -> 最大全域木を構築するため, 降順で並び替える.

sort(all(t));

reverse(all(t));

// 4. 最大全域木.

// -> 最小全域木(Kruskal's Algorithm) のアルゴリズムを流用.

// 競プロ典型 90 問 (049 - Flip Digits 2)

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp

UnionFind uf(N + 2);

LL ans = 0;

rep(i, t.size()){

// 4-1. グラフ情報.

int u = get<1>(t[i]);

int v = get<2>(t[i]);

LL cost = get<0>(t[i]);

// 4-2. 辺を追加.

if(!uf.same(u, v)){

uf.unite(u, v);

ans += cost;

}

// 5. 出力.

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

return 0;

}

[入力例]
4 10
4 2 3 2

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

[入力例]
20 100
29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8

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

[入力例]
5 25
7 24 17 12 3

[出力例]
60

[入力例]
20 2023
877 1532 1740 388 462 252 1299 421 841 1235 994 1761 639 868 560 632 1042 1265 314 671

[出力例]
36147

[入力例]
200 20230113
18581675 4274380 17829716 12271757 16916200 1801487 19665242 5334036 4149560 15459494 15009176 13960748 17980544 7812492 6551123 16646042 4931704 15515582 664316 13659957 13248666 16041711 1175879 6251446 1765631 11159012 4595851 19069927 16750999 15386170 15261501 17331674 13525451 2537306 9130297 6746448 5611532 19698071 3756218 16877032 13992225 2580209 18423027 12538584 1432012 8446157 2422875 15411158 15178100 16045055 10960697 5312125 18010947 16866996 19069532 5673025 13311148 9928007 10637002 3927509 10616580 7472782 10241197 5355881 4791590 1741882 13050504 16134873 794851 10155052 19085692 15259444 18497994 16237086 12574864 904170 17500959 17751459 16908642 10401729 19386260 15502160 11247117 6231333 13477170 725403 11788249 5343633 9634343 19517803 18302876 6091777 16251194 6956039 11047990 13970323 13658944 7773722 5159731 11256668 1910547 13838026 16677238 1059524 15208750 20132229 19088533 11249240 16513896 4838707 5282521 3498958 6440002 12747410 11606399 5363413 16472850 6482823 4871440 13118149 18764972 11846496 14760037 16155126 13472131 5684766 1097515 9962678 9855707 11379308 17577264 2261296 7262536 9544603 17909797 4991889 19637396 9794908 8014022 17119197 15241735 9608467 20002119 13530795 8052363 14067583 3304908 8033144 9290093 10359397 5951141 15090209 1115963 16137160 12718867 18909523 9630118 10792540 6057036 10400061 897345 14155403 12196582 17996942 8863261 18423454 2684276 13130763 8531789 6656673 2288890 5587375 8044163 4316572 3282614 13257153 19098256 16295289 10977860 9649381 13672792 10120501 7639862 5445919 19413562 1048660 19782177 16185142 18790452 3909213 12116149 18583901 10285888 996135 7594577 13815619 9946295 13640951 13048670 14564381

[出力例]
3998446571

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

[出力例]
10221

[入力例]

4 10

4 2 3 2

[出力例]

※AtCoderテストケースより

[入力例]

20 100

29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8

[出力例]

1733

※AtCoderテストケースより

[入力例]

5 25

7 24 17 12 3

[出力例]

[入力例]

20 2023

877 1532 1740 388 462 252 1299 421 841 1235 994 1761 639 868 560 632 1042 1265 314 671

[出力例]

36147

[入力例]

200 20230113

18581675 4274380 17829716 12271757 16916200 1801487 19665242 5334036 4149560 15459494 15009176 13960748 17980544 7812492 6551123 16646042 4931704 15515582 664316 13659957 13248666 16041711 1175879 6251446 1765631 11159012 4595851 19069927 16750999 15386170 15261501 17331674 13525451 2537306 9130297 6746448 5611532 19698071 3756218 16877032 13992225 2580209 18423027 12538584 1432012 8446157 2422875 15411158 15178100 16045055 10960697 5312125 18010947 16866996 19069532 5673025 13311148 9928007 10637002 3927509 10616580 7472782 10241197 5355881 4791590 1741882 13050504 16134873 794851 10155052 19085692 15259444 18497994 16237086 12574864 904170 17500959 17751459 16908642 10401729 19386260 15502160 11247117 6231333 13477170 725403 11788249 5343633 9634343 19517803 18302876 6091777 16251194 6956039 11047990 13970323 13658944 7773722 5159731 11256668 1910547 13838026 16677238 1059524 15208750 20132229 19088533 11249240 16513896 4838707 5282521 3498958 6440002 12747410 11606399 5363413 16472850 6482823 4871440 13118149 18764972 11846496 14760037 16155126 13472131 5684766 1097515 9962678 9855707 11379308 17577264 2261296 7262536 9544603 17909797 4991889 19637396 9794908 8014022 17119197 15241735 9608467 20002119 13530795 8052363 14067583 3304908 8033144 9290093 10359397 5951141 15090209 1115963 16137160 12718867 18909523 9630118 10792540 6057036 10400061 897345 14155403 12196582 17996942 8863261 18423454 2684276 13130763 8531789 6656673 2288890 5587375 8044163 4316572 3282614 13257153 19098256 16295289 10977860 9649381 13672792 10120501 7639862 5445919 19413562 1048660 19782177 16185142 18790452 3909213 12116149 18583901 10285888 996135 7594577 13815619 9946295 13640951 13048670 14564381

[出力例]

3998446571

[入力例]

500 23

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

[出力例]

10221

■参照サイト
HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)

2023年1月8日

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

C++の練習を兼ねて, AtCoder Beginner Contest 282 の問題C (String Delimiter) ～問題D (Make Bipartite 2) を解いてみた.

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

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

■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--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    char c[202020];
    scanf("%d %s", &N, c);
    string S(c);
    
    // 2. 文字列作成.
    string ans;
    bool f = false;
    rep(i, N){
        if(S[i] == ','){
            ans.pb(f ? ',' : '.');
            continue;
        }
        if(S[i] == '"') f = !f;
        ans.pb(S[i]);
    }
    
    // 3. 出力.
    printf("%s\n", ans.c_str());
    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--)

#define pb push_back

int main(){

// 1. 入力情報.

int N;

char c[202020];

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

string S(c);

// 2. 文字列作成.

string ans;

bool f = false;

rep(i, N){

if(S[i] == ','){

ans.pb(f ? ',' : '.');

continue;

}

if(S[i] == '"') f = !f;

ans.pb(S[i]);

}

// 3. 出力.

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

return 0;

}

[入力例]
8
"a,b"c,d

[出力例]
"a,b"c.d
※AtCoderテストケースより

[入力例]
5
,,,,,

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

[入力例]
20
a,"t,"c,"o,"d,"e,"r,

[出力例]
a."t,"c."o,"d."e,"r.
※AtCoderテストケースより

[入力例]
45
"s,t,"r,"i,n,"g,"d","e,""l,i,m",i,"""t,e,"r""

[出力例]
"s,t,"r."i,n,"g."d"."e,""l,i,m".i."""t,e,"r""

[入力例]
70
""a,","aa,","aaa,","aaaa,","aaaaa,","aaaaaa,","aaaaaaa,","aaaaaaaa,","

[出力例]
""a.","aa.","aaa.","aaaa.","aaaaa.","aaaaaa.","aaaaaaa.","aaaaaaaa.","

[入力例]

"a,b"c,d

[出力例]

"a,b"c.d

※AtCoderテストケースより

[入力例]

,,,,,

[出力例]

.....

※AtCoderテストケースより

[入力例]

a,"t,"c,"o,"d,"e,"r,

[出力例]

a."t,"c."o,"d."e,"r.

※AtCoderテストケースより

[入力例]

"s,t,"r,"i,n,"g,"d","e,""l,i,m",i,"""t,e,"r""

[出力例]

"s,t,"r."i,n,"g."d"."e,""l,i,m".i."""t,e,"r""

[入力例]

""a,","aa,","aaa,","aaaa,","aaaaa,","aaaaaa,","aaaaaaa,","aaaaaaaa,","

[出力例]

""a.","aa.","aaa.","aaaa.","aaaaa.","aaaaaa.","aaaaaaa.","aaaaaaaa.","

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    };
    int c[N], n = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++n);
    
    // 3. 連結成分ごとのグラフ.
    vvi CG(n + 1);
    rep(i, N) CG[c[i] - 1].pb(i);
    
    // 4. 二部グラフ判定・集計.
    // -> 各連結成分が, 二部グラフとなる必要があるはず.
    bool isBipartite = true;
    LL ans = 0;
    rep(i, n){
        // 4-1. 座標圧縮.
        map<int, int> m;
        set<int> st;
        for(auto &p : CG[i]) m[p] = 0, st.insert(p);
        int idx = -1;
        for(auto &p : m) p.b = ++idx;
        
        // 4-2. 最短距離.
        // -> 頂点番号 を 座標圧縮したので, bfsは, ここに埋め込んだ.
        int d[idx + 1];
        rep(j, idx + 1) d[j] = -1;
        queue<int> q;
        int s = CG[i][0];
        d[m[s]] = 0;
        q.push(s);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(auto &v : G[u]) if(st.count(v) && d[m[v]] == -1 && v != s) d[m[v]] = d[m[u]] + 1, q.push(v);
        }
        
        // 4-3. 距離の偶奇.
        LL e = 0, o = 0;
        rep(j, idx + 1){
            if(d[j] & 1) ++o;
            else         ++e;
        }
        
        // 4-4. 二部グラフか？
        LL t = 0;
        for(auto &p : CG[i]){
            LL c = 0;
            for(auto &q : G[p]){
                // 距離の偶奇が同じ場合は, 矛盾.
                if((d[m[q]] & 1) == (d[m[p]] & 1)) isBipartite = false;
                
                // 距離の偶奇が異なるものをカウント.
                if((d[m[q]] & 1) != (d[m[p]] & 1)) ++c;
            }
            
            // 隣接頂点どうしは, 辺が存在しているので除外.
            t += (d[m[p]] & 1) ? (e - c) : (o - c);
        }
        
        // 4-5. 加算.
        ans += (LL)(idx + 1) * (LL)(N - idx - 1);
        ans += t;
    }
    
    // 5. 出力.
    printf("%lld\n", isBipartite ? ans / 2 : 0);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

rep(i, M){

int u, v;

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

--u;

--v;

G[u].pb(v);

G[v].pb(u);

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

int c[N], n = 0;

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

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

// 3. 連結成分ごとのグラフ.

vvi CG(n + 1);

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

// 4. 二部グラフ判定・集計.

// -> 各連結成分が, 二部グラフとなる必要があるはず.

bool isBipartite = true;

LL ans = 0;

rep(i, n){

// 4-1. 座標圧縮.

map<int, int> m;

set<int> st;

for(auto &p : CG[i]) m[p] = 0, st.insert(p);

int idx = -1;

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

// 4-2. 最短距離.

// -> 頂点番号を座標圧縮したので, bfsは, ここに埋め込んだ.

int d[idx + 1];

rep(j, idx + 1) d[j] = -1;

queue<int> q;

int s = CG[i][0];

d[m[s]] = 0;

q.push(s);

while(!q.empty()){

int u = q.front();

q.pop();

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

}

// 4-3. 距離の偶奇.

LL e = 0, o = 0;

rep(j, idx + 1){

if(d[j] & 1) ++o;

else ++e;

}

// 4-4. 二部グラフか？

LL t = 0;

for(auto &p : CG[i]){

LL c = 0;

for(auto &q : G[p]){

// 距離の偶奇が同じ場合は, 矛盾.

if((d[m[q]] & 1) == (d[m[p]] & 1)) isBipartite = false;

// 距離の偶奇が異なるものをカウント.

if((d[m[q]] & 1) != (d[m[p]] & 1)) ++c;

}

// 隣接頂点どうしは, 辺が存在しているので除外.

t += (d[m[p]] & 1) ? (e - c) : (o - c);

}

// 4-5. 加算.

ans += (LL)(idx + 1) * (LL)(N - idx - 1);

ans += t;

}

// 5. 出力.

printf("%lld\n", isBipartite ? ans / 2 : 0);

return 0;

}

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

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

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

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

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

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

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

[出力例]
15

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

[出力例]
97

[入力例]
12 8
5 6
6 8
5 7
7 8
9 10
10 11
12 11
12 9

[出力例]
54

[入力例]
23 18
1 2
1 9
3 2
11 3
10 9
11 10
13 14
15 14
13 12
15 12
16 18
16 17
17 20
16 21
22 21
19 18
23 19
22 18

[出力例]
215

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

[出力例]
361

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

[入力例]

5 4

4 2

3 1

5 2

3 2

[出力例]

※AtCoderテストケースより

[入力例]

4 3

3 1

3 2

1 2

[出力例]

※AtCoderテストケースより

[入力例]

9 11

4 9

9 1

8 2

8 3

9 2

8 4

6 7

4 6

7 5

4 5

7 8

[出力例]

※AtCoderテストケースより

[入力例]

10 10

1 2

8 1

2 3

9 3

9 10

3 4

5 4

5 6

7 6

5 8

[出力例]

[入力例]

19 18

1 2

1 3

1 7

1 8

7 15

8 15

2 4

5 3

4 6

6 5

6 12

13 6

14 12

14 13

14 16

14 17

18 16

19 17

[出力例]

[入力例]

12 8

5 6

6 8

5 7

7 8

9 10

10 11

12 11

12 9

[出力例]

[入力例]

23 18

1 2

1 9

3 2

11 3

10 9

11 10

13 14

15 14

13 12

15 12

16 18

16 17

17 20

16 21

22 21

19 18

23 19

22 18

[出力例]

215

[入力例]

30 27

4 5

7 5

6 5

8 9

8 11

11 10

10 9

12 13

15 13

16 12

17 16

17 14

15 14

18 19

19 20

21 20

21 18

22 21

23 22

24 23

27 24

26 24

29 24

28 27

27 25

26 25

30 25

[出力例]

361

■参照サイト
HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)

2023年1月6日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc281/editorial/5367
// 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);
    vi a(N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, int m, vi& ca, int d) -> int {
        // 終了条件.
        if(!ca.size() || d == -1) return m;
        
        // d 桁目.
        vi s, t;
        for(auto &p : ca){
            if(p & (1 << d)) t.pb(p);
            else             s.pb(p);
        }
        
        // 集合 S が 空(d 桁目は, 0).
        if(!s.size()) return self(self, m, t, d - 1);
        
        // 集合 T が 空(d 桁目は, 0).
        if(!t.size()) return self(self, m, s, d - 1);
        
        // 集合 S, T が 空でない(d 桁目は, 1).
        return min(self(self, m + (1 << d), t, d - 1), self(self, m + (1 << d), s, d - 1));
    };
    
    // 3. 出力.
    printf("%d\n", dfs(dfs, 0, a, 30));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc281/editorial/5367

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

vi a(N);

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

// 2. dfs.

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

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

// 終了条件.

if(!ca.size() || d == -1) return m;

// d 桁目.

vi s, t;

for(auto &p : ca){

if(p & (1 << d)) t.pb(p);

else s.pb(p);

}

// 集合 S が空(d 桁目は, 0).

if(!s.size()) return self(self, m, t, d - 1);

// 集合 T が空(d 桁目は, 0).

if(!t.size()) return self(self, m, s, d - 1);

// 集合 S, T が空でない(d 桁目は, 1).

return min(self(self, m + (1 << d), t, d - 1), self(self, m + (1 << d), s, d - 1));

};

// 3. 出力.

printf("%d\n", dfs(dfs, 0, a, 30));

return 0;

}

[入力例]
3
12 18 11

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

[入力例]
10
0 0 0 0 0 0 0 0 0 0

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

[入力例]
5
324097321 555675086 304655177 991244276 9980291

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

[入力例]
5
10 7 3 13 2

[出力例]
12

[入力例]
8
10 9 13 15 4 3 8 5

[出力例]
12

[入力例]
10
70 61 15 88 105 18 33 121 36 79

[出力例]
112

[入力例]
50
6891 6298 5053 6323 6042 6655 5783 5991 7339 5310 7118 5565 5284 7006 6330 5662 5076 7133 6397 6750 6200 6016 5993 5313 5955 7260 6804 5918 6068 5399 5714 5000 6160 6415 6138 6541 6179 7152 6255 6404 5134 6886 5828 6079 5763 5596 5740 7161 5294 6549

[出力例]
3136

[入力例]
1000
983416 585352 1514003 1368537 628064 911914 852445 982631 1693264 1361091 737487 785615 781739 1185733 931554 1260586 563653 1285736 980567 1276610 542170 1077277 1114263 728838 616468 562931 1725756 1634694 672414 1060936 1292963 1177298 755917 1594473 707707 910290 948009 1325922 1221078 1479813 1294760 1172099 1641627 872866 1072574 1473997 1076895 1034100 744153 1262289 1533736 1324906 1038768 778896 1710597 1237965 855432 1488449 749075 825760 1081769 1727737 1143983 924439 908693 919781 1431951 741219 1076844 910410 879026 1183673 1392139 1477801 1328296 608659 1698782 733672 1591460 1609047 1700774 1673479 663875 910323 961351 898437 1290098 943939 570831 1519890 1510777 574038 1202544 822785 1678814 963797 1353459 608025 740323 1197190 1066108 1041366 1346662 759977 742769 1003010 1212186 691366 1487334 1207565 1623128 592368 1333753 808206 1147178 582467 1549749 1249085 1106388 1014022 1490996 719387 1687600 908056 966861 691388 853561 1436926 1357853 776927 1650304 627724 724605 1472979 878040 1729693 1567007 646237 522055 1003464 775690 917899 1634841 874818 793981 1128783 984634 1602266 1611244 1446130 1334701 1146127 761298 1114100 1709548 1154834 1399373 1344416 1098500 906520 916937 1452298 558143 1275907 1384928 1282163 940375 1393104 1119685 1708259 1091628 1649039 1421195 712586 1215532 1294831 981186 1203012 1710922 918264 1043072 1062496 1553728 1707387 1679920 932616 1527549 934318 502752 948819 614657 1722344 1143717 1410262 1309428 977796 1000454 900387 630260 715472 841628 523619 591036 1447406 1505193 680814 1595274 577501 1264036 1408642 1731624 881817 1113097 620604 1675387 1498398 1541302 610660 1281241 1568924 917296 1339673 1506762 1027640 1276060 625298 993041 1250344 1570929 926371 1339385 1027619 572102 792486 1721781 1180346 523433 1327957 501425 1674301 1594504 1052839 886843 1176682 1379631 599408 567522 1475706 977058 871550 834591 1524172 1074068 831014 1062927 842688 1458822 999255 515184 1581908 1147764 1001192 1587982 1148463 1219656 1187186 1255179 1724131 636036 609462 756729 913071 1242734 977876 1689974 885843 1417044 1272653 610327 765544 1207198 1065033 1273496 1500218 1258206 1166552 693238 707318 990762 1102785 589450 1024800 1390004 794298 1135495 1705148 1672313 896231 1010256 1013690 844637 1606162 1019861 1070515 1280961 932971 705239 1116011 1210134 603795 1569111 1031562 1313016 972400 981734 721353 1635394 1280633 904305 903156 945272 635857 1716128 1394821 1392790 835131 1615934 1484725 1037344 550375 1265608 1546394 1629639 1323872 1624597 1510289 1129836 1715819 882041 1648866 1315204 617024 1256136 1252701 855799 1009486 1260492 1717634 1579134 659884 535675 939980 1429725 1717878 558554 1453666 1666314 1181581 1457079 1652944 873479 1425264 1690676 848435 861744 1544194 994752 571427 1206999 1456648 1126576 1266595 1220349 935434 1351714 1485038 843940 1609479 1154589 604605 1078542 527303 1208152 1297267 1004356 1515926 663932 1464629 1622408 1353081 1686717 1272569 553734 1556424 1516071 1077974 1419726 1253948 1148411 1338586 1146172 1241036 1459069 1205731 627951 716508 723100 1314254 994886 1282887 1705678 1393108 1712077 1400576 923026 547291 1308835 923502 663368 1016911 1607411 1281784 510744 1281018 542960 1070778 921364 1606321 1703870 1249787 1564831 1360999 1344476 1488401 1201755 950602 1731818 504664 953870 793182 1172900 1582618 728804 1145571 1273063 919016 1047802 1342517 683145 602870 1648276 1622501 1380991 1693277 1559236 560074 1141852 1133747 854384 1402464 1080471 1703957 1668638 644370 1204166 714414 1358206 1027715 1203036 946434 846699 1664249 1042485 1716155 1725165 1220274 1713856 873869 1046990 1624218 776288 973149 1366109 675323 654288 1188632 976038 561180 1338607 1363684 1502732 1031369 1384732 815055 580376 1374545 1571458 1395377 1170260 1070661 694816 683679 561746 1470475 1281386 1147188 1276962 815414 1179335 1361202 1388800 1054392 1564174 1111506 987868 1503420 1711851 1507373 1425868 1641098 570810 1373541 1211831 511029 972173 610840 1346426 1714863 1251497 1198761 1259705 1205714 1689021 1364924 960307 563469 1586400 1049348 1185988 1100514 902613 1610018 1602541 871195 1150976 977318 1605422 919835 1447884 1363822 596255 978564 1401498 1461780 1151317 1034731 1073149 1246885 937200 1704507 803548 1049859 831794 1469033 1211419 678577 1140500 1722756 1576530 590983 1211337 649674 1304078 846537 1279153 1353718 1040815 1683899 584310 971484 550199 1159031 1621576 997678 1507425 1314612 979439 1031653 995345 1030310 800904 595315 1048013 758614 1235269 836843 1455995 880259 755557 1033347 1124065 561549 903641 1609012 520943 847622 1240910 670344 1314795 1303247 596642 1177203 1417615 1385613 1694898 721874 1546623 864539 1655304 842597 1371664 1269623 1080602 1672786 1354552 1370997 831302 1657300 1198714 819853 823261 1671340 1135290 1023759 1353563 1111549 654563 1219736 1481001 637716 521269 980577 596608 1692666 914248 1518911 993073 1120947 692604 1210341 1456407 725654 711496 1509963 788303 1636970 1693739 1410562 1578090 1607691 945239 524358 721613 639157 570785 798624 1139665 1041143 1343836 1402657 831744 876759 1307704 533915 1330382 1638454 1014884 763066 921486 1002392 1426872 901227 843700 855913 841840 1162783 1439559 502946 795389 1439145 1403450 1531124 1331720 1079256 1141823 1095810 1622052 1255064 1230648 1206913 879320 1255279 1328814 1362776 1274286 564183 1091989 1163016 1221343 821690 1675341 974480 1085842 528778 1062445 504281 694116 1221562 1642195 646713 1268695 1555056 1527589 622656 1639675 950740 1078952 906810 1170825 1398173 916149 1067253 1136941 1585320 1076647 883699 602136 824728 1246107 644715 1238566 1270928 1322168 950555 879013 1467174 703100 1492807 525589 1451229 536602 1450200 1053052 677285 1591185 756736 1164696 1273902 972771 1269924 591397 1143897 1070464 933373 1311806 1570453 1237401 865829 1157795 1134854 1650980 1397561 1616694 611675 804661 1309608 1569280 550408 1422570 1692747 1727110 1561091 613442 1229872 748854 1098317 894614 1692991 895103 1457213 1454880 841646 598728 906285 1143390 1576522 1662076 1071330 844800 725503 1638394 1373735 1636011 1668504 1303964 1370633 1521229 885664 820561 1350174 1015327 1162501 1199324 512182 543616 824980 837269 1118544 643917 506402 592923 1442628 1681434 747823 875423 534858 1613138 1733817 599331 614533 1461844 971387 1500765 662700 599283 1686085 588158 1725375 804693 843414 844685 1162893 1726029 1353942 970714 1139888 697280 695339 1341836 1437968 1659257 1458117 1703316 1062947 1336929 560650 1561283 1348394 523360 968698 1362091 680834 1246187 1343243 1688697 1517121 660823 1422364 1353592 1216435 1482240 1376711 906090 1705903 523046 1328303 863702 1275263 540667 556225 673730 1567224 546413 1377102 617703 800422 1418411 1719871 857171 1353932 521768 695589 892808 753489 999977 746917 824074 1065473 984510 765495 1082287 1631085 1716669 510416 1285702 1373783 1492096 1423294 867459 1178875 1512610 1255379 1635278 1303548 1065347 703908 1089724 1050720 725155 530081 1677577 879378 637441 1231246 828087 1610890 1469629 1051717 774936 1312291 1540137 850489 597006 1031149 631009 1430909 587877 1122854 1398058 930432 1684843 1038739 1577539 1167758 992667 1397756 1695939 1190678 555017 656652 590666 1561242 548326 1581106 536742 1551651 959458 1689673 1466760 1026859 1193359 1420273 1627861 1094225 708273 766875 1501004 1072155 1311448 608528 1667118 1178100 1583931 873651 967958 589671 684109 1295141 1487741 913334 1395806 1098559 1359309 561207 930174 739629 872796 1188656 1487772 1686236 1145892 1087539 672334 1503400 1377209 1197106 889942 1150368 1545105 1165920

[出力例]
1595392

[入力例]

12 18 11

[出力例]

※AtCoderテストケースより

[入力例]

0 0 0 0 0 0 0 0 0 0

[出力例]

※AtCoderテストケースより

[入力例]

324097321 555675086 304655177 991244276 9980291

[出力例]

805306368

※AtCoderテストケースより

[入力例]

10 7 3 13 2

[出力例]

[入力例]

10 9 13 15 4 3 8 5

[出力例]

[入力例]

70 61 15 88 105 18 33 121 36 79

[出力例]

112

[入力例]

6891 6298 5053 6323 6042 6655 5783 5991 7339 5310 7118 5565 5284 7006 6330 5662 5076 7133 6397 6750 6200 6016 5993 5313 5955 7260 6804 5918 6068 5399 5714 5000 6160 6415 6138 6541 6179 7152 6255 6404 5134 6886 5828 6079 5763 5596 5740 7161 5294 6549

[出力例]

3136

[入力例]

1000

983416 585352 1514003 1368537 628064 911914 852445 982631 1693264 1361091 737487 785615 781739 1185733 931554 1260586 563653 1285736 980567 1276610 542170 1077277 1114263 728838 616468 562931 1725756 1634694 672414 1060936 1292963 1177298 755917 1594473 707707 910290 948009 1325922 1221078 1479813 1294760 1172099 1641627 872866 1072574 1473997 1076895 1034100 744153 1262289 1533736 1324906 1038768 778896 1710597 1237965 855432 1488449 749075 825760 1081769 1727737 1143983 924439 908693 919781 1431951 741219 1076844 910410 879026 1183673 1392139 1477801 1328296 608659 1698782 733672 1591460 1609047 1700774 1673479 663875 910323 961351 898437 1290098 943939 570831 1519890 1510777 574038 1202544 822785 1678814 963797 1353459 608025 740323 1197190 1066108 1041366 1346662 759977 742769 1003010 1212186 691366 1487334 1207565 1623128 592368 1333753 808206 1147178 582467 1549749 1249085 1106388 1014022 1490996 719387 1687600 908056 966861 691388 853561 1436926 1357853 776927 1650304 627724 724605 1472979 878040 1729693 1567007 646237 522055 1003464 775690 917899 1634841 874818 793981 1128783 984634 1602266 1611244 1446130 1334701 1146127 761298 1114100 1709548 1154834 1399373 1344416 1098500 906520 916937 1452298 558143 1275907 1384928 1282163 940375 1393104 1119685 1708259 1091628 1649039 1421195 712586 1215532 1294831 981186 1203012 1710922 918264 1043072 1062496 1553728 1707387 1679920 932616 1527549 934318 502752 948819 614657 1722344 1143717 1410262 1309428 977796 1000454 900387 630260 715472 841628 523619 591036 1447406 1505193 680814 1595274 577501 1264036 1408642 1731624 881817 1113097 620604 1675387 1498398 1541302 610660 1281241 1568924 917296 1339673 1506762 1027640 1276060 625298 993041 1250344 1570929 926371 1339385 1027619 572102 792486 1721781 1180346 523433 1327957 501425 1674301 1594504 1052839 886843 1176682 1379631 599408 567522 1475706 977058 871550 834591 1524172 1074068 831014 1062927 842688 1458822 999255 515184 1581908 1147764 1001192 1587982 1148463 1219656 1187186 1255179 1724131 636036 609462 756729 913071 1242734 977876 1689974 885843 1417044 1272653 610327 765544 1207198 1065033 1273496 1500218 1258206 1166552 693238 707318 990762 1102785 589450 1024800 1390004 794298 1135495 1705148 1672313 896231 1010256 1013690 844637 1606162 1019861 1070515 1280961 932971 705239 1116011 1210134 603795 1569111 1031562 1313016 972400 981734 721353 1635394 1280633 904305 903156 945272 635857 1716128 1394821 1392790 835131 1615934 1484725 1037344 550375 1265608 1546394 1629639 1323872 1624597 1510289 1129836 1715819 882041 1648866 1315204 617024 1256136 1252701 855799 1009486 1260492 1717634 1579134 659884 535675 939980 1429725 1717878 558554 1453666 1666314 1181581 1457079 1652944 873479 1425264 1690676 848435 861744 1544194 994752 571427 1206999 1456648 1126576 1266595 1220349 935434 1351714 1485038 843940 1609479 1154589 604605 1078542 527303 1208152 1297267 1004356 1515926 663932 1464629 1622408 1353081 1686717 1272569 553734 1556424 1516071 1077974 1419726 1253948 1148411 1338586 1146172 1241036 1459069 1205731 627951 716508 723100 1314254 994886 1282887 1705678 1393108 1712077 1400576 923026 547291 1308835 923502 663368 1016911 1607411 1281784 510744 1281018 542960 1070778 921364 1606321 1703870 1249787 1564831 1360999 1344476 1488401 1201755 950602 1731818 504664 953870 793182 1172900 1582618 728804 1145571 1273063 919016 1047802 1342517 683145 602870 1648276 1622501 1380991 1693277 1559236 560074 1141852 1133747 854384 1402464 1080471 1703957 1668638 644370 1204166 714414 1358206 1027715 1203036 946434 846699 1664249 1042485 1716155 1725165 1220274 1713856 873869 1046990 1624218 776288 973149 1366109 675323 654288 1188632 976038 561180 1338607 1363684 1502732 1031369 1384732 815055 580376 1374545 1571458 1395377 1170260 1070661 694816 683679 561746 1470475 1281386 1147188 1276962 815414 1179335 1361202 1388800 1054392 1564174 1111506 987868 1503420 1711851 1507373 1425868 1641098 570810 1373541 1211831 511029 972173 610840 1346426 1714863 1251497 1198761 1259705 1205714 1689021 1364924 960307 563469 1586400 1049348 1185988 1100514 902613 1610018 1602541 871195 1150976 977318 1605422 919835 1447884 1363822 596255 978564 1401498 1461780 1151317 1034731 1073149 1246885 937200 1704507 803548 1049859 831794 1469033 1211419 678577 1140500 1722756 1576530 590983 1211337 649674 1304078 846537 1279153 1353718 1040815 1683899 584310 971484 550199 1159031 1621576 997678 1507425 1314612 979439 1031653 995345 1030310 800904 595315 1048013 758614 1235269 836843 1455995 880259 755557 1033347 1124065 561549 903641 1609012 520943 847622 1240910 670344 1314795 1303247 596642 1177203 1417615 1385613 1694898 721874 1546623 864539 1655304 842597 1371664 1269623 1080602 1672786 1354552 1370997 831302 1657300 1198714 819853 823261 1671340 1135290 1023759 1353563 1111549 654563 1219736 1481001 637716 521269 980577 596608 1692666 914248 1518911 993073 1120947 692604 1210341 1456407 725654 711496 1509963 788303 1636970 1693739 1410562 1578090 1607691 945239 524358 721613 639157 570785 798624 1139665 1041143 1343836 1402657 831744 876759 1307704 533915 1330382 1638454 1014884 763066 921486 1002392 1426872 901227 843700 855913 841840 1162783 1439559 502946 795389 1439145 1403450 1531124 1331720 1079256 1141823 1095810 1622052 1255064 1230648 1206913 879320 1255279 1328814 1362776 1274286 564183 1091989 1163016 1221343 821690 1675341 974480 1085842 528778 1062445 504281 694116 1221562 1642195 646713 1268695 1555056 1527589 622656 1639675 950740 1078952 906810 1170825 1398173 916149 1067253 1136941 1585320 1076647 883699 602136 824728 1246107 644715 1238566 1270928 1322168 950555 879013 1467174 703100 1492807 525589 1451229 536602 1450200 1053052 677285 1591185 756736 1164696 1273902 972771 1269924 591397 1143897 1070464 933373 1311806 1570453 1237401 865829 1157795 1134854 1650980 1397561 1616694 611675 804661 1309608 1569280 550408 1422570 1692747 1727110 1561091 613442 1229872 748854 1098317 894614 1692991 895103 1457213 1454880 841646 598728 906285 1143390 1576522 1662076 1071330 844800 725503 1638394 1373735 1636011 1668504 1303964 1370633 1521229 885664 820561 1350174 1015327 1162501 1199324 512182 543616 824980 837269 1118544 643917 506402 592923 1442628 1681434 747823 875423 534858 1613138 1733817 599331 614533 1461844 971387 1500765 662700 599283 1686085 588158 1725375 804693 843414 844685 1162893 1726029 1353942 970714 1139888 697280 695339 1341836 1437968 1659257 1458117 1703316 1062947 1336929 560650 1561283 1348394 523360 968698 1362091 680834 1246187 1343243 1688697 1517121 660823 1422364 1353592 1216435 1482240 1376711 906090 1705903 523046 1328303 863702 1275263 540667 556225 673730 1567224 546413 1377102 617703 800422 1418411 1719871 857171 1353932 521768 695589 892808 753489 999977 746917 824074 1065473 984510 765495 1082287 1631085 1716669 510416 1285702 1373783 1492096 1423294 867459 1178875 1512610 1255379 1635278 1303548 1065347 703908 1089724 1050720 725155 530081 1677577 879378 637441 1231246 828087 1610890 1469629 1051717 774936 1312291 1540137 850489 597006 1031149 631009 1430909 587877 1122854 1398058 930432 1684843 1038739 1577539 1167758 992667 1397756 1695939 1190678 555017 656652 590666 1561242 548326 1581106 536742 1551651 959458 1689673 1466760 1026859 1193359 1420273 1627861 1094225 708273 766875 1501004 1072155 1311448 608528 1667118 1178100 1583931 873651 967958 589671 684109 1295141 1487741 913334 1395806 1098559 1359309 561207 930174 739629 872796 1188656 1487772 1686236 1145892 1087539 672334 1503400 1377209 1197106 889942 1150368 1545105 1165920

[出力例]

1595392

■参照サイト
AtCoder Beginner Contest 281

2023年1月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 283 の問題C (Cash Register) ～問題D (Scope) を解いてみた.

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

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

■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 main(){
    
    // 1. 入力情報.
    char c[101010];
    scanf("%s", c);
    string S(c);
    
    // 2. ボタンを押す.
    stack<char> st;
    rep(i, S.size()){
        if(S[i] == '0'){
            if(st.top() == '0'){
                st.pop();
                st.push('#');
                continue;
            }
        }
        st.push(S[i]);
    }
    
    // 3. 出力.
    printf("%d\n", st.size());
    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 main(){

// 1. 入力情報.

char c[101010];

scanf("%s", c);

string S(c);

// 2. ボタンを押す.

stack<char> st;

rep(i, S.size()){

if(S[i] == '0'){

if(st.top() == '0'){

st.pop();

st.push('#');

continue;

}

st.push(S[i]);

}

// 3. 出力.

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

return 0;

}

[入力例]
40004

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

[入力例]
1355506027

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

[入力例]
10888869450418352160768000001

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

[入力例]
1785105004847100897567100964501590001439902666470652249691970000320000013530000000104684273796321391

[出力例]
89

[入力例]
3571062473377399226311502600000000004301915504888668914316992165195828227931444705642124895663068311926000000000045054240336955075967197575737372788176327545435301343481345241930400000000009421146625064611409952999586750537613571473170559487379667436957194682515291381049498170415074585728548619029623111459050903296706318360442471650277945689265336393231890647416832135999417085001286323056038363992774314332727674699730405414802563066090000000000866425809637278257270595877511414783956600000000006513705678364730000000000000000000006721682052138160981567818812652480667750977332524210157085359151119180863279995486949119316605057712921127513633488207757937038381405125526774362717463841138969384644539053504898570082901128121542454435470000000000000000000008961478441788048944020670000000000000000000000000000000000000000004260844879853898339838378889786310200781205635085522107726531271268138964441207708723659787845717080809950000000000596393212314806635887079962930925464621301488711126874284000

[出力例]
925

[入力例]

40004

[出力例]

※AtCoderテストケースより

[入力例]

1355506027

[出力例]

※AtCoderテストケースより

[入力例]

10888869450418352160768000001

[出力例]

※AtCoderテストケースより

[入力例]

1785105004847100897567100964501590001439902666470652249691970000320000013530000000104684273796321391

[出力例]

[入力例]

3571062473377399226311502600000000004301915504888668914316992165195828227931444705642124895663068311926000000000045054240336955075967197575737372788176327545435301343481345241930400000000009421146625064611409952999586750537613571473170559487379667436957194682515291381049498170415074585728548619029623111459050903296706318360442471650277945689265336393231890647416832135999417085001286323056038363992774314332727674699730405414802563066090000000000866425809637278257270595877511414783956600000000006513705678364730000000000000000000006721682052138160981567818812652480667750977332524210157085359151119180863279995486949119316605057712921127513633488207757937038381405125526774362717463841138969384644539053504898570082901128121542454435470000000000000000000008961478441788048944020670000000000000000000000000000000000000000004260844879853898339838378889786310200781205635085522107726531271268138964441207708723659787845717080809950000000000596393212314806635887079962930925464621301488711126874284000

[出力例]

925

■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 main(){
    
    // 1. 入力情報.
    char c[303030];
    scanf("%s", c);
    string S(c);
    
    // 2. 操作.
    bool ok = true;
    stack<char> st;
    set<char> box;
    rep(i, S.size()){
        // 英小文字.
        if(S[i] >= 'a' && S[i] <= 'z'){
            // ボールが既に箱に入っているか？
            if(box.count(S[i])){
                ok = false;
                break;
            }
            
            // ボールを箱に追加.
            box.insert(S[i]);
            st.push(S[i]);
        }
        
        // 左括弧.
        if(S[i] == '(') st.push(S[i]);
        
        // 右括弧.
        if(S[i] == ')'){
            while(1){
                char b = st.top();
                if(b != '('){
                    // ボールを箱から取り出す.
                    st.pop();
                    box.erase(b);
                }else{
                    break;
                }
            }
            st.pop();
        }
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "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 main(){

// 1. 入力情報.

char c[303030];

scanf("%s", c);

string S(c);

// 2. 操作.

bool ok = true;

stack<char> st;

set<char> box;

rep(i, S.size()){

// 英小文字.

if(S[i] >= 'a' && S[i] <= 'z'){

// ボールが既に箱に入っているか？

if(box.count(S[i])){

ok = false;

break;

}

// ボールを箱に追加.

box.insert(S[i]);

st.push(S[i]);

}

// 左括弧.

if(S[i] == '(') st.push(S[i]);

// 右括弧.

if(S[i] == ')'){

while(1){

char b = st.top();

if(b != '('){

// ボールを箱から取り出す.

st.pop();

box.erase(b);

}else{

break;

}

st.pop();

}

// 3. 出力.

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

return 0;

}

[入力例]
((a)ba)

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

[入力例]
(a(ba))

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

[入力例]
(((())))

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

[入力例]
abca

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

[入力例]
(ab)b(bc)c(ca)

[出力例]
No

[入力例]
(ab)b(ca)c(a)a

[出力例]
Yes

[入力例]
(a(bc)b(cd)c(de))(a(bc)b(cd)c(de))(a(bc)b(cd)c(de))

[出力例]
Yes

[入力例]

((a)ba)

[出力例]

Yes

※AtCoderテストケースより

[入力例]

(a(ba))

[出力例]

※AtCoderテストケースより

[入力例]

(((())))

[出力例]

Yes

※AtCoderテストケースより

[入力例]

abca

[出力例]

※AtCoderテストケースより

[入力例]

(ab)b(bc)c(ca)

[出力例]

[入力例]

(ab)b(ca)c(a)a

[出力例]

Yes

[入力例]

(a(bc)b(cd)c(de))(a(bc)b(cd)c(de))(a(bc)b(cd)c(de))

[出力例]

Yes

■参照サイト
ユニークビジョンプログラミングコンテスト2022 冬(AtCoder Beginner Contest 283)

2023年1月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 281 の問題E (Least Elements) を解いてみた.

■感想.
1. 問題E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 実装に苦労したものの, std::multiset の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題E／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--)
LL a[202020];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 先頭 の (M - 1) 項.
    multiset<LL> lMst, rMst;
    rep(i, M - 1){
        lMst.insert(a[i]);
        if(lMst.size() > K){
            auto e = (--lMst.end());
            rMst.insert(*e);
            lMst.erase(lMst.find(*e));
        }
    }
    LL ans = 0;
    for(auto &x : lMst) ans += x;
    
    // 3. クエリ回答.
    repx(i, M - 1, N){
        // 3-1. a[i - M] の 処理.
        if(i - M >= 0){
            if(lMst.find(a[i - M]) != lMst.end()){
                ans -= a[i - M];
                lMst.erase(lMst.find(a[i - M]));
            }else{
                rMst.erase(rMst.find(a[i - M]));
            }
        }
        
        // 3-2. a[i] の 処理.
        rMst.insert(a[i]);
        if(lMst.size() < K){
            auto s = rMst.begin();
            ans += *s;
            lMst.insert(*s);
            rMst.erase(rMst.find(*s));
        }else{
            auto s = rMst.begin();
            auto e = (--lMst.end());
            if(*e > *s){
                ans += *s;
                lMst.insert(*s);
                rMst.erase(rMst.find(*s));
                ans -= *e;
                rMst.insert(*e);
                lMst.erase(lMst.find(*e));
            }
        }
        
        // 3-3. 出力.
        printf("%lld%s", ans, (i < N - 1) ? " " : "\n");
    }
    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--)

LL a[202020];

int main(){

// 1. 入力情報.

int N, M, K;

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

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

// 2. 先頭の (M - 1) 項.

multiset<LL> lMst, rMst;

rep(i, M - 1){

lMst.insert(a[i]);

if(lMst.size() > K){

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

rMst.insert(*e);

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

}

LL ans = 0;

for(auto &x : lMst) ans += x;

// 3. クエリ回答.

repx(i, M - 1, N){

// 3-1. a[i - M] の処理.

if(i - M >= 0){

if(lMst.find(a[i - M]) != lMst.end()){

ans -= a[i - M];

lMst.erase(lMst.find(a[i - M]));

}else{

rMst.erase(rMst.find(a[i - M]));

}

// 3-2. a[i] の処理.

rMst.insert(a[i]);

if(lMst.size() < K){

auto s = rMst.begin();

ans += *s;

lMst.insert(*s);

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

}else{

auto s = rMst.begin();

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

if(*e > *s){

ans += *s;

lMst.insert(*s);

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

ans -= *e;

rMst.insert(*e);

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

}

// 3-3. 出力.

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

}

return 0;

}

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

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

[入力例]
10 6 3
12 2 17 11 19 8 4 3 6 20

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

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

[出力例]
3 3 3

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

[出力例]
6 7 6 5 6

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

[出力例]
6 9 10 9 6 5

[入力例]
50 10 7
76 105 111 38 82 122 7 110 61 90 39 111 113 8 109 110 15 117 5 111 110 115 5 13 34 111 111 39 121 73 110 36 111 61 83 116 111 5 110 89 93 111 2 110 62 75 72 5 5 79

[出力例]
459 422 427 427 397 424 424 432 432 376 397 468 468 362 367 292 293 389 317 423 385 385 310 416 464 513 513 513 479 478 494 477 552 443 492 471 436 398 398 310 300

[入力例]
100 12 5
111 222 333 2023 785 147 724 1215 2023 103 712 103 111 270 111 906 196 567 777 809 196 111 621 753 1010 717 761 57 811 570 177 1183 103 555 748 1065 585 999 377 1173 285 624 187 2023 876 287 210 175 792 256 141 1133 59 1225 945 478 729 115 53 286 777 111 2023 103 2023 715 2023 335 111 1 103 1200 65 493 71 604 650 90 103 19 111 111 1123 111 103 1210 1025 110 689 191 750 2023 1124 515 888 1219 200 2023 103 126

[出力例]
686 686 734 575 575 575 624 624 624 624 632 632 725 884 1181 1691 1127 1552 1555 1111 1111 1018 1462 1462 1462 1462 1462 1269 1782 1497 1497 1507 1507 1989 1721 1346 1144 1144 1113 969 969 772 772 841 841 841 700 543 624 624 479 624 441 668 668 668 668 493 379 429 429 383 383 343 351 351 330 330 246 246 348 348 348 386 386 426 425 425 446 454 546 626 1030 1030 1608 1705 1705 1119 1135

[入力例]

6 4 3

3 1 4 1 5 9

[出力例]

5 6 10

※AtCoderテストケースより

[入力例]

10 6 3

12 2 17 11 19 8 4 3 6 20

[出力例]

21 14 15 13 13

※AtCoderテストケースより

[入力例]

5 3 3

1 1 1 1 1

[出力例]

3 3 3

[入力例]

7 3 3

1 2 3 2 1 2 3

[出力例]

6 7 6 5 6

[入力例]

10 5 3

1 2 3 4 5 4 3 2 1 2

[出力例]

6 9 10 9 6 5

[入力例]

50 10 7

76 105 111 38 82 122 7 110 61 90 39 111 113 8 109 110 15 117 5 111 110 115 5 13 34 111 111 39 121 73 110 36 111 61 83 116 111 5 110 89 93 111 2 110 62 75 72 5 5 79

[出力例]

459 422 427 427 397 424 424 432 432 376 397 468 468 362 367 292 293 389 317 423 385 385 310 416 464 513 513 513 479 478 494 477 552 443 492 471 436 398 398 310 300

[入力例]

100 12 5

111 222 333 2023 785 147 724 1215 2023 103 712 103 111 270 111 906 196 567 777 809 196 111 621 753 1010 717 761 57 811 570 177 1183 103 555 748 1065 585 999 377 1173 285 624 187 2023 876 287 210 175 792 256 141 1133 59 1225 945 478 729 115 53 286 777 111 2023 103 2023 715 2023 335 111 1 103 1200 65 493 71 604 650 90 103 19 111 111 1123 111 103 1210 1025 110 689 191 750 2023 1124 515 888 1219 200 2023 103 126

[出力例]

686 686 734 575 575 575 624 624 624 624 632 632 725 884 1181 1691 1127 1552 1555 1111 1111 1018 1462 1462 1462 1462 1462 1269 1782 1497 1497 1507 1507 1989 1721 1346 1144 1144 1113 969 969 772 772 841 841 841 700 543 624 624 479 624 441 668 668 668 668 493 379 429 429 383 383 343 351 351 330 330 246 246 348 348 348 386 386 426 425 425 446 454 546 626 1030 1030 1608 1705 1705 1119 1135

■参照サイト
AtCoder Beginner Contest 281

2023年1月2日

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

C++の練習を兼ねて, AtCoder Beginner Contest 281 の問題C (Circular Playlist) ～問題D (Max Multiple) を解いてみた.

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

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

■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--)
LL a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL T, total = 0;
    scanf("%d %lld", &N, &T);
    rep(i, N){
        scanf("%lld", &a[i]);
        total += a[i];
    }
    
    // 2. T秒後に流れている曲は？
    LL r = T % total;
    int idx = 0;
    rep(i, N){
        if(r < a[i]){
            idx = i + 1;
            break;
        }
        r -= a[i];
    }
    
    // 3. 出力.
    printf("%d %lld\n", idx, r);
    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--)

LL a[101010];

int main(){

// 1. 入力情報.

int N;

LL T, total = 0;

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

rep(i, N){

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

total += a[i];

}

// 2. T秒後に流れている曲は？

LL r = T % total;

int idx = 0;

rep(i, N){

if(r < a[i]){

idx = i + 1;

break;

}

r -= a[i];

}

// 3. 出力.

printf("%d %lld\n", idx, r);

return 0;

}

[入力例]
3 600
180 240 120

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

[入力例]
3 281
94 94 94

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

[入力例]
10 5678912340
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

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

[入力例]
10 2023
25 123 87 51 12 46 18 118 21 113

[出力例]
3 33

[入力例]
20 20230102
1212 793 583 123 645 140 800 753 650 1020 1024 357 844 500 987 1145 960 1136 524 1137

[出力例]
10 176

[入力例]

3 600

180 240 120

[出力例]

1 60

※AtCoderテストケースより

[入力例]

3 281

94 94 94

[出力例]

3 93

※AtCoderテストケースより

[入力例]

10 5678912340

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

[出力例]

6 678912340

※AtCoderテストケースより

[入力例]

10 2023

25 123 87 51 12 46 18 118 21 113

[出力例]

3 33

[入力例]

20 20230102

1212 793 583 123 645 140 800 753 650 1020 1024 357 844 500 987 1145 960 1136 524 1137

[出力例]

10 176

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

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

int main(){
    
    // 1. 入力情報.
    int N, K, D;
    scanf("%d %d %d", &N, &K, &D);
    rep(i, N) scanf("%lld", &a[i + 1]);
    
    // 2. 初期化.
    rep(i, 101) rep(k, 101) rep(d, 101) dp[i][k][d] = -1;
    dp[0][0][0] = 0;
    
    // 3. dp更新.
    repx(i, 1, N + 1){
        rep(k, K){
            rep(d, D){
                if(dp[i - 1][k][d] != -1){
                    // i番目 を 含める.
                    int r = (int)((dp[i - 1][k][d] + a[i]) % D);
                    dp[i][k + 1][r] = max(dp[i][k + 1][r], dp[i - 1][k][d] + a[i]);
                    
                    // i番目 を 含めない.
                    dp[i][k][d] = max(dp[i][k][d], dp[i - 1][k][d]);
                }
            }
        }
    }
    
    // 4. 最大値は？
    // -> K 項 の 和 かつ D の 倍数 で, 最大値 を 抽出.
    LL ans = -1;
    repx(i, 1, N + 1) ans = max(ans, dp[i][K][0]);
    
    // 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--)

LL a[111], dp[101][101][101];

int main(){

// 1. 入力情報.

int N, K, D;

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

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

// 2. 初期化.

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

dp[0][0][0] = 0;

// 3. dp更新.

repx(i, 1, N + 1){

rep(k, K){

rep(d, D){

if(dp[i - 1][k][d] != -1){

// i番目を含める.

int r = (int)((dp[i - 1][k][d] + a[i]) % D);

dp[i][k + 1][r] = max(dp[i][k + 1][r], dp[i - 1][k][d] + a[i]);

// i番目を含めない.

dp[i][k][d] = max(dp[i][k][d], dp[i - 1][k][d]);

}

// 4. 最大値は？

// -> K 項の和かつ D の倍数で, 最大値を抽出.

LL ans = -1;

repx(i, 1, N + 1) ans = max(ans, dp[i][K][0]);

// 5. 出力.

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

return 0;

}

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

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

[入力例]
3 1 2
1 3 5

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

[入力例]
5 3 11
24 51 121 99 59

[出力例]
231

[入力例]
7 5 23
17 18 32 31 24 67 10

[出力例]
115

[入力例]
10 7 25
137 341 1076 904 918 260 1162 522 77 553

[出力例]
5000

[入力例]
20 8 50
9714 2793 8323 5761 8174 8744 4510 12431 13882 5782 5484 10155 15805 6603 11644 15739 5960 12170 3532 3163

[出力例]
100000

[入力例]
30 18 75
831021 430434 587696 611139 556413 432910 518107 521563 493192 323579 158772 847917 971788 89466 304955 1198448 779351 329823 1262641 938893 733769 503082 1058434 1219455 857062 679021 486827 652111 285795 766320

[出力例]
15000000

[入力例]

4 2 2

1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

3 1 2

1 3 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 3 11

24 51 121 99 59

[出力例]

231

[入力例]

7 5 23

17 18 32 31 24 67 10

[出力例]

115

[入力例]

10 7 25

137 341 1076 904 918 260 1162 522 77 553

[出力例]

5000

[入力例]

20 8 50

9714 2793 8323 5761 8174 8744 4510 12431 13882 5782 5484 10155 15805 6603 11644 15739 5960 12170 3532 3163

[出力例]

100000

[入力例]

30 18 75

831021 430434 587696 611139 556413 432910 518107 521563 493192 323579 158772 847917 971788 89466 304955 1198448 779351 329823 1262641 938893 733769 503082 1058434 1219455 857062 679021 486827 652111 285795 766320

[出力例]

15000000

■参照サイト
AtCoder Beginner Contest 281

C++の練習を兼ねて, AtCoder Beginner Contest 284 の 問題C (Count Connected Components) ～ 問題D (Happy New Year 2023) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 215 の 問題G (Colorful Candies 2) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 215 の 問題E (Chain Contestant) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 282 の 問題E (Choose Two and Eat One) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 282 の 問題C (String Delimiter) ～ 問題D (Make Bipartite 2) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 283 の 問題C (Cash Register) ～ 問題D (Scope) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 281 の 問題E (Least Elements) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 281 の 問題C (Circular Playlist) ～ 問題D (Max Multiple) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 284 の問題C (Count Connected Components) ～問題D (Happy New Year 2023) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 215 の問題G (Colorful Candies 2) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 215 の問題E (Chain Contestant) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 282 の問題E (Choose Two and Eat One) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 282 の問題C (String Delimiter) ～問題D (Make Bipartite 2) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 283 の問題C (Cash Register) ～問題D (Scope) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 281 の問題E (Least Elements) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 281 の問題C (Circular Playlist) ～問題D (Max Multiple) を解いてみた.