C++ | 個人用メモ帳

2024年6月23日

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

C++の練習を兼ねて, AtCoder Beginner Contest 353 の問題C (Sigma Problem) ～問題D (Another Sigma Problem) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったため, 解説プログラムを参考に, AC版に到達できたと思う.
2. 個人的には, 尺取り法の復習ができたので, 非常に良かったと思う.
3. 引き続き, 時間があれば, 過去問を確認していきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc353/editorial/9957
// 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);
    LL ans = 0;
    rep(i, N){
        scanf("%lld", &a[i]);
        ans += a[i];
    }
    ans *= (N - 1);
    
    // 2. sort.
    sort(all(a));
    
    // 3. 尺取り法.
    int j = N;
    rep(i, N){
        j = max(i + 1, j);
        while(j - 1 > i && a[j - 1] + a[i] >= 100000000) --j;
        ans -= (LL)(N - j) * 100000000;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc353/editorial/9957

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

LL ans = 0;

rep(i, N){

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

ans += a[i];

}

ans *= (N - 1);

// 2. sort.

sort(all(a));

// 3. 尺取り法.

int j = N;

rep(i, N){

j = max(i + 1, j);

while(j - 1 > i && a[j - 1] + a[i] >= 100000000) --j;

ans -= (LL)(N - j) * 100000000;

}

// 4. 出力.

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

return 0;

}

[入力例]
3
3 50000001 50000002

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

[入力例]
5
1 3 99999999 99999994 1000000

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

[入力例]
7
12345678 23456789 34567890 45678901 56789012 67890123 78901234

[出力例]
1017777762

[入力例]

3 50000001 50000002

[出力例]

100000012

※AtCoderテストケースより

[入力例]

1 3 99999999 99999994 1000000

[出力例]

303999988

※AtCoderテストケースより

[入力例]

12345678 23456789 34567890 45678901 56789012 67890123 78901234

[出力例]

1017777762

■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 pb push_back
const LL MOD = 998244353;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vl a(N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 10 の 冪乗.
    vl cPow;
    cPow.pb(1LL);
    rep(i, 11) cPow.pb(cPow.back() * 10LL % MOD);
    
    // 3. 累積和.
    vl pCum(N + 1);
    rep(i, N) pCum[i + 1] = (pCum[i] + a[i]) % MOD;
    
    // 4. 集計(第二引数を基準に, 一括で足し込むようにする).
    // 
    // ex. N = 5
    // f(A1, A2)
    // f(A1, A3) + f(A2, A3)
    // f(A1, A4) + f(A2, A4) + f(A3, A4)
    // f(A1, A5) + f(A2, A5) + f(A3, A5) + f(A4, A5)
    LL ans = 0;
    repx(i, 1, N){
        // 第二引数.
        ans += a[i] * i;
        ans %= MOD;
        
        // 第一引数.
        int d = to_string(a[i]).size();
        ans += pCum[i] * cPow[d] % MOD;
        ans %= MOD;
    }
    
    // 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 pb push_back

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vl a(N);

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

// 2. 10 の冪乗.

vl cPow;

cPow.pb(1LL);

rep(i, 11) cPow.pb(cPow.back() * 10LL % MOD);

// 3. 累積和.

vl pCum(N + 1);

rep(i, N) pCum[i + 1] = (pCum[i] + a[i]) % MOD;

// 4. 集計(第二引数を基準に, 一括で足し込むようにする).

// ex. N = 5

// f(A1, A2)

// f(A1, A3) + f(A2, A3)

// f(A1, A4) + f(A2, A4) + f(A3, A4)

// f(A1, A5) + f(A2, A5) + f(A3, A5) + f(A4, A5)

LL ans = 0;

repx(i, 1, N){

// 第二引数.

ans += a[i] * i;

ans %= MOD;

// 第一引数.

int d = to_string(a[i]).size();

ans += pCum[i] * cPow[d] % MOD;

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
3
3 14 15

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

[入力例]
5
1001 5 1000000 1000000000 100000

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

[入力例]
7
5 7 12 17 1 20 3

[出力例]
9084

[入力例]
10
2024 5 11 2100 12345 54321 999999999 333 222 111

[出力例]
116320320

[入力例]

3 14 15

[出力例]

2044

※AtCoderテストケースより

[入力例]

1001 5 1000000 1000000000 100000

[出力例]

625549048

※AtCoderテストケースより

[入力例]

5 7 12 17 1 20 3

[出力例]

9084

[入力例]

2024 5 11 2100 12345 54321 999999999 333 222 111

[出力例]

116320320

■参照サイト
AtCoder Beginner Contest 353

2024年1月3日

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

C++の練習を兼ねて, AtCoder Regular Contest 165 の問題C (Social Distance on Graph) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説の二部グラフを使った考え方で解ける点が, 興味深く思った.
3. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc165/editorial/7137
// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using T3 = tuple<int, int, int>;
using vi = vector<int>;
using vp = vector<P>;
using vvp = vector<vp>;
using vt = vector<T3>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define all(x) x.begin(), x.end()

// 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, M;
    scanf("%d %d", &N, &M);
    vt t;
    vvp G(N);
    rep(i, M){
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        --a;
        --b;
        G[a].emplace_back(P{w, b});
        G[b].emplace_back(P{w, a});
        t.emplace_back(T3{w, a, b});
    }
    
    // 2. sort.
    sort(all(t));
    rep(i, N) sort(all(G[i]));
    
    // 3. 2本の辺を用いるパスの重みの最小値は？
    int ans = 2020202020;
    rep(i, N) if(G[i].size() >= 2) ans = min(ans, G[i][0].a + G[i][1].a);
    
    // 4. グラフが初めて二部グラフでなくなる辺の重みは？
    // -> 最小全域木(Kruskal's Algorithm) の アルゴリズム を 流用.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    UnionFind uf(2 * N + 4);
    rep(i, t.size()){
        // 4-1. グラフ情報.
        int w = get<0>(t[i]);
        int a = get<1>(t[i]);
        int b = get<2>(t[i]);
        
        // 4-2. 辺 を 追加.
        uf.unite(2 * a, 2 * b + 1);
        uf.unite(2 * b, 2 * a + 1);
        
        // 4-3. 連結か？
        // 二部グラフで無くなった場合に, 連結と判定される.
        if(uf.same(2 * a, 2 * a + 1)){
            ans = min(ans, w);
            break;
        }
    }
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc165/editorial/7137

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

using vi = vector<int>;

using vp = vector<P>;

using vvp = vector<vp>;

using vt = vector<T3>;

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

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

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

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

#define a first

#define b second

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

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

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

vt t;

vvp G(N);

rep(i, M){

int a, b, w;

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

--a;

--b;

G[a].emplace_back(P{w, b});

G[b].emplace_back(P{w, a});

t.emplace_back(T3{w, a, b});

}

// 2. sort.

sort(all(t));

rep(i, N) sort(all(G[i]));

// 3. 2本の辺を用いるパスの重みの最小値は？

int ans = 2020202020;

rep(i, N) if(G[i].size() >= 2) ans = min(ans, G[i][0].a + G[i][1].a);

// 4. グラフが初めて二部グラフでなくなる辺の重みは？

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

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

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

UnionFind uf(2 * N + 4);

rep(i, t.size()){

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

int w = get<0>(t[i]);

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

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

// 4-2. 辺を追加.

uf.unite(2 * a, 2 * b + 1);

uf.unite(2 * b, 2 * a + 1);

// 4-3. 連結か？

// 二部グラフで無くなった場合に, 連結と判定される.

if(uf.same(2 * a, 2 * a + 1)){

ans = min(ans, w);

break;

}

// 5. 出力.

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

return 0;

}

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

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

[入力例]
10 20
7 10 982219000
3 10 968366179
2 4 992330437
5 6 984414664
2 8 897295423
7 9 155604979
6 8 958833005
2 3 973209957
3 7 985173062
6 10 963895817
2 10 986243534
4 5 721724794
1 3 657562445
1 6 566370694
1 4 988050146
1 9 967817807
4 9 796531581
5 9 983960054
1 10 964450079
8 9 959369491

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

[入力例]
10 20
5 6 871895994
8 10 873709822
3 5 454175869
6 10 980782191
2 6 901290987
1 8 298092290
4 8 693116157
4 5 947939338
7 8 934395075
7 9 759563833
5 8 779870031
4 6 919637355
2 9 822858749
4 10 855497285
3 7 954942051
1 2 950411658
4 7 665939990
3 4 634533617
5 7 908372507
1 9 591466693

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

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

[出力例]
7

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

[出力例]
10

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

[出力例]
12

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

[入力例]

3 3

1 2 5

2 3 6

1 3 12

[出力例]

※AtCoderのテストケースより

[入力例]

10 20

7 10 982219000

3 10 968366179

2 4 992330437

5 6 984414664

2 8 897295423

7 9 155604979

6 8 958833005

2 3 973209957

3 7 985173062

6 10 963895817

2 10 986243534

4 5 721724794

1 3 657562445

1 6 566370694

1 4 988050146

1 9 967817807

4 9 796531581

5 9 983960054

1 10 964450079

8 9 959369491

[出力例]

952136560

※AtCoderのテストケースより

[入力例]

10 20

5 6 871895994

8 10 873709822

3 5 454175869

6 10 980782191

2 6 901290987

1 8 298092290

4 8 693116157

4 5 947939338

7 8 934395075

7 9 759563833

5 8 779870031

4 6 919637355

2 9 822858749

4 10 855497285

3 7 954942051

1 2 950411658

4 7 665939990

3 4 634533617

5 7 908372507

1 9 591466693

[出力例]

759563833

※AtCoderのテストケースより

[入力例]

5 7

1 2 3

1 3 7

1 5 4

2 5 9

3 4 8

2 4 7

3 5 10

[出力例]

[入力例]

12 11

1 2 8

1 5 3

1 4 7

2 3 12

2 7 5

3 10 8

4 8 5

4 6 11

6 9 3

7 11 8

10 12 13

[出力例]

[入力例]

16 20

1 2 8

1 4 7

1 15 8

2 3 12

2 4 18

2 6 6

2 9 20

3 7 12

3 9 10

4 7 7

4 8 12

5 8 7

5 13 12

6 14 18

7 10 30

7 11 11

8 12 10

9 10 6

11 12 5

15 16 27

[出力例]

■参照サイト
AtCoder Regular Contest 165
Union-Find木

2024年1月2日

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

C++の練習を兼ねて, AtCoder Regular Contest 165 の問題B (Sliding Window Sort 2) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc165/editorial/7136
// 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 all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vi p(N);
    rep(i, N) scanf("%d", &p[i]);
    
    // 2. 累積和.
    vi qCum(N + 1, 0);
    rep(i, N) qCum[i + 1] = qCum[i] + ((i + 1 < N) && (p[i] < p[i + 1]));
    
    // 3. Q[i] = P となる i が存在するか？
    rep(i, N - K + 1){
        if(qCum[i + K - 1] - qCum[i] == K - 1){
            rep(j, N) printf("%d%s", p[j], (j < N - 1) ? " " : "\n");
            return 0;
        }
    }
    
    // 3. 累積min.
    vi pCumMin(N + 1, N + 1);
    repx(i, N - K, N) pCumMin[i + 1] = min(pCumMin[i], p[i]);
    
    // 5. 上記以外.
    // 5-1. Q[N - K + 1].
    vi q1(N - K), qr1(K);
    rep(i, N - K) q1[i] = p[i];
    repx(i, N - K, N) qr1[i - (N - K)] = p[i];
    sort(all(qr1));
    q1.insert(q1.end(), all(qr1));
    
    // 5-2. Q[i](判定).
    int idx = -1;
    rep(i, N - K){
        // 条件 1.
        bool ok = false;
        if(qCum[N - K] - qCum[i] == N - K - i) ok = true;
        
        // 条件 2.
        if(!ok) continue;
        if(N - K - 1 >= 0){
            if(pCumMin[i + K - 1] > p[N - K - 1]){
                idx = i;
                break;
            }
        }
    }
    
    // 5-3. 出力(Q[N - K + 1]).
    if(idx == -1){
        rep(j, N) printf("%d%s", q1[j], (j < N - 1) ? " " : "\n");
        return 0;
    }
    
    // 5-4. Q[i](構築).
    vi q2(idx), qm2(K), qr2(N - idx - K);
    rep(i, idx) q2[i] = p[i];
    repx(i, idx, idx + K) qm2[i - idx] = p[i];
    sort(all(qm2));
    repx(i, idx + K, N) qr2[i - (idx + K)] = p[i];
    q2.insert(q2.end(), all(qm2));
    q2.insert(q2.end(), all(qr2));
    
    // 5-5. 出力(Q[N - K + 1], Q[i] を 比較した結果).
    if(q1 > q2) rep(j, N) printf("%d%s", q1[j], (j < N - 1) ? " " : "\n");
    else        rep(j, N) printf("%d%s", q2[j], (j < N - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc165/editorial/7136

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

int main(){

// 1. 入力情報.

int N, K;

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

vi p(N);

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

// 2. 累積和.

vi qCum(N + 1, 0);

rep(i, N) qCum[i + 1] = qCum[i] + ((i + 1 < N) && (p[i] < p[i + 1]));

// 3. Q[i] = P となる i が存在するか？

rep(i, N - K + 1){

if(qCum[i + K - 1] - qCum[i] == K - 1){

rep(j, N) printf("%d%s", p[j], (j < N - 1) ? " " : "\n");

return 0;

}

// 3. 累積min.

vi pCumMin(N + 1, N + 1);

repx(i, N - K, N) pCumMin[i + 1] = min(pCumMin[i], p[i]);

// 5. 上記以外.

// 5-1. Q[N - K + 1].

vi q1(N - K), qr1(K);

rep(i, N - K) q1[i] = p[i];

repx(i, N - K, N) qr1[i - (N - K)] = p[i];

sort(all(qr1));

q1.insert(q1.end(), all(qr1));

// 5-2. Q[i](判定).

int idx = -1;

rep(i, N - K){

// 条件 1.

bool ok = false;

if(qCum[N - K] - qCum[i] == N - K - i) ok = true;

// 条件 2.

if(!ok) continue;

if(N - K - 1 >= 0){

if(pCumMin[i + K - 1] > p[N - K - 1]){

idx = i;

break;

}

// 5-3. 出力(Q[N - K + 1]).

if(idx == -1){

rep(j, N) printf("%d%s", q1[j], (j < N - 1) ? " " : "\n");

return 0;

}

// 5-4. Q[i](構築).

vi q2(idx), qm2(K), qr2(N - idx - K);

rep(i, idx) q2[i] = p[i];

repx(i, idx, idx + K) qm2[i - idx] = p[i];

sort(all(qm2));

repx(i, idx + K, N) qr2[i - (idx + K)] = p[i];

q2.insert(q2.end(), all(qm2));

q2.insert(q2.end(), all(qr2));

// 5-5. 出力(Q[N - K + 1], Q[i] を比較した結果).

if(q1 > q2) rep(j, N) printf("%d%s", q1[j], (j < N - 1) ? " " : "\n");

else rep(j, N) printf("%d%s", q2[j], (j < N - 1) ? " " : "\n");

return 0;

}

[入力例]
4 3
2 1 4 3

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

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

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

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

[出力例]
9 4 3 1 11 12 13 15 17 7 2 5 6 8 18 19 20 16 14 10
※AtCoderのテストケースより

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

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

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

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

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

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

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

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

[入力例]

4 3

2 1 4 3

[出力例]

2 1 3 4

※AtCoderのテストケースより

[入力例]

5 1

3 1 4 2 5

[出力例]

3 1 4 2 5

※AtCoderのテストケースより

[入力例]

20 7

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

[出力例]

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

※AtCoderのテストケースより

[入力例]

7 2

7 6 5 4 3 2 1

[出力例]

7 6 5 4 3 1 2

[入力例]

10 5

7 5 4 10 3 9 6 8 2 1

[出力例]

7 5 4 10 3 1 2 6 8 9

[入力例]

20 7

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

[出力例]

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

[入力例]

50 10

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

[出力例]

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

■参照サイト
AtCoder Regular Contest 165

2024年1月1日

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

C++の練習を兼ねて, AtCoder Regular Contest 165 の問題A (Sum equals LCM) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc165/editorial/7130
// 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
const int MAX = 31623;

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. 素数.
    vi a(MAX + 1, 0), v;
    repx(i, 2, MAX + 1){
        if(a[i]) continue;
        repex(j, i * 2, MAX + 1, i) ++a[j];
    }
    repx(i, 2, MAX + 1) if(!a[i]) v.pb(i);
    
    // 3. テストケース.
    rep(i, T){
        // 3-1. 各テストケース.
        int N;
        scanf("%d ", &N);
        
        // 3-2. N を 割り切る最小の素数は？
        int p = -1;
        for(auto &x : v){
            if(N % x == 0){
                p = x;
                break;
            }
        }
        
        // 3-3. N が 素数.
        if(p == -1){
            puts("No");
            continue;
        }
        
        // 3-4. N を 素数で割っていく.
        int n = N, r = 0;
        while(r == 0){
            r = n % p;
            n /= p;
        }
        
        // 3-5. 出力.
        puts((n == 0 && r == 1) ? "No" : "Yes");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc165/editorial/7130

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

const int MAX = 31623;

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. 素数.

vi a(MAX + 1, 0), v;

repx(i, 2, MAX + 1){

if(a[i]) continue;

repex(j, i * 2, MAX + 1, i) ++a[j];

}

repx(i, 2, MAX + 1) if(!a[i]) v.pb(i);

// 3. テストケース.

rep(i, T){

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

int N;

scanf("%d ", &N);

// 3-2. N を割り切る最小の素数は？

int p = -1;

for(auto &x : v){

if(N % x == 0){

p = x;

break;

}

// 3-3. N が素数.

if(p == -1){

puts("No");

continue;

}

// 3-4. N を素数で割っていく.

int n = N, r = 0;

while(r == 0){

r = n % p;

n /= p;

}

// 3-5. 出力.

puts((n == 0 && r == 1) ? "No" : "Yes");

}

return 0;

}

[入力例]
4
6
4
998244353
367291763

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

[入力例]
10
2
6
10
121
1089
2024
83521
123456
166375
912704521

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

[入力例]

998244353

367291763

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

121

1089

2024

83521

123456

166375

912704521

[出力例]

Yes

■参照サイト
AtCoder Regular Contest 165

2023年12月5日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc324/editorial/7405
// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vvi = vector<vector<int>>;
using vvt = vector<vector<tuple<int, 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 pb push_back

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    vvt t(N);
    rep(i, M){
        int u, v, b, c;
        scanf("%d %d %d %d", &u, &v, &b, &c);
        --u;
        --v;
        
        // 有向グラフ.
        G[u].pb(v);
        
        // 頂点, 美しさ, コスト.
        t[u].emplace_back(v, b, c);
    }
    
    // 2. 評価関数.
    auto f = [&](LL x) -> bool {
        // 2-1. 初期化.
        LL dp[N];
        rep(i, N) dp[i] = -2e18;
        dp[0] = 0;
        
        // 2-2. dp更新(頂点番号の小さい順).
        rep(u, N){
            // 辺(u, v)で, 最大値更新.
            for(auto &e : t[u]){
                int v = get<0>(e);
                int b = get<1>(e);
                int c = get<2>(e);
                dp[v] = max(dp[v], dp[u] + (LL)b * 1000000000 - (LL)c * x);
            }
        }
        
        // 2-3. 判定結果(OK).
        return (dp[N - 1] >= 0);
    };
    
    // 3. 二分探索で確認してみる.
    LL l = -1, h = 400000000000001;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    
    // 4. 出力.
    printf("%.16lf\n", (double)h / 1000000000);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc324/editorial/7405

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vvi = vector<vector<int>>;

using vvt = vector<vector<tuple<int, 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 pb push_back

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

vvt t(N);

rep(i, M){

int u, v, b, c;

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

--u;

--v;

// 有向グラフ.

G[u].pb(v);

// 頂点, 美しさ, コスト.

t[u].emplace_back(v, b, c);

}

// 2. 評価関数.

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

// 2-1. 初期化.

LL dp[N];

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

dp[0] = 0;

// 2-2. dp更新(頂点番号の小さい順).

rep(u, N){

// 辺(u, v)で, 最大値更新.

for(auto &e : t[u]){

int v = get<0>(e);

int b = get<1>(e);

int c = get<2>(e);

dp[v] = max(dp[v], dp[u] + (LL)b * 1000000000 - (LL)c * x);

}

// 2-3. 判定結果(OK).

return (dp[N - 1] >= 0);

};

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

LL l = -1, h = 400000000000001;

while(l + 1 < h){

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

if(f(m)) l = m;

else h = m;

// printf("h=%lld l=%lld m=%lld\n", h, l, m);

}

// 4. 出力.

printf("%.16lf\n", (double)h / 1000000000);

return 0;

}

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

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

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

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

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

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

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

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

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

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

[出力例]
2.2500000010000001

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

[出力例]
3.5000000010000001

[入力例]

5 7

1 2 3 6

1 3 9 5

2 3 1 5

2 4 5 3

2 5 1 9

3 4 4 8

4 5 2 7

[出力例]

0.7500000000000000

※AtCoderテストケースより

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

0.7500000010000000

[入力例]

3 3

1 3 1 1

1 3 2 1

1 3 3 1

[出力例]

3.0000000000000000

※AtCoderテストケースより

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

3.0000000010000001

[入力例]

10 20

3 4 1 2

7 9 4 5

2 4 4 5

4 5 1 4

6 9 4 1

9 10 3 2

6 10 5 5

5 6 1 2

5 6 5 2

2 3 2 3

6 10 4 4

4 6 3 4

4 8 4 1

3 5 3 2

2 4 3 2

3 5 4 2

1 5 3 4

1 2 4 2

3 7 2 2

7 8 1 3

[出力例]

1.8333333333333333

※AtCoderテストケースより

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

1.8333333340000000

[入力例]

7 10

1 2 5 6

2 3 1 6

2 7 5 8

3 7 9 2

1 5 3 1

5 6 5 6

3 6 5 7

4 6 3 7

3 4 6 1

6 7 10 1

[出力例]

2.2500000010000001

[入力例]

10 16

1 2 3 2

1 5 2 1

2 5 10 2

2 3 3 5

3 4 6 1

5 6 3 7

6 7 2 10

5 7 6 1

6 8 3 8

7 8 10 1

8 10 6 4

7 10 3 5

6 10 8 1

3 9 3 1

4 9 5 3

9 10 5 1

[出力例]

3.5000000010000001

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

2023年12月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 330 の問題C (Minimize Abs 2) ～問題E (Mex and Update) を解いてみた.

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

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

■C++版プログラム(問題C／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
#define all(x) x.begin(), x.end()
const int MAX = 1414214;

int main(){
    
    // 1. 入力情報.
    LL D;
    scanf("%lld", &D);
    
    // 2. 平方数.
    vl sNum;
    rep(i, MAX) sNum.pb((LL)i * (LL)i);
    
    // 3. 最小値は？
    LL ans = 202020202020202020;
    rep(i, MAX){
        LL gap = D - sNum[i];
        if(gap < 0) break;
        int at = lower_bound(all(sNum), gap) - sNum.begin();
        if(at)       ans = min(ans, abs(sNum[i] + sNum[at - 1] - D));
        if(at < MAX) ans = min(ans, abs(sNum[i] + sNum[at] - D));
    }
    
    // 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

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

const int MAX = 1414214;

int main(){

// 1. 入力情報.

LL D;

scanf("%lld", &D);

// 2. 平方数.

vl sNum;

rep(i, MAX) sNum.pb((LL)i * (LL)i);

// 3. 最小値は？

LL ans = 202020202020202020;

rep(i, MAX){

LL gap = D - sNum[i];

if(gap < 0) break;

int at = lower_bound(all(sNum), gap) - sNum.begin();

if(at) ans = min(ans, abs(sNum[i] + sNum[at - 1] - D));

if(at < MAX) ans = min(ans, abs(sNum[i] + sNum[at] - D));

}

// 4. 出力.

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

return 0;

}

[入力例]
21

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

[入力例]
998244353

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

[入力例]
264428617

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

[入力例]
12345

[出力例]
1

[入力例]
4092529

[出力例]
0

[入力例]
3703629658

[出力例]
7

[入力例]
202311252100

[出力例]
2

[入力例]
1987654321012

[出力例]
0

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

998244353

[出力例]

※AtCoderテストケースより

[入力例]

264428617

[出力例]

※AtCoderテストケースより

[入力例]

12345

[出力例]

[入力例]

4092529

[出力例]

[入力例]

3703629658

[出力例]

[入力例]

202311252100

[出力例]

[入力例]

1987654321012

[出力例]

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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--)
LL rCum[2020][2020], cCum[2020][2020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vs v(N);
    rep(i, N){
        char c[N + 1];
        scanf("%s", c);
        string s(c);
        v[i] = s;
    }
    
    // 2. 累積和.
    rep(i, N) rep(j, N) rCum[i][j + 1] = rCum[i][j] + (v[i][j] == 'o');
    rep(j, N) rep(i, N) cCum[i + 1][j] = cCum[i][j] + (v[i][j] == 'o');
    
    // 3. 集計.
    LL ans = 0;
    rep(i, N) rep(j, N) if(v[i][j] == 'o') ans += (rCum[i][N] - 1) * (cCum[N][j] - 1);
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

LL rCum[2020][2020], cCum[2020][2020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vs v(N);

rep(i, N){

char c[N + 1];

scanf("%s", c);

string s(c);

v[i] = s;

}

// 2. 累積和.

rep(i, N) rep(j, N) rCum[i][j + 1] = rCum[i][j] + (v[i][j] == 'o');

rep(j, N) rep(i, N) cCum[i + 1][j] = cCum[i][j] + (v[i][j] == 'o');

// 3. 集計.

LL ans = 0;

rep(i, N) rep(j, N) if(v[i][j] == 'o') ans += (rCum[i][N] - 1) * (cCum[N][j] - 1);

// 4. 出力.

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

return 0;

}

[入力例]
3
ooo
oxx
xxo

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

[入力例]
4
oxxx
xoxx
xxox
xxxo

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

[入力例]
15
xooxxooooxxxoox
oxxoxoxxxoxoxxo
oxxoxoxxxoxoxxx
ooooxooooxxoxxx
oxxoxoxxxoxoxxx
oxxoxoxxxoxoxxo
oxxoxooooxxxoox
xxxxxxxxxxxxxxx
xooxxxooxxxooox
oxxoxoxxoxoxxxo
xxxoxxxxoxoxxoo
xooxxxooxxoxoxo
xxxoxxxxoxooxxo
oxxoxoxxoxoxxxo
xooxxxooxxxooox

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

[入力例]
5
oxoxo
xoxox
oxoxo
xoxox
oxoxo

[出力例]
40

[入力例]
20
xoxxoxxoxoxooxoooxox
oooxoooxxoxooxooxoxx
oooooxoxoooxooxooxxx
xxoxxxxooxxooxxxoooo
xoooxooxxxxooooxoxoo
xoxxoxxooxooxxxxxoox
oxooooooooxxxxooxoxx
oxooooxxoxoxoxoxxxxo
xxoooxxoxxxoxoxooooo
xooxooxoxxxxoooxxxxo
ooxoxoooxxxooxoxoxoo
xooxoxoxoxooxoooxooo
xxooxoooxooooooooxxx
xxooxooxooooxoxxxxox
oxxoxxxxoxxoxoxxxooo
oxoxoxxxxoooxxoxoxoo
ooxooooxooxoooxxxxoo
ooxooxxoxoxxxxxxxoxo
oxooooxxoxxxoxxoxxox
xooxxoxooxoxxoxoxxxx

[出力例]
20113

[入力例]
50
xooxoxoooxxxoooooxxxxooxoxoooxxxoooooxxxooxooxooox
xxxooxxooxoooxoxooooxooxoxoooxxxoooooxxxoxxoxxoxox
ooxooxxxxoxoxoxooxxxxooxoxoooxxxoooooxxxoooxxxooxo
ooxxoxoxxoxoxoxoxoxxxooxoxoooxoxoooooxxxooxooxooox
xxxxxooxoooxooxoxoooxooxoxoooxxxoooooxxxoooxxxooxo
xoxxxxoxooxoooxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox
xoooxoxoooooooxoooxxxooxoxoooxxxoooooxxxooxxxxooxo
xxoxoxooxooxoooxxoxxxooxoxoooxxxoooooxxxooxooxooox
xxooxxxoxoxxoxxxoxxoxooxoxoooxoxoooooxxxooxxoxooxo
xxxoxxoxooxxoxxoxxooxooxoxoooxxxoooooxxxoooxxxooxo
oxoxooooxxxxoxoxxxxoxooxoxoooxxxoooooxxxoxxooxoxox
xxxxoxoxxxooxoxxooxxxooxoxoooxxxoooooxxxooxooxooox
xoxoooooxxoxoooxoxxoxooxoxoooxxxoooooxoxooxxxxooxo
xoxooxooooxoooxoooxoxooxoxoooxxxoooooxxxoooxxxooxo
oxoxxoxxoxxoxoxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox
oooxoxoxoxxxxooxoxxoxooxoxoooxxxoxoooxxxooxxxxooxo
xooxxooxxxoxxxoxxoooxooxoxoooxxxoooooxxxooxooxooox
oxoxoxxoooooooxoxxxxxooxoxoooxxxoxoooxxxoxxoxxoxox
xxxxoxxoxxxooxoxoxoxxooxoxoooxxxoooxoxoxoooxxxooxo
xooxooxxooxoxooxxoxoxooxoxoooxxxoooooxxxooxooxooox
oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo
oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxoxooxxxxooxo
oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo
oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxoxooxxxxooxo
oooxoxoxoxxoxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo
xooxoxoooxoxoooooxxxxooxoxoooxxxoooooxxoooxooxooox
xxxooxxooxoooxoxooooxooxoxoooxxxoooooxxxoxxoxxoxox
ooxooxxxxoxoxoxooxxxxooxoxoooxxxoooooxxxoooxxxooxo
ooxxoxoxxoxoxoxoxoxoxooxoxoooxxxoooooxoxooxooxooox
xxxxxooxoooxooxoxoooxooxoxoooxxxoooooxxxoooxxxooxo
xoxoxxoxooxoooxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox
xoooxoxoooooooxoooxxxooxoxoooxxxoooooxoxooxxxxooxo
xxoxoxooxooxoooxxoxxxooxoxoooxxxoooooxxxooxooxooox
xxooxxxoxoxxoxxxoxxoxooxoxoooxxxoooooxxoooxxxoooxo
xxxoxxoxooxxoxxoxxooxooxoxoooxxxoooooxxxoooxxxooxo
oxoxooooxxxxoxoxxxxoxooxoxoooxoxoooooxxxoxxoxxoxox
xxxxoxoxxxooxoxxooxxxooxoxoooxxxoooooxxxooxooxoooo
xoxoooooxxoxoooxoxxoxooxoxoooxxooooooxxxooxxxxooxo
xoxooxooooxoooxoooxoxooxoxoooxxxoooooxxxoooxoxooxo
oxoxxoxxoxxoxoxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox
oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo
xooxxooxxxoxxxoxxoooxooxoxoooxxxoooooxxxooxooxooox
oxoxoxxoooooooxoxxxxxooxoxoooxxxoooooxxxoxxoxxoxox
xxxxoxxoxxxooxoxoxoxxooxoxoooxxxoooooxxxoooxxxooxo
xooxooxxooxoxooxxoxoxooxoxoooxxxoooooxxxooxooxooox
oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo
oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo
oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo
oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo
oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo

[出力例]
1303146

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

[入力例]

ooo

oxx

xxo

[出力例]

※AtCoderテストケースより

[入力例]

oxxx

xoxx

xxox

xxxo

[出力例]

※AtCoderテストケースより

[入力例]

xooxxooooxxxoox

oxxoxoxxxoxoxxo

oxxoxoxxxoxoxxx

ooooxooooxxoxxx

oxxoxoxxxoxoxxx

oxxoxoxxxoxoxxo

oxxoxooooxxxoox

xxxxxxxxxxxxxxx

xooxxxooxxxooox

oxxoxoxxoxoxxxo

xxxoxxxxoxoxxoo

xooxxxooxxoxoxo

xxxoxxxxoxooxxo

oxxoxoxxoxoxxxo

xooxxxooxxxooox

[出力例]

2960

※AtCoderテストケースより

[入力例]

oxoxo

xoxox

oxoxo

xoxox

oxoxo

[出力例]

[入力例]

xoxxoxxoxoxooxoooxox

oooxoooxxoxooxooxoxx

oooooxoxoooxooxooxxx

xxoxxxxooxxooxxxoooo

xoooxooxxxxooooxoxoo

xoxxoxxooxooxxxxxoox

oxooooooooxxxxooxoxx

oxooooxxoxoxoxoxxxxo

xxoooxxoxxxoxoxooooo

xooxooxoxxxxoooxxxxo

ooxoxoooxxxooxoxoxoo

xooxoxoxoxooxoooxooo

xxooxoooxooooooooxxx

xxooxooxooooxoxxxxox

oxxoxxxxoxxoxoxxxooo

oxoxoxxxxoooxxoxoxoo

ooxooooxooxoooxxxxoo

ooxooxxoxoxxxxxxxoxo

oxooooxxoxxxoxxoxxox

xooxxoxooxoxxoxoxxxx

[出力例]

20113

[入力例]

xooxoxoooxxxoooooxxxxooxoxoooxxxoooooxxxooxooxooox

xxxooxxooxoooxoxooooxooxoxoooxxxoooooxxxoxxoxxoxox

ooxooxxxxoxoxoxooxxxxooxoxoooxxxoooooxxxoooxxxooxo

ooxxoxoxxoxoxoxoxoxxxooxoxoooxoxoooooxxxooxooxooox

xxxxxooxoooxooxoxoooxooxoxoooxxxoooooxxxoooxxxooxo

xoxxxxoxooxoooxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox

xoooxoxoooooooxoooxxxooxoxoooxxxoooooxxxooxxxxooxo

xxoxoxooxooxoooxxoxxxooxoxoooxxxoooooxxxooxooxooox

xxooxxxoxoxxoxxxoxxoxooxoxoooxoxoooooxxxooxxoxooxo

xxxoxxoxooxxoxxoxxooxooxoxoooxxxoooooxxxoooxxxooxo

oxoxooooxxxxoxoxxxxoxooxoxoooxxxoooooxxxoxxooxoxox

xxxxoxoxxxooxoxxooxxxooxoxoooxxxoooooxxxooxooxooox

xoxoooooxxoxoooxoxxoxooxoxoooxxxoooooxoxooxxxxooxo

xoxooxooooxoooxoooxoxooxoxoooxxxoooooxxxoooxxxooxo

oxoxxoxxoxxoxoxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox

oooxoxoxoxxxxooxoxxoxooxoxoooxxxoxoooxxxooxxxxooxo

xooxxooxxxoxxxoxxoooxooxoxoooxxxoooooxxxooxooxooox

oxoxoxxoooooooxoxxxxxooxoxoooxxxoxoooxxxoxxoxxoxox

xxxxoxxoxxxooxoxoxoxxooxoxoooxxxoooxoxoxoooxxxooxo

xooxooxxooxoxooxxoxoxooxoxoooxxxoooooxxxooxooxooox

oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo

oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxoxooxxxxooxo

oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo

oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxoxooxxxxooxo

oooxoxoxoxxoxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo

xooxoxoooxoxoooooxxxxooxoxoooxxxoooooxxoooxooxooox

xxxooxxooxoooxoxooooxooxoxoooxxxoooooxxxoxxoxxoxox

ooxooxxxxoxoxoxooxxxxooxoxoooxxxoooooxxxoooxxxooxo

ooxxoxoxxoxoxoxoxoxoxooxoxoooxxxoooooxoxooxooxooox

xxxxxooxoooxooxoxoooxooxoxoooxxxoooooxxxoooxxxooxo

xoxoxxoxooxoooxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox

xoooxoxoooooooxoooxxxooxoxoooxxxoooooxoxooxxxxooxo

xxoxoxooxooxoooxxoxxxooxoxoooxxxoooooxxxooxooxooox

xxooxxxoxoxxoxxxoxxoxooxoxoooxxxoooooxxoooxxxoooxo

xxxoxxoxooxxoxxoxxooxooxoxoooxxxoooooxxxoooxxxooxo

oxoxooooxxxxoxoxxxxoxooxoxoooxoxoooooxxxoxxoxxoxox

xxxxoxoxxxooxoxxooxxxooxoxoooxxxoooooxxxooxooxoooo

xoxoooooxxoxoooxoxxoxooxoxoooxxooooooxxxooxxxxooxo

xoxooxooooxoooxoooxoxooxoxoooxxxoooooxxxoooxoxooxo

oxoxxoxxoxxoxoxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox

oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo

xooxxooxxxoxxxoxxoooxooxoxoooxxxoooooxxxooxooxooox

oxoxoxxoooooooxoxxxxxooxoxoooxxxoooooxxxoxxoxxoxox

xxxxoxxoxxxooxoxoxoxxooxoxoooxxxoooooxxxoooxxxooxo

xooxooxxooxoxooxxoxoxooxoxoooxxxoooooxxxooxooxooox

oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo

[出力例]

1303146

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

// 解き直し.
// https://atcoder.jp/contests/abc330/editorial/7752
// 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 a[202020], bk[202020];

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 初期化.
    set<int> st;
    rep(i, N) if(a[i] <= N) ++bk[a[i]];
    rep(k, N + 1) if(bk[k] == 0) st.insert(k);
    
    // 3. クエリ回答(解説通り).
    rep(j, Q){
        // 3-1. クエリ入力情報.
        int i, x;
        scanf("%d %d", &i, &x);
        --i;
        
        // 3-2. 出現回数更新(更新前a[i]).
        if(a[i] < N + 1){
            --bk[a[i]];
            if(bk[a[i]] == 0) st.insert(a[i]);
        }
        
        // 3-3. a[i]更新.
        a[i] = x;
        
        // 3-4. 出現回数更新(更新後a[i]).
        if(a[i] < N + 1){
            if(bk[a[i]] == 0) st.erase(a[i]);
            ++bk[a[i]];
        }
        
        // 3-5. 出力.
        printf("%d\n", *st.begin());
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc330/editorial/7752

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

int main(){

// 1. 入力情報.

int N, Q;

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

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

// 2. 初期化.

set<int> st;

rep(i, N) if(a[i] <= N) ++bk[a[i]];

rep(k, N + 1) if(bk[k] == 0) st.insert(k);

// 3. クエリ回答(解説通り).

rep(j, Q){

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

int i, x;

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

--i;

// 3-2. 出現回数更新(更新前a[i]).

if(a[i] < N + 1){

--bk[a[i]];

if(bk[a[i]] == 0) st.insert(a[i]);

}

// 3-3. a[i]更新.

a[i] = x;

// 3-4. 出現回数更新(更新後a[i]).

if(a[i] < N + 1){

if(bk[a[i]] == 0) st.erase(a[i]);

++bk[a[i]];

}

// 3-5. 出力.

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

}

return 0;

}

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

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

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

[出力例]
0
1
2
0
2

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

[出力例]
2
4
5
3
1

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

[出力例]
0
0
0
1
1

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

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

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

[出力例]
5
6
11
11
11
11
8
8
9
5
5
5
11
11
1
1
1
6
6
6
6
10
6
10
10

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

[入力例]

8 5

2 0 2 2 1 1 2 5

4 3

4 4

6 3

8 1000000000

2 1

[出力例]

※AtCoderテストケースより

[入力例]

3 5

7 7 7

3 3

2 0

1 1

2 4

2 0

[出力例]

[入力例]

5 5

0 1 3 5 7

4 6

4 2

5 4

3 0

2 2

[出力例]

[入力例]

5 5

1000000000 1000000000 1000000000 1000000000 1000000000

4 6

4 2

5 4

3 0

2 2

[出力例]

[入力例]

10 7

1 0 3 5 4 3 7 8 12 15

1 0

2 1

1 1

3 0

9 2

8 6

6 9

[出力例]

[入力例]

20 25

1 9 2 0 4 16 2 4 8 9 0 3 2 0 3 4 8 7 10 10

9 25

8 5

20 6

2 0

16 1

7 2

17 2

4 0

10 8

8 23

8 9

3 13

16 5

2 8

1 3

20 9

13 14

6 1

20 7

18 1

4 12

19 6

19 2

1 6

13 8

[出力例]

■参照サイト
トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)

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）

C++の練習を兼ねて, AtCoder Beginner Contest 353 の 問題C (Sigma Problem) ～ 問題D (Another Sigma Problem) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 165 の 問題C (Social Distance on Graph) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 165 の 問題B (Sliding Window Sort 2) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 165 の 問題A (Sum equals LCM) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 330 の 問題C (Minimize Abs 2) ～ 問題E (Mex and Update) を解いてみた.

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 Beginner Contest 353 の問題C (Sigma Problem) ～問題D (Another Sigma Problem) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 165 の問題C (Social Distance on Graph) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 165 の問題B (Sliding Window Sort 2) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 165 の問題A (Sum equals LCM) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 330 の問題C (Minimize Abs 2) ～問題E (Mex and Update) を解いてみた.

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) を解いてみた.