C++ | 個人用メモ帳

2022年7月1日

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

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

■感想.
1. 問題Fは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 解説のロジックで, 最小の移動時間が抽出できる点が, 不思議に見え, 非常に面白く感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc257/editorial/4183
// 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
const int INF = 20202020;

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N + 1);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --v;
        
        // 仮想頂点と可変テレポーターを結ぶ.
        if(!u){
            G[N].pb(v);
            G[v].pb(N);
        }
        
        // 通常のグラフ作成.
        if(u){
            --u;
            G[u].pb(v);
            G[v].pb(u);
        }
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d) {
        // 空のキュー.
        queue<int> q;
        
        // 開始地点は, 距離ゼロ.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(d[e] == INF && e != s) d[e] = d[u] + 1, q.push(e);
        }
    };
    
    // 3. 町 1 からの 最短距離.
    int d1[N + 1];
    rep(i, N + 1) d1[i] = INF;
    bfs(G, 0, d1);
    
    // 4. 町 N からの 最短距離.
    int d2[N + 1];
    rep(i, N + 1) d2[i] = INF;
    bfs(G, N - 1, d2);
    
    // 5. 各町ごとに出力.
    rep(i, N){
        // 特殊テレポーターを使わない経路.
        int ans1 = d1[N - 1];
        
        // 特殊テレポーターを, 町 i -> 町 (N + 1) で使う経路.
        int ans2 = d1[i] + d2[N];
        
        // 特殊テレポーターを, 町 (N + 1) -> 町 i で使う経路.
        int ans3 = d1[N] + d2[i];
        
        // 出力.
        int ans = min({ans1, ans2, ans3});
        printf("%d%s", (ans >= INF) ? -1 : ans, (i < N - 1) ? " " : "\n");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc257/editorial/4183

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

const int INF = 20202020;

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N + 1);

rep(i, M){

int u, v;

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

--v;

// 仮想頂点と可変テレポーターを結ぶ.

if(!u){

G[N].pb(v);

G[v].pb(N);

}

// 通常のグラフ作成.

if(u){

--u;

G[u].pb(v);

G[v].pb(u);

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 隣接頂点をチェック.

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

}

};

// 3. 町 1 からの最短距離.

int d1[N + 1];

rep(i, N + 1) d1[i] = INF;

bfs(G, 0, d1);

// 4. 町 N からの最短距離.

int d2[N + 1];

rep(i, N + 1) d2[i] = INF;

bfs(G, N - 1, d2);

// 5. 各町ごとに出力.

rep(i, N){

// 特殊テレポーターを使わない経路.

int ans1 = d1[N - 1];

// 特殊テレポーターを, 町 i -> 町 (N + 1) で使う経路.

int ans2 = d1[i] + d2[N];

// 特殊テレポーターを, 町 (N + 1) -> 町 i で使う経路.

int ans3 = d1[N] + d2[i];

// 出力.

int ans = min({ans1, ans2, ans3});

printf("%d%s", (ans >= INF) ? -1 : ans, (i < N - 1) ? " " : "\n");

}

return 0;

}

[入力例]
3 2
0 2
1 2

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

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

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

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

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

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

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

[入力例]

3 2

0 2

1 2

[出力例]

-1 -1 2

※AtCoderテストケースより

[入力例]

5 5

1 2

1 3

3 4

4 5

0 2

[出力例]

3 3 3 3 2

※AtCoderテストケースより

[入力例]

7 8

1 3

2 5

2 7

4 6

0 4

0 3

0 5

0 7

[出力例]

1 3 2 3 3 3 2

[入力例]

10 10

1 5

2 4

2 5

3 6

3 9

6 7

9 10

0 2

0 7

0 8

[出力例]

5 7 5 8 6 6 7 8 4 3

■参照サイト
日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257）

2022年6月30日2022年6月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 118 の問題C (Coprime Set) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 解説のロジックで, 条件を満たす整数を抽出できる点が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 基準とする集合.
    set<int> st = {6, 10, 15};
    
    // 3. 6 の 倍数.
    int n = 1;
    while(st.size() < N && (n + 1) * 6 <= 10000) st.insert(++n * 6);
    
    // 4. 10 の 倍数.
    n = 1;
    while(st.size() < N && (n + 1) * 10 <= 10000) st.insert(++n * 10);
    
    // 5. 15 の 倍数.
    n = 1;
    while(st.size() < N && (n + 1) * 15 <= 10000) st.insert(++n * 15);
    
    // 6. 最大公約数チェック.
    int g = 6;
    vi ans;
    for(auto &p : st){
        ans.pb(p);
        g = __gcd(g, p);
    }
    assert(g == 1);
    
    // 7. 出力.
    rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc118/editorial/1206

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 基準とする集合.

set<int> st = {6, 10, 15};

// 3. 6 の倍数.

int n = 1;

while(st.size() < N && (n + 1) * 6 <= 10000) st.insert(++n * 6);

// 4. 10 の倍数.

n = 1;

while(st.size() < N && (n + 1) * 10 <= 10000) st.insert(++n * 10);

// 5. 15 の倍数.

n = 1;

while(st.size() < N && (n + 1) * 15 <= 10000) st.insert(++n * 15);

// 6. 最大公約数チェック.

int g = 6;

vi ans;

for(auto &p : st){

ans.pb(p);

g = __gcd(g, p);

}

assert(g == 1);

// 7. 出力.

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

return 0;

}

[入力例]
4

[出力例]
84 60 105 70
※AtCoderテストケースより

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

[入力例]
3

[出力例]
6 10 15

[入力例]
5

[出力例]
6 10 12 15 18

[入力例]
10

[出力例]
6 10 12 15 18 24 30 36 42 48

[入力例]
15

[出力例]
6 10 12 15 18 24 30 36 42 48 54 60 66 72 78

[入力例]
100

[出力例]
6 10 12 15 18 24 30 36 42 48 54 60 66 72 78 84 90 96 102 108 114 120 126 132 138 144 150 156 162 168 174 180 186 192 198 204 210 216 222 228 234 240 246 252 258 264 270 276 282 288 294 300 306 312 318 324 330 336 342 348 354 360 366 372 378 384 390 396 402 408 414 420 426 432 438 444 450 456 462 468 474 480 486 492 498 504 510 516 522 528 534 540 546 552 558 564 570 576 582 588

[入力例]

[出力例]

84 60 105 70

※AtCoderテストケースより

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

6 10 12 15

[入力例]

[出力例]

6 10 15

[入力例]

[出力例]

6 10 12 15 18

[入力例]

[出力例]

6 10 12 15 18 24 30 36 42 48

[入力例]

[出力例]

6 10 12 15 18 24 30 36 42 48 54 60 66 72 78

[入力例]

100

[出力例]

6 10 12 15 18 24 30 36 42 48 54 60 66 72 78 84 90 96 102 108 114 120 126 132 138 144 150 156 162 168 174 180 186 192 198 204 210 216 222 228 234 240 246 252 258 264 270 276 282 288 294 300 306 312 318 324 330 336 342 348 354 360 366 372 378 384 390 396 402 408 414 420 426 432 438 444 450 456 462 468 474 480 486 492 498 504 510 516 522 528 534 540 546 552 558 564 570 576 582 588

■参照サイト
AtCoder Regular Contest 118

2022年6月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 155 の問題D (Pairs) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc155/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    LL K, a;
    vl vm, vp, vz;
    scanf("%d %lld", &N, &K);
    rep(i, N){
        scanf("%lld", &a);
        if(a < 0) vm.pb(-a);
        if(a > 0) vp.pb(a);
        if(a == 0) vz.pb(0);
    }
    
    // 2. 負, 零, 正 の ペア.
    // 負: 1          ～ mCount
    // 零: mCount + 1 ～ zCount
    // 正: zCount + 1 ～ (LL)N * (LL)(N - 1) / 2
    LL nm = vm.size();
    LL np = vp.size();
    LL nz = vz.size();
    LL mCount = nm * np;
    LL zCount = mCount + nz * (nz - 1) / 2 + nz * (LL)(N - nz);
    
    // 3. sort.
    sort(all(vm));
    sort(all(vp));
    
    // 4. K 番目 が 負.
    if(K <= mCount){
        // 4-1. 評価関数.
        auto f = [&](LL X) -> bool {
            // ペアで, X以上となる個数.
            LL ret = 0;
            rep(i, nm){
                LL q = X / vm[i];
                int at = lower_bound(all(vp), q) - vp.begin();
                while(at < np && vm[i] * vp[at] < X) ++at;
                ret += np - at;
            }
            
            // 判定結果.
            return (ret >= K);
        };
        
        // 4-2. 二分探索で確認してみる.
        LL l = 0, h = 2e18 + 1, m;
        while(l + 1 < h){
            LL m = (h + l) >> 1LL;
            if(f(m)) l = m;
            else     h = m;
            // printf("h=%lld l=%lld m=%lld\n", h, l, m);
        }
        
        // 4-3. 出力.
        printf("%lld\n", -l);
    }
    
    // 5. K 番目 が 零.
    if(K > mCount && K <= zCount) puts("0");
    
    // 6. K 番目 が 正.
    if(K > zCount){
        // 6-1. 評価関数.
        auto f = [&](LL X) -> bool {
            // ペアで, X以上となる個数(負).
            LL ret = 0;
            rep(i, nm){
                LL q = X / vm[i];
                int at = lower_bound(all(vm), q) - vm.begin();
                while(at < nm && vm[i] * vm[at] < X) ++at;
                ret += nm - max(at, i + 1);
            }
            
            // ペアで, X以上となる個数(正).
            rep(i, np){
                LL q = X / vp[i];
                int at = lower_bound(all(vp), q) - vp.begin();
                while(at < np && vp[i] * vp[at] < X) ++at;
                ret += np - max(at, i + 1);
            }
            
            // 判定結果.
            return (ret >= (LL)N * (LL)(N - 1) / 2 - K + 1);
        };
        
        // 6-2. 二分探索で確認してみる.
        LL l = 0, h = 2e18 + 1, m;
        while(l + 1 < h){
            LL m = (h + l) >> 1LL;
            if(f(m)) l = m;
            else     h = m;
            // printf("h=%lld l=%lld m=%lld\n", h, l, m);
        }
        
        // 6-3. 出力.
        printf("%lld\n", l);
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

int N;

LL K, a;

vl vm, vp, vz;

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

rep(i, N){

scanf("%lld", &a);

if(a < 0) vm.pb(-a);

if(a > 0) vp.pb(a);

if(a == 0) vz.pb(0);

}

// 2. 負, 零, 正のペア.

// 負: 1 ～ mCount

// 零: mCount + 1 ～ zCount

// 正: zCount + 1 ～ (LL)N * (LL)(N - 1) / 2

LL nm = vm.size();

LL np = vp.size();

LL nz = vz.size();

LL mCount = nm * np;

LL zCount = mCount + nz * (nz - 1) / 2 + nz * (LL)(N - nz);

// 3. sort.

sort(all(vm));

sort(all(vp));

// 4. K 番目が負.

if(K <= mCount){

// 4-1. 評価関数.

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

// ペアで, X以上となる個数.

LL ret = 0;

rep(i, nm){

LL q = X / vm[i];

int at = lower_bound(all(vp), q) - vp.begin();

while(at < np && vm[i] * vp[at] < X) ++at;

ret += np - at;

}

// 判定結果.

return (ret >= K);

};

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

LL l = 0, h = 2e18 + 1, m;

while(l + 1 < h){

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

if(f(m)) l = m;

else h = m;

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

}

// 4-3. 出力.

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

}

// 5. K 番目が零.

if(K > mCount && K <= zCount) puts("0");

// 6. K 番目が正.

if(K > zCount){

// 6-1. 評価関数.

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

// ペアで, X以上となる個数(負).

LL ret = 0;

rep(i, nm){

LL q = X / vm[i];

int at = lower_bound(all(vm), q) - vm.begin();

while(at < nm && vm[i] * vm[at] < X) ++at;

ret += nm - max(at, i + 1);

}

// ペアで, X以上となる個数(正).

rep(i, np){

LL q = X / vp[i];

int at = lower_bound(all(vp), q) - vp.begin();

while(at < np && vp[i] * vp[at] < X) ++at;

ret += np - max(at, i + 1);

}

// 判定結果.

return (ret >= (LL)N * (LL)(N - 1) / 2 - K + 1);

};

// 6-2. 二分探索で確認してみる.

LL l = 0, h = 2e18 + 1, m;

while(l + 1 < h){

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

if(f(m)) l = m;

else h = m;

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

}

// 6-3. 出力.

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

}

return 0;

}

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

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

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

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

[入力例]
30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

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

[入力例]
32 100
6 -4 1 11 9 6 7 -6 4 3 11 4 9 -4 5 0 -6 -5 11 0 -8 6 -5 8 11 -10 6 5 4 10 -9 6

[出力例]
-36

[入力例]
100 2022
61 54 58 86 116 5 22 99 57 96 66 23 -66 -8 84 -112 99 15 15 61 18 39 19 -4 30 79 3 54 -84 101 68 55 42 48 70 85 14 1 60 2 38 25 0 66 110 8 122 95 105 54 47 8 57 0 113 0 69 72 11 28 77 10 4 92 15 100 111 75 -114 69 -55 68 115 -98 103 -88 96 62 76 39 15 23 13 107 67 101 100 104 59 122 -22 116 18 87 119 121 96 48 46 37

[出力例]
810

[入力例]
500 123456
9335 3944 3417 4250 11000 5835 -10891 5495 2109 4495 1512 976 11827 8877 8514 7942 8991 642 2459 1567 -11710 5827 10069 7089 5160 2361 1851 11615 7462 2511 6510 9731 -2596 -9952 10391 6923 11173 8934 3891 4978 11855 4164 -10466 3346 7092 3505 3669 123 7658 -11383 5487 9148 8546 9899 -1748 11251 11662 6712 11364 4217 8934 5624 3530 10779 5004 10737 3559 12145 3905 11180 307 10907 1420 648 6141 8981 -10137 705 8542 -10782 851 46 3111 5739 9808 910 7272 3690 4042 11167 572 11661 10423 3593 6812 7501 -12021 10112 -11188 -7773 4252 7439 1518 5973 6619 2976 3564 6070 2273 6745 5361 9472 932 4624 3861 1975 4616 8289 6416 5693 10601 9241 6184 2230 5242 7116 11063 -9305 8582 6848 6082 11589 10273 3721 -11313 6430 5217 1278 4734 11468 9379 5170 6300 -573 10122 3157 -4433 6667 7636 5556 -5632 7591 10277 9515 875 2057 2171 -12043 11848 100 7520 8304 8985 9323 1401 3588 9434 6842 9175 2262 4764 4976 9345 10830 8318 7875 9732 12322 8453 4908 3128 3915 8852 8211 8038 10484 476 6113 4469 1125 7068 -1025 3946 9268 9781 6543 2111 9918 -7381 753 998 12065 6851 10543 -4516 9740 1996 1267 3318 1168 1698 756 7591 1193 -10789 4680 -10749 2717 8364 1709 7056 313 -12043 7427 1922 10593 2707 8311 6788 2813 3342 6921 11480 7225 7425 4613 7238 6576 2287 6908 -6357 10794 11999 4226 8213 1878 -1892 1177 10463 8186 -11557 11051 1662 9945 8059 9921 3462 9390 8277 5947 4396 2081 9825 -4092 11293 11834 9337 909 8200 6236 11053 11505 11909 9464 7190 654 889 3779 12183 8962 11940 8112 8421 9701 4286 5259 4151 -1655 8782 5989 6652 2605 3278 7442 9091 4828 10335 4303 692 3046 10991 4897 1120 5681 3194 7806 -7807 1434 11209 147 9057 -5880 4630 4956 3426 12087 -3982 -11836 7248 574 7828 10259 1989 3601 1159 11069 8723 9463 -10726 480 1994 3501 6181 3574 7705 -9485 3239 365 5479 11394 6226 3992 3518 -10092 3467 3344 7689 4032 6358 7667 8296 4997 5351 4806 7274 6360 8812 -2507 -4692 -5065 2396 12112 6426 1621 7241 3169 -4416 10127 784 1122 9859 -10271 9159 10223 6047 12146 4507 4766 2018 2046 7446 1055 3004 8453 6973 775 8296 1997 3348 7894 505 4162 1984 4140 10912 -10471 7963 4503 2614 10364 8667 2130 5784 3578 3130 8981 -12323 2411 8183 8241 -8861 1923 2680 8126 3885 -9200 -6852 -10541 7872 1231 -8718 451 478 3441 -10802 10017 4217 7088 9451 -9700 10607 4292 8920 -10601 9517 -5043 1101 -13108 8274 7536 8908 8500 5864 -10837 8651 1642 6122 -11759 11413 11317 2536 -4625 -4658 7541 528 -10230 -7926 9626 10548 10155 7766 2005 -7346 10132 8516 -10853 551 7515 5526 10232 10205 1002 10570 -8776 -11922 5902 7924 3858 2967 -1777 7246 1502 785 10691 12053 94 7334 7377 -10656 40 2597 3327 4805 3781 9262 -10589 7053 12320 6780 -7329

[出力例]
123934756

[入力例]

4 3

3 3 -4 -2

[出力例]

-6

※AtCoderテストケースより

[入力例]

10 40

5 4 3 2 -1 0 0 0 0 0

[出力例]

※AtCoderテストケースより

[入力例]

30 413

-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

[出力例]

448283280358331064

※AtCoderテストケースより

[入力例]

32 100

6 -4 1 11 9 6 7 -6 4 3 11 4 9 -4 5 0 -6 -5 11 0 -8 6 -5 8 11 -10 6 5 4 10 -9 6

[出力例]

-36

[入力例]

100 2022

61 54 58 86 116 5 22 99 57 96 66 23 -66 -8 84 -112 99 15 15 61 18 39 19 -4 30 79 3 54 -84 101 68 55 42 48 70 85 14 1 60 2 38 25 0 66 110 8 122 95 105 54 47 8 57 0 113 0 69 72 11 28 77 10 4 92 15 100 111 75 -114 69 -55 68 115 -98 103 -88 96 62 76 39 15 23 13 107 67 101 100 104 59 122 -22 116 18 87 119 121 96 48 46 37

[出力例]

810

[入力例]

500 123456

9335 3944 3417 4250 11000 5835 -10891 5495 2109 4495 1512 976 11827 8877 8514 7942 8991 642 2459 1567 -11710 5827 10069 7089 5160 2361 1851 11615 7462 2511 6510 9731 -2596 -9952 10391 6923 11173 8934 3891 4978 11855 4164 -10466 3346 7092 3505 3669 123 7658 -11383 5487 9148 8546 9899 -1748 11251 11662 6712 11364 4217 8934 5624 3530 10779 5004 10737 3559 12145 3905 11180 307 10907 1420 648 6141 8981 -10137 705 8542 -10782 851 46 3111 5739 9808 910 7272 3690 4042 11167 572 11661 10423 3593 6812 7501 -12021 10112 -11188 -7773 4252 7439 1518 5973 6619 2976 3564 6070 2273 6745 5361 9472 932 4624 3861 1975 4616 8289 6416 5693 10601 9241 6184 2230 5242 7116 11063 -9305 8582 6848 6082 11589 10273 3721 -11313 6430 5217 1278 4734 11468 9379 5170 6300 -573 10122 3157 -4433 6667 7636 5556 -5632 7591 10277 9515 875 2057 2171 -12043 11848 100 7520 8304 8985 9323 1401 3588 9434 6842 9175 2262 4764 4976 9345 10830 8318 7875 9732 12322 8453 4908 3128 3915 8852 8211 8038 10484 476 6113 4469 1125 7068 -1025 3946 9268 9781 6543 2111 9918 -7381 753 998 12065 6851 10543 -4516 9740 1996 1267 3318 1168 1698 756 7591 1193 -10789 4680 -10749 2717 8364 1709 7056 313 -12043 7427 1922 10593 2707 8311 6788 2813 3342 6921 11480 7225 7425 4613 7238 6576 2287 6908 -6357 10794 11999 4226 8213 1878 -1892 1177 10463 8186 -11557 11051 1662 9945 8059 9921 3462 9390 8277 5947 4396 2081 9825 -4092 11293 11834 9337 909 8200 6236 11053 11505 11909 9464 7190 654 889 3779 12183 8962 11940 8112 8421 9701 4286 5259 4151 -1655 8782 5989 6652 2605 3278 7442 9091 4828 10335 4303 692 3046 10991 4897 1120 5681 3194 7806 -7807 1434 11209 147 9057 -5880 4630 4956 3426 12087 -3982 -11836 7248 574 7828 10259 1989 3601 1159 11069 8723 9463 -10726 480 1994 3501 6181 3574 7705 -9485 3239 365 5479 11394 6226 3992 3518 -10092 3467 3344 7689 4032 6358 7667 8296 4997 5351 4806 7274 6360 8812 -2507 -4692 -5065 2396 12112 6426 1621 7241 3169 -4416 10127 784 1122 9859 -10271 9159 10223 6047 12146 4507 4766 2018 2046 7446 1055 3004 8453 6973 775 8296 1997 3348 7894 505 4162 1984 4140 10912 -10471 7963 4503 2614 10364 8667 2130 5784 3578 3130 8981 -12323 2411 8183 8241 -8861 1923 2680 8126 3885 -9200 -6852 -10541 7872 1231 -8718 451 478 3441 -10802 10017 4217 7088 9451 -9700 10607 4292 8920 -10601 9517 -5043 1101 -13108 8274 7536 8908 8500 5864 -10837 8651 1642 6122 -11759 11413 11317 2536 -4625 -4658 7541 528 -10230 -7926 9626 10548 10155 7766 2005 -7346 10132 8516 -10853 551 7515 5526 10232 10205 1002 10570 -8776 -11922 5902 7924 3858 2967 -1777 7246 1502 785 10691 12053 94 7334 7377 -10656 40 2597 3327 4805 3781 9262 -10589 7053 12320 6780 -7329

[出力例]

123934756

■参照サイト
AtCoder Beginner Contest 155

2022年6月26日

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

C++の練習を兼ねて, AtCoder Beginner Contest 257 の問題E (Addition and Multiplication 2) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc257/editorial/4136
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N, cMin = 2020202020, b = 0;
    scanf("%d", &N);
    map<int, int> m;
    rep(i, 9){
        int c;
        scanf("%d", &c);
        m[c] = i + 1;
        if(cMin >= c){
            cMin = c;
            b = i + 1;
        }
    }
    
    // 2. 利用可能な金額.
    vp o;
    for(auto &p : m) if(p.a < cMin * 2) o.pb({p.a, p.b});
    
    // 3. 桁数.
    int n = N / cMin;
    
    // 4. 貪欲法.
    string ans = "";
    int bef = 0;
    rep(i, n){
        // i 桁目(候補).
        // -> なるべく大きな i 桁目 の 候補は？
        int d = 0, cur;
        for(auto &p : o){
            if(p.b > d && bef + p.a + cMin * (n - i - 1) <= N){
                d = p.b;
                cur = bef + p.a;
            }
        }
        
        // i 桁目.
        ans.pb(d + '0');
        
        // 前回分更新.
        bef = cur;
    }
    
    // 5. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc257/editorial/4136

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int N, cMin = 2020202020, b = 0;

scanf("%d", &N);

map<int, int> m;

rep(i, 9){

int c;

scanf("%d", &c);

m[c] = i + 1;

if(cMin >= c){

cMin = c;

b = i + 1;

}

// 2. 利用可能な金額.

vp o;

for(auto &p : m) if(p.a < cMin * 2) o.pb({p.a, p.b});

// 3. 桁数.

int n = N / cMin;

// 4. 貪欲法.

string ans = "";

int bef = 0;

rep(i, n){

// i 桁目(候補).

// -> なるべく大きな i 桁目の候補は？

int d = 0, cur;

for(auto &p : o){

if(p.b > d && bef + p.a + cMin * (n - i - 1) <= N){

d = p.b;

cur = bef + p.a;

}

// i 桁目.

ans.pb(d + '0');

// 前回分更新.

bef = cur;

}

// 5. 出力.

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

return 0;

}

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

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

[入力例]
20
1 1 1 1 1 1 1 1 1

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

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

[出力例]
766666

[入力例]
256
31 41 5 9 26 53 5 8 9

[出力例]
777777777777777777777777777777777777777777777777777

[入力例]
2022
13 33 18 27 32 31 14 15 31

[出力例]
88871111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

[入力例]
2022
13 33 18 27 32 31 14 15 16

[出力例]
99711111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

[入力例]
12345
896 789 776 1327 735 743 770 836 1270

[出力例]
9765555555555555

[入力例]
20220625
68650 68661 68727 95533 93697 69078 70325 85841 129387

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

[入力例]

5 4 3 3 2 5 3 5 3

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1 1 1 1 1 1 1

[出力例]

99999999999999999999

※AtCoderテストケースより

[入力例]

12 5 6 9 10 2 3 7 5

[出力例]

766666

[入力例]

256

31 41 5 9 26 53 5 8 9

[出力例]

777777777777777777777777777777777777777777777777777

[入力例]

2022

13 33 18 27 32 31 14 15 31

[出力例]

88871111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

[入力例]

2022

13 33 18 27 32 31 14 15 16

[出力例]

99711111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

[入力例]

12345

896 789 776 1327 735 743 770 836 1270

[出力例]

9765555555555555

[入力例]

20220625

68650 68661 68727 95533 93697 69078 70325 85841 129387

[出力例]

887666332211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

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

■参照サイト
日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257）

2022年6月26日2022年6月26日

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

C++の練習を兼ねて, AtCoder Beginner Contest 257 の問題C (Robot Takahashi) ～問題D (Jumping Takahashi 2) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    char c[202020];
    scanf("%d %s", &N, c);
    vi va, vc;
    rep(i, N){
        int w;
        scanf("%d", &w);
        if(c[i] == '0') vc.pb(w);
        if(c[i] == '1') va.pb(w);
    }
    
    // 2. 例外.
    int nc = vc.size(), na = va.size();
    if(nc == 0 || na == 0){
        printf("%d\n", N);
        return 0;
    }
    
    // 3. sort.
    sort(all(vc));
    sort(all(va));
    
    // 4. カウント(子供視点).
    // 4-1. 最終要素まで.
    int ans = 0;
    rep(i, nc){
        int x = vc[i];
        int cAt1 = upper_bound(all(vc), x - 1) - vc.begin();
        int cAt2 = lower_bound(all(va), x) - va.begin();
        ans = max(ans, cAt1 + na - cAt2);
    }
    
    // 4-2. 最終要素 より, 1 大きい.
    int x = vc.back() + 1;
    int cAt1 = upper_bound(all(vc), x - 1) - vc.begin();
    int cAt2 = lower_bound(all(va), x) - va.begin();
    ans = max(ans, cAt1 + na - cAt2);
    
    // 5. カウント(大人視点).
    // 5-1. 最終要素まで.
    rep(i, na){
        int y = va[i];
        int aAt1 = upper_bound(all(vc), y - 1) - vc.begin();
        int aAt2 = lower_bound(all(va), y) - va.begin();
        ans = max(ans, aAt1 + na - aAt2);
    }
    
    // 5-2. 最終要素 より, 1 大きい.
    int y = va.back() + 1;
    int aAt1 = upper_bound(all(vc), y - 1) - vc.begin();
    int aAt2 = lower_bound(all(va), y) - va.begin();
    ans = max(ans, aAt1 + na - aAt2);
    
    // 6. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

int N;

char c[202020];

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

vi va, vc;

rep(i, N){

int w;

scanf("%d", &w);

if(c[i] == '0') vc.pb(w);

if(c[i] == '1') va.pb(w);

}

// 2. 例外.

int nc = vc.size(), na = va.size();

if(nc == 0 || na == 0){

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

return 0;

}

// 3. sort.

sort(all(vc));

sort(all(va));

// 4. カウント(子供視点).

// 4-1. 最終要素まで.

int ans = 0;

rep(i, nc){

int x = vc[i];

int cAt1 = upper_bound(all(vc), x - 1) - vc.begin();

int cAt2 = lower_bound(all(va), x) - va.begin();

ans = max(ans, cAt1 + na - cAt2);

}

// 4-2. 最終要素より, 1 大きい.

int x = vc.back() + 1;

int cAt1 = upper_bound(all(vc), x - 1) - vc.begin();

int cAt2 = lower_bound(all(va), x) - va.begin();

ans = max(ans, cAt1 + na - cAt2);

// 5. カウント(大人視点).

// 5-1. 最終要素まで.

rep(i, na){

int y = va[i];

int aAt1 = upper_bound(all(vc), y - 1) - vc.begin();

int aAt2 = lower_bound(all(va), y) - va.begin();

ans = max(ans, aAt1 + na - aAt2);

}

// 5-2. 最終要素より, 1 大きい.

int y = va.back() + 1;

int aAt1 = upper_bound(all(vc), y - 1) - vc.begin();

int aAt2 = lower_bound(all(va), y) - va.begin();

ans = max(ans, aAt1 + na - aAt2);

// 6. 出力.

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

return 0;

}

[入力例]
5
10101
60 45 30 40 80

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

[入力例]
3
000
1 2 3

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

[入力例]
5
10101
60 50 50 50 60

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

[入力例]
20
01100000111100111000
18 8 6 7 19 4 15 4 12 25 18 4 21 14 22 4 16 16 4 1

[出力例]
13

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

[出力例]
33

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

[出力例]
300

[入力例]

10101

60 45 30 40 80

[出力例]

※AtCoderテストケースより

[入力例]

000

1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

10101

60 50 50 50 60

[出力例]

※AtCoderテストケースより

[入力例]

01100000111100111000

18 8 6 7 19 4 15 4 12 25 18 4 21 14 22 4 16 16 4 1

[出力例]

[入力例]

10010101111110001010011000001110111010001010110101

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

[出力例]

[入力例]

500

01110010001101001111001111001101010101011101001101111100101000010011010101111000111000011010111100100100000101100111100011110000111110001010011000101000110110001111110010100011110010111100110000111000011011010100100100010000011010001001100101000100001111100001110010010111100011101001100000101101011000101101110000111111111100011101011011001010100001001110110111101001110000000000110001100101100011000000100010000000110011110110110111100000110001001110010001011000001000111001110111010111000111101000

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

[出力例]

300

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

// 解き直し.
// https://atcoder.jp/contests/abc257/editorial/4166
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using T3 = tuple<LL, LL, LL>;
using vt = vector<T3>;
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 main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vt t;
    rep(i, N){
        LL x, y, p;
        scanf("%lld %lld %lld", &x, &y, &p);
        t.emplace_back(x, y, p);
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d) {
        // 空のキュー.
        queue<int> q;
        
        // 開始地点は, 距離ゼロ.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(d[e] == INF && e != s) d[e] = d[u] + 1, q.push(e);
        }
    };
    
    // 3. 評価関数.
    auto f = [&](LL x, int s) -> bool {
        // 3-1. グラフ作成.
        vvi G(N);
        rep(i, N){
            rep(j, N){
                if(i == j) continue;
                LL p = get<2>(t[i]);
                LL xi = get<0>(t[i]);
                LL yi = get<1>(t[i]);
                LL xj = get<0>(t[j]);
                LL yj = get<1>(t[j]);
                
                // 有向辺追加.
                if(x * p >= abs(xi - xj) + abs(yi - yj)) G[i].pb(j);
            }
        }
        
        // 3-2. 各頂点までの最短距離は？
        int d[N];
        rep(i, N) d[i] = INF;
        bfs(G, s, d);
        
        // 3-3. 到達できない頂点があれば, 判定結果は, NG.
        rep(i, N) if(d[i] == INF) return false;
        
        // 3-4. 判定結果(OK).
        return true;
    };
    
    // 4. 各ジャンプ台を, 始点として確認.
    LL ans = 1e18 + 1;
    rep(i, N){
        // 4-1. 二分探索で確認してみる(01_random_02.txt WA回避のため, 上限 を 修正).
       LL l = -1, h = (LL)(1e10 + 1);
        while(l + 1 < h){
            LL m = (h + l) >> 1;
            if(f(m, i)) h = m;
            else        l = m;
            // printf("h=%lld l=%lld m=%lld\n", h, l, m);
        }
        
        // 4-2. 最小値更新.
        ans = min(ans, h);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

// 解き直し.

// https://atcoder.jp/contests/abc257/editorial/4166

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

using vt = vector<T3>;

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

// 1. 入力情報.

int N;

scanf("%d", &N);

vt t;

rep(i, N){

LL x, y, p;

scanf("%lld %lld %lld", &x, &y, &p);

t.emplace_back(x, y, p);

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 隣接頂点をチェック.

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

}

};

// 3. 評価関数.

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

// 3-1. グラフ作成.

vvi G(N);

rep(i, N){

rep(j, N){

if(i == j) continue;

LL p = get<2>(t[i]);

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

LL yi = get<1>(t[i]);

LL xj = get<0>(t[j]);

LL yj = get<1>(t[j]);

// 有向辺追加.

if(x * p >= abs(xi - xj) + abs(yi - yj)) G[i].pb(j);

}

// 3-2. 各頂点までの最短距離は？

int d[N];

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

bfs(G, s, d);

// 3-3. 到達できない頂点があれば, 判定結果は, NG.

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

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

return true;

};

// 4. 各ジャンプ台を, 始点として確認.

LL ans = 1e18 + 1;

rep(i, N){

// 4-1. 二分探索で確認してみる(01_random_02.txt WA回避のため, 上限を修正).

LL l = -1, h = (LL)(1e10 + 1);

while(l + 1 < h){

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

if(f(m, i)) h = m;

else l = m;

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

}

// 4-2. 最小値更新.

ans = min(ans, h);

}

// 5. 出力.

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

return 0;

}

[入力例]
4
-10 0 1
0 0 5
10 0 1
11 0 1

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

[入力例]
7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

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

[入力例]
2
1000000000 -1000000000 1
-1000000000 1000000000 1

[出力例]
4000000000

[入力例]
2
5 -11 3
7 10 2

[出力例]
8

[入力例]
5
19 11 5
-20 15 3
17 23 7
20 -1 11
-31 8 5

[出力例]
6

[入力例]
12
15 25 1
39 8 2
39 1 8
11 23 6
32 7 2
7 2 2
31 26 1
50 0 9
40 31 6
31 12 7
39 9 9
41 8 2

[出力例]
5

[入力例]
20
61 117 7
105 -42 10
108 19 8
115 40 1
44 -117 4
88 113 6
-82 30 9
90 26 12
7 117 3
-28 38 7
90 50 4
117 -61 2
97 -3 10
48 47 18
103 96 2
-26 28 5
11 83 13
84 90 11
55 -121 6
67 119 8

[出力例]
10

[入力例]
50
114826816 82519150 6268
12619116 120467525 1933
-54631995 55776049 2561
88550491 -5015087 10811
73166962 10866346 5507
18962497 -31770244 455
66735709 79304028 6856
-24040554 104695951 5157
8572736 855152 1891
33316757 85245979 6791
90140520 -42894360 4142
-111400647 36917981 8805
66830104 86440296 12077
120893655 46441247 3373
44730385 100628985 8032
-20570340 78653521 9343
99140500 36018937 6700
52408530 90992130 3145
90388276 95623765 5390
114943431 -32374556 8835
122632077 17107169 6263
92383853 -111744501 6213
55578000 46109416 1508
13518989 -77004646 8944
-63657253 34875699 8272
85925462 103245186 4572
106193136 78153142 3674
39842806 114117953 10934
69038936 4613269 6446
-84568400 24860434 10797
6483886 77568171 7455
27752939 103955066 7157
-24027241 56901240 4622
111243292 -71222874 9828
31581048 65522484 8512
113900134 -87365771 8889
77984052 63912975 3894
121103638 117798519 12197
91188226 33868808 10223
15144083 89296569 12263
120632877 -24974624 12966
29091477 113080664 8081
29899286 81579179 3818
29476643 121878926 8319
100429020 121005105 12294
18324115 95287004 8707
106407288 61242219 9409
90704153 -64757691 5806
54331027 29355424 3050
101391511 31441797 3528

[出力例]
10000

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

[入力例]

-10 0 1

0 0 5

10 0 1

11 0 1

[出力例]

※AtCoderテストケースより

[入力例]

20 31 1

13 4 3

-10 -15 2

34 26 5

-2 39 4

0 -50 1

5 -20 2

[出力例]

※AtCoderテストケースより

[入力例]

1000000000 -1000000000 1

-1000000000 1000000000 1

[出力例]

4000000000

[入力例]

5 -11 3

7 10 2

[出力例]

[入力例]

19 11 5

-20 15 3

17 23 7

20 -1 11

-31 8 5

[出力例]

[入力例]

15 25 1

39 8 2

39 1 8

11 23 6

32 7 2

7 2 2

31 26 1

50 0 9

40 31 6

31 12 7

39 9 9

41 8 2

[出力例]

[入力例]

61 117 7

105 -42 10

108 19 8

115 40 1

44 -117 4

88 113 6

-82 30 9

90 26 12

7 117 3

-28 38 7

90 50 4

117 -61 2

97 -3 10

48 47 18

103 96 2

-26 28 5

11 83 13

84 90 11

55 -121 6

67 119 8

[出力例]

[入力例]

114826816 82519150 6268

12619116 120467525 1933

-54631995 55776049 2561

88550491 -5015087 10811

73166962 10866346 5507

18962497 -31770244 455

66735709 79304028 6856

-24040554 104695951 5157

8572736 855152 1891

33316757 85245979 6791

90140520 -42894360 4142

-111400647 36917981 8805

66830104 86440296 12077

120893655 46441247 3373

44730385 100628985 8032

-20570340 78653521 9343

99140500 36018937 6700

52408530 90992130 3145

90388276 95623765 5390

114943431 -32374556 8835

122632077 17107169 6263

92383853 -111744501 6213

55578000 46109416 1508

13518989 -77004646 8944

-63657253 34875699 8272

85925462 103245186 4572

106193136 78153142 3674

39842806 114117953 10934

69038936 4613269 6446

-84568400 24860434 10797

6483886 77568171 7455

27752939 103955066 7157

-24027241 56901240 4622

111243292 -71222874 9828

31581048 65522484 8512

113900134 -87365771 8889

77984052 63912975 3894

121103638 117798519 12197

91188226 33868808 10223

15144083 89296569 12263

120632877 -24974624 12966

29091477 113080664 8081

29899286 81579179 3818

29476643 121878926 8319

100429020 121005105 12294

18324115 95287004 8707

106407288 61242219 9409

90704153 -64757691 5806

54331027 29355424 3050

101391511 31441797 3528

[出力例]

10000

■参照サイト
日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257）

2022年6月24日2022年6月24日

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

C++の練習を兼ねて, AtCoder Beginner Contest 158 の問題E (Divisible Substring) を解いてみた.

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

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

// 解き直し.
// https://img.atcoder.jp/abc158/editorial.pdf
// 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 N, P;
    char c[202020];
    scanf("%d %d %s", &N, &P, c);
    string s(c);
    int ns = s.size();
    LL ans = 0;
    
    // 2. P = 2, 5 の 場合.
    if(P == 2 || P == 5){
        // 2-1. 右端が, P の 倍数か？
        repr(i, ns - 1, 0) if((s[i] - '0') % P == 0) ans += (LL)(i + 1);
        
        // 2-2. 出力.
        printf("%lld\n", ans);
        return 0;
    }
    
    // 3. 上記以外.
    // 3-1. 10 の べき乗.
    int mPow10[ns];
    mPow10[ns - 1] = 1;
    repr(i, ns - 2, 0) mPow10[i] = mPow10[i + 1] * 10 % P;
    
    // 3-2. U[i] (mod P) の 個数は？
    map<int, int> uCount;
    int u = 0;
    repr(i, ns - 1, 0){
        u += mPow10[i] * (s[i] - '0');
        u %= P;
        ++uCount[u];
    }
    
    // 3-3. 集計.
    map<int, int> xCount;
    int x = 0;
    repr(i, ns - 1, 0){
        x += mPow10[i] * (s[i] - '0');
        x %= P;
        ++xCount[x];
        
        // x が 0 は, 自分自身もカウント対象なので, 注意.
        // ex.
        // N = 6 P = 7 S = 728105 の場合, 
        //      5 -> 7 の 倍数 でない -> 05 - 5 = 0 が 7 の倍数となるので, 1 を 加算.
        //     05 -> 7 の 倍数 でない -> 05 は 7 の倍数でないので, 0 を 加算.
        //    105 -> 7 の 倍数 である -> 728105, 28105, 105(自分自身) から, 
        //                              それぞれ 105 を 減算したものが 7 の 倍数なので, 3 を 加算.
        //   8105 -> 7 の 倍数 でない -> 8105 は 7 の倍数でないので, 0 を 加算.
        //  28105 -> 7 の 倍数 である -> 728105, 28105(自分自身) から, 
        //                              それぞれ 28105 を 減算したものが 7 の 倍数なので, 2 を 加算.
        // 728105 -> 7 の 倍数 である -> 728105(自分自身) から, 
        //                              それぞれ 728105 を 減算したものが 7 の 倍数なので, 1 を 加算.
        // 上記合計 7 (= 1 + 3 + 2 + 1) が 集計結果のはず.
        ans += (LL)(uCount[x] - xCount[x] + (x == 0));
    }
    
    // 3-4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// 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 N, P;

char c[202020];

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

string s(c);

int ns = s.size();

LL ans = 0;

// 2. P = 2, 5 の場合.

if(P == 2 || P == 5){

// 2-1. 右端が, P の倍数か？

repr(i, ns - 1, 0) if((s[i] - '0') % P == 0) ans += (LL)(i + 1);

// 2-2. 出力.

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

return 0;

}

// 3. 上記以外.

// 3-1. 10 のべき乗.

int mPow10[ns];

mPow10[ns - 1] = 1;

repr(i, ns - 2, 0) mPow10[i] = mPow10[i + 1] * 10 % P;

// 3-2. U[i] (mod P) の個数は？

map<int, int> uCount;

int u = 0;

repr(i, ns - 1, 0){

u += mPow10[i] * (s[i] - '0');

u %= P;

++uCount[u];

}

// 3-3. 集計.

map<int, int> xCount;

int x = 0;

repr(i, ns - 1, 0){

x += mPow10[i] * (s[i] - '0');

x %= P;

++xCount[x];

// x が 0 は, 自分自身もカウント対象なので, 注意.

// ex.

// N = 6 P = 7 S = 728105 の場合,

// 5 -> 7 の倍数でない -> 05 - 5 = 0 が 7 の倍数となるので, 1 を加算.

// 05 -> 7 の倍数でない -> 05 は 7 の倍数でないので, 0 を加算.

// 105 -> 7 の倍数である -> 728105, 28105, 105(自分自身) から,

// それぞれ 105 を減算したものが 7 の倍数なので, 3 を加算.

// 8105 -> 7 の倍数でない -> 8105 は 7 の倍数でないので, 0 を加算.

// 28105 -> 7 の倍数である -> 728105, 28105(自分自身) から,

// それぞれ 28105 を減算したものが 7 の倍数なので, 2 を加算.

// 728105 -> 7 の倍数である -> 728105(自分自身) から,

// それぞれ 728105 を減算したものが 7 の倍数なので, 1 を加算.

// 上記合計 7 (= 1 + 3 + 2 + 1) が集計結果のはず.

ans += (LL)(uCount[x] - xCount[x] + (x == 0));

}

// 3-4. 出力.

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

return 0;

}

[入力例]
4 3
3543

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

[入力例]
4 2
2020

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

[入力例]
20 11
33883322005544116655

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

[入力例]
6 7
728105

[出力例]
7

[入力例]
8 2
20220624

[出力例]
36

[入力例]
12 5
202003072240

[出力例]
30

[入力例]
100 123
6872267760531042464119518350821166892127405932097676518321338765887563671699117552972989237935232870

[出力例]
43

[入力例]
500 31415
19827912619128213155324311431340676818881586771968486313913880031802243688276451376203819426630356973924068276151752054138722949743845433174772642870341335136341653840978780047251625547015001037931570908172412415966038163714662909499827012269549282246479667761400616079763785738707691959444312832666207128504468482429462634779225762390883765639589187652951246319470816174745539828792627999850115408217855959299618176113149651198371207914448214824113154122258866645535483442753629014046055718878658164

[出力例]
56

[入力例]
1000 2022
2050746112373639485356489833822371389761990747934841841265597655258830232297968397489207690233496298133426293410768896915523812766755705073823818586409515760897930782894751029665097634226112753987009332271329102783102474625096233249280891692991693597633568639895819920959422459379571442123896088337866984489421595649580969796285426754644632567315800335271368050999071714673857927670715182746888815581432466171292295492131794475868801461733656763305977528429343286060721957075107528065898455564711323607055890311868877628618909133146693166860023145095450109292930544534876119895283488561564114642504547807421167248323016039488901561535793585700349466310737594859928780026542295538555515350355620916753933481763278124757373272127214451484549647938952706423163558530974157549181711513258840177446645005648016782019516724730986996393453592778311173619130217005658774305107670115722832986813548915716074625354172299675322194502546799298436785198907858447467803448790926043797899845966937419584694318042712

[出力例]
568

[入力例]
3000 20220307
596214249853483225097693315388909224384489458359826431372736370050820603971963623887223374916230451032952080616398933184251535026230270724401835890958546743454624434891513179796364363818613684299745813048992821012775776182603274217611727698315108854249194305571011714789573157968383474519210375548761883910648845714429491574215927967709529586597429267623637097712094874502528637589735259356521011987313487531114622639634280895531314472288317567241924124525374520626380053203654966374814948435836589081101098669761100669044658065687596533021109001359272974337164913032035249760410975011064653792396282333036217955719298828194573458829930219324512386017241443762438470885612043869536406611407681095560972777468453531916866773859101030929635813816830251144742068739585983959899577090196410233902164796886451593744927354893343913356858966924015231123951425230217457267923084875035706239757292110054735757720086630271101268691864803947406905179497668152325101570480106285035326410169587797498380392931595402548509074625534910183494355558852211413021128648117649900899014169715046066938106607928463353582556945561703118313686961815834149389505115465789809090890212540837188891715090834795472118703882181590227429467403212542982180674875675033516437035242158029597291351551040676003812134976183481144271558828702957427471354270949454780890810664406648785857395292896935628252928596982336870833981830324741464515604511843205181063341575739040518666255058327080389585965186610896654696065438411142665435271504129640043328572627654592179256255998025566103548660638942322143384677507961636075308992340792680254033645422068246686361691158623570075069431018321294545922421021636389297080337921588663982357977229526909116470321114915822673139914674472409576525020826191261709718690585036734121329540440957161361075738430823928138503133266943441005162406670170916574939298499893570061282038478026906288854595326694851351613865867391128213501468341263222274248107637114390405173134592468888519410941707681906904200754225523509190205865290605683971994577025051344857027083921022685954654893216083835686869098933948840609643556421123794591700725195710399020043544330293227662378282784174622758179743232409877655255045476605887615189866917175127208582069784212405656661186614031757797931490384710033497512237081906460780325753339042238740671828300928523312109224528224759099737242272565258627768278828066694562802209146872750725148590822945224260010532206995105321255181059324710839633727858809587370076767850668306926873691694429616371742926924403392061260046164734364664045255997895823394969579011070406439847192915118769193956704674278360413560579461109790715768935197207081728188375678386794199954373694666726071455324418062658727966723489352678898548319161293224216340382739015335474768790942239571225028961503326144288659244262210157158502728534527947520526957552280442455094734146572080410264728865088794877026515299468446838590500231888330601026317311155564146863595555475196625646824815420202458726192347289235

[出力例]
313

[入力例]

4 3

3543

[出力例]

※AtCoderのテストケースより

[入力例]

4 2

2020

[出力例]

※AtCoderのテストケースより

[入力例]

20 11

33883322005544116655

[出力例]

※AtCoderのテストケースより

[入力例]

6 7

728105

[出力例]

[入力例]

8 2

20220624

[出力例]

[入力例]

12 5

202003072240

[出力例]

[入力例]

100 123

6872267760531042464119518350821166892127405932097676518321338765887563671699117552972989237935232870

[出力例]

[入力例]

500 31415

19827912619128213155324311431340676818881586771968486313913880031802243688276451376203819426630356973924068276151752054138722949743845433174772642870341335136341653840978780047251625547015001037931570908172412415966038163714662909499827012269549282246479667761400616079763785738707691959444312832666207128504468482429462634779225762390883765639589187652951246319470816174745539828792627999850115408217855959299618176113149651198371207914448214824113154122258866645535483442753629014046055718878658164

[出力例]

[入力例]

1000 2022

2050746112373639485356489833822371389761990747934841841265597655258830232297968397489207690233496298133426293410768896915523812766755705073823818586409515760897930782894751029665097634226112753987009332271329102783102474625096233249280891692991693597633568639895819920959422459379571442123896088337866984489421595649580969796285426754644632567315800335271368050999071714673857927670715182746888815581432466171292295492131794475868801461733656763305977528429343286060721957075107528065898455564711323607055890311868877628618909133146693166860023145095450109292930544534876119895283488561564114642504547807421167248323016039488901561535793585700349466310737594859928780026542295538555515350355620916753933481763278124757373272127214451484549647938952706423163558530974157549181711513258840177446645005648016782019516724730986996393453592778311173619130217005658774305107670115722832986813548915716074625354172299675322194502546799298436785198907858447467803448790926043797899845966937419584694318042712

[出力例]

568

[入力例]

3000 20220307

596214249853483225097693315388909224384489458359826431372736370050820603971963623887223374916230451032952080616398933184251535026230270724401835890958546743454624434891513179796364363818613684299745813048992821012775776182603274217611727698315108854249194305571011714789573157968383474519210375548761883910648845714429491574215927967709529586597429267623637097712094874502528637589735259356521011987313487531114622639634280895531314472288317567241924124525374520626380053203654966374814948435836589081101098669761100669044658065687596533021109001359272974337164913032035249760410975011064653792396282333036217955719298828194573458829930219324512386017241443762438470885612043869536406611407681095560972777468453531916866773859101030929635813816830251144742068739585983959899577090196410233902164796886451593744927354893343913356858966924015231123951425230217457267923084875035706239757292110054735757720086630271101268691864803947406905179497668152325101570480106285035326410169587797498380392931595402548509074625534910183494355558852211413021128648117649900899014169715046066938106607928463353582556945561703118313686961815834149389505115465789809090890212540837188891715090834795472118703882181590227429467403212542982180674875675033516437035242158029597291351551040676003812134976183481144271558828702957427471354270949454780890810664406648785857395292896935628252928596982336870833981830324741464515604511843205181063341575739040518666255058327080389585965186610896654696065438411142665435271504129640043328572627654592179256255998025566103548660638942322143384677507961636075308992340792680254033645422068246686361691158623570075069431018321294545922421021636389297080337921588663982357977229526909116470321114915822673139914674472409576525020826191261709718690585036734121329540440957161361075738430823928138503133266943441005162406670170916574939298499893570061282038478026906288854595326694851351613865867391128213501468341263222274248107637114390405173134592468888519410941707681906904200754225523509190205865290605683971994577025051344857027083921022685954654893216083835686869098933948840609643556421123794591700725195710399020043544330293227662378282784174622758179743232409877655255045476605887615189866917175127208582069784212405656661186614031757797931490384710033497512237081906460780325753339042238740671828300928523312109224528224759099737242272565258627768278828066694562802209146872750725148590822945224260010532206995105321255181059324710839633727858809587370076767850668306926873691694429616371742926924403392061260046164734364664045255997895823394969579011070406439847192915118769193956704674278360413560579461109790715768935197207081728188375678386794199954373694666726071455324418062658727966723489352678898548319161293224216340382739015335474768790942239571225028961503326144288659244262210157158502728534527947520526957552280442455094734146572080410264728865088794877026515299468446838590500231888330601026317311155564146863595555475196625646824815420202458726192347289235

[出力例]

313

■参照サイト
AtCoder Beginner Contest 158

2022年6月23日

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

C++の練習を兼ねて, AtCoder Beginner Contest 254 の問題E (Small d and k) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc254/editorial/4052
// 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 a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int k) -> int {
        // 空のキュー.
        queue<int> q;
        
        // 変数を用意.
        map<int, int> d;
        int ret = 0;
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 距離 k より大きい場合, 終了.
            if(d.count(u) && d[u] > k) break;
            
            // 頂点の番号を集計.
            ret += (u + 1);
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(!d.count(e) && e != s) d[e] = d[u] + 1, q.push(e);
        }
        
        // 返却.
        return ret;
    };
    
    // 3. クエリ回答.
    int Q;
    scanf("%d", &Q);
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int x, k;
        scanf("%d %d", &x, &k);
        --x;
        
        // 3-2. bfs(距離 k 以下のみ).
        int ans = bfs(G, x, k);
        
        // 3-3. 出力.
        printf("%d\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc254/editorial/4052

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

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

--a, --b;

G[a].pb(b);

G[b].pb(a);

}

// 2. bfs.

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

auto bfs = [&](vvi &G, int s, int k) -> int {

// 空のキュー.

queue<int> q;

// 変数を用意.

map<int, int> d;

int ret = 0;

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 距離 k より大きい場合, 終了.

if(d.count(u) && d[u] > k) break;

// 頂点の番号を集計.

ret += (u + 1);

// 隣接頂点をチェック.

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

}

// 返却.

return ret;

};

// 3. クエリ回答.

int Q;

scanf("%d", &Q);

rep(i, Q){

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

int x, k;

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

--x;

// 3-2. bfs(距離 k 以下のみ).

int ans = bfs(G, x, k);

// 3-3. 出力.

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

}

return 0;

}

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

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

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

[出力例]
55
25
13
6
25
24
24
25

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

[出力例]
8
74
77
45
75
71
21
74
53
64
72
6
58
75
9

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

[入力例]

6 5

2 3

3 4

3 5

5 6

2 6

1 1

2 2

2 0

2 3

4 1

6 0

4 3

[出力例]

※AtCoderテストケースより

[入力例]

10 12

1 2

1 3

1 4

2 5

2 6

5 6

3 7

3 8

7 8

4 9

4 10

9 10

1 3

3 2

5 1

6 0

7 3

4 1

10 2

8 3

[出力例]

[入力例]

20 22

1 2

1 3

1 13

2 4

3 5

4 6

4 8

5 10

5 11

6 7

7 9

7 17

8 9

9 20

10 12

11 12

12 18

13 14

14 15

14 16

15 16

16 19

8 0

6 3

19 3

3 2

5 3

7 2

8 1

6 3

6 2

16 1

2 3

6 0

14 1

5 3

3 1

[出力例]

■参照サイト
AtCoder Beginner Contest 254

2022年6月22日

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

C++の練習を兼ねて, AtCoder Beginner Contest 246 の問題C (Coupon) ～問題D (2-variable Function) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    LL K, X;
    scanf("%d %lld %lld", &N, &K, &X);
    PQ pq;
    rep(i, N){
        LL a;
        scanf("%lld", &a);
        pq.push(a);
    }
    
    // 2. 商品価格の更新.
    while(K && !pq.empty()){
        // 商品を取得.
        LL a = pq.top();
        pq.pop();
        
        // 終了条件.
        if(a < X) break;
        
        // クーポン適用.
        LL q = min(K, a / X);
        a -= q * X;
        K -= q;
        
        // 戻し.
        if(a > 0) pq.push(a);
    }
    
    // 3. 集計.
    LL ans = 0;
    while(!pq.empty()){
        // 商品を取得.
        LL a = pq.top();
        pq.pop();
        
        // 次へ.
        if(--K > 0) continue;
        
        // 金額集計.
        ans += a;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using PQ = priority_queue<LL>;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

LL K, X;

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

PQ pq;

rep(i, N){

LL a;

scanf("%lld", &a);

pq.push(a);

}

// 2. 商品価格の更新.

while(K && !pq.empty()){

// 商品を取得.

LL a = pq.top();

pq.pop();

// 終了条件.

if(a < X) break;

// クーポン適用.

LL q = min(K, a / X);

a -= q * X;

K -= q;

// 戻し.

if(a > 0) pq.push(a);

}

// 3. 集計.

LL ans = 0;

while(!pq.empty()){

// 商品を取得.

LL a = pq.top();

pq.pop();

// 次へ.

if(--K > 0) continue;

// 金額集計.

ans += a;

}

// 4. 出力.

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

return 0;

}

[入力例]
5 4 7
8 3 10 5 13

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

[入力例]
5 100 7
8 3 10 5 13

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

[入力例]
20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

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

[入力例]
10 15 32
7 13 23 84 77 110 57 89 57 52

[出力例]
110

[入力例]
30 25 777
661 1309 1076 501 710 649 539 792 236 734 880 829 1067 1242 822 1260 798 264 1205 1294 829 513 993 822 583 1151 1186 140 762 669

[出力例]
6000

[入力例]

5 4 7

8 3 10 5 13

[出力例]

※AtCoderテストケースより

[入力例]

5 100 7

8 3 10 5 13

[出力例]

※AtCoderテストケースより

[入力例]

20 815 60

2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

[出力例]

112

※AtCoderテストケースより

[入力例]

10 15 32

7 13 23 84 77 110 57 89 57 52

[出力例]

110

[入力例]

30 25 777

661 1309 1076 501 710 649 539 792 236 734 880 829 1067 1242 822 1260 798 264 1205 1294 829 513 993 822 583 1151 1186 140 762 669

[出力例]

6000

■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. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 3 乗が N 以下のもの.
    int p = 0;
    while((LL)p * (LL)p * (LL)p <= N) ++p;
    
    // 3. 評価関数.
    auto f = [&](LL a, LL b) -> bool {
        // 3-1. 数式計算.
        LL X = (a + b) * (a * a + b * b);
        
        // 3-2. 判定結果.
        return (X < N);
    };
    
    // 4. 区間[0, p] で 確認.
    LL ans = 1e18 + 1;
    rep(i, p + 1){
        // 4-1. 二分探索で確認してみる.
       LL l = -1, h = (LL)(2 * p + 1), m, a = (LL)i;
        while(l + 1 < h){
            LL m = (h + l) >> 1;
            if(f(a, m)) l = m;
            else        h = m;
            // printf("h=%lld l=%lld m=%lld\n", h, l, m);
        }
        
        // 4-2. 最小値更新.
        ans = min(ans, (a + h) * (a * a + h * h));
    }
    
    // 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--)

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 3 乗が N 以下のもの.

int p = 0;

while((LL)p * (LL)p * (LL)p <= N) ++p;

// 3. 評価関数.

auto f = [&](LL a, LL b) -> bool {

// 3-1. 数式計算.

LL X = (a + b) * (a * a + b * b);

// 3-2. 判定結果.

return (X < N);

};

// 4. 区間[0, p] で確認.

LL ans = 1e18 + 1;

rep(i, p + 1){

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

LL l = -1, h = (LL)(2 * p + 1), m, a = (LL)i;

while(l + 1 < h){

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

if(f(a, m)) l = m;

else h = m;

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

}

// 4-2. 最小値更新.

ans = min(ans, (a + h) * (a * a + h * h));

}

// 5. 出力.

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

return 0;

}

[入力例]
9

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

[入力例]
0

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

[入力例]
999999999989449206

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

[入力例]
123

[出力例]
125

[入力例]
2022

[出力例]
2048

[入力例]
20220622

[出力例]
20221245

[入力例]
202204022100

[出力例]
202204033115

[入力例]
314159265358979323

[出力例]
314159265359236485

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

999999999989449206

[出力例]

1000000000000000000

※AtCoderテストケースより

[入力例]

123

[出力例]

125

[入力例]

2022

[出力例]

2048

[入力例]

20220622

[出力例]

20221245

[入力例]

202204022100

[出力例]

202204033115

[入力例]

314159265358979323

[出力例]

314159265359236485

■参照サイト
AtCoder Beginner Contest 246

2022年6月21日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. Binary Indexed Tree の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 個人的には, 解説に記載されている数式を使って, 計算していくロジックが, 非常に面白いと感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 事前準備.
    // -> Fenwick Tree を 3個用意する.
    BIT<LL> ft1(N + 1), ft2(N + 1), ft3(N + 1);
    repx(i, 1, N + 1){
        // i * i * a[i].
        ft1.add(i, (LL)i * (LL)i % MOD * a[i - 1] % MOD);
        
        // i * a[i].
        ft2.add(i, (LL)i * a[i - 1] % MOD);
        
        // a[i].
        ft3.add(i, a[i - 1]);
    }
    
    // 3. クエリ回答.
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int f;
        scanf("%d", &f);
        
        // 3-2. クエリ 1.
        if(f == 1){
            int x;
            LL v;
            scanf("%d %lld", &x, &v);
            
            // a[x](区間[x, x + 1) の 合計)を, v に 置き換える.
            // i * i * a[i].
            LL cur1 = ft1.sum(x, x + 1);
            ft1.add(x, ((LL)x * (LL)x % MOD * v % MOD + MOD - cur1) % MOD);
            
            // i * a[i].
            LL cur2 = ft2.sum(x, x + 1);
            ft2.add(x, ((LL)x * v % MOD + MOD - cur2) % MOD);
            
            // a[i].
            LL cur3 = ft3.sum(x, x + 1);
            ft3.add(x, (v + MOD - cur3) % MOD);
        }
        
        // 3-3. クエリ 2.
        if(f == 2){
            int x;
            scanf("%d", &x);
            
            // 区間[1, x + 1) の 合計について, 係数を考慮して, D[x] を 計算.
            // i * i * a[i].
            LL q1 = ft1.sum(1, x + 1);
            q1 %= MOD;
            q1 *= 499122177;
            q1 %= MOD;
            
            // i * a[i].
            LL q2 = ft2.sum(1, x + 1);
            q2 %= MOD;
            q2 *= (LL)(2 * x + 3);
            q2 %= MOD;
            q2 *= 499122177;
            q2 %= MOD;
            
            // a[i].
            LL q3 = ft3.sum(1, x + 1);
            q3 %= MOD;
            q3 *= (LL)(x + 1);
            q3 %= MOD;
            q3 *= (LL)(x + 2);
            q3 %= MOD;
            q3 *= 499122177;
            q3 %= MOD;
            
            // 出力.
            printf("%lld\n", (q1 + MOD - q2 + q3) % MOD);
        }
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

// 解き直し.

// https://atcoder.jp/contests/abc256/editorial/4131

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 998244353;

LL a[202020];

// Binary Indexed Tree (Fenwick Tree)

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

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

template<typename T>

struct BIT{

int n;

vector<T> d;

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

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

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

}

T sum(int i){

T x = 0;

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

return x;

}

T sum(int l, int r){

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

}

};

int main(){

// 1. 入力情報.

int N, Q;

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

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

// 2. 事前準備.

// -> Fenwick Tree を 3個用意する.

BIT<LL> ft1(N + 1), ft2(N + 1), ft3(N + 1);

repx(i, 1, N + 1){

// i * i * a[i].

ft1.add(i, (LL)i * (LL)i % MOD * a[i - 1] % MOD);

// i * a[i].

ft2.add(i, (LL)i * a[i - 1] % MOD);

// a[i].

ft3.add(i, a[i - 1]);

}

// 3. クエリ回答.

rep(i, Q){

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

int f;

scanf("%d", &f);

// 3-2. クエリ 1.

if(f == 1){

int x;

LL v;

scanf("%d %lld", &x, &v);

// a[x](区間[x, x + 1) の合計)を, v に置き換える.

// i * i * a[i].

LL cur1 = ft1.sum(x, x + 1);

ft1.add(x, ((LL)x * (LL)x % MOD * v % MOD + MOD - cur1) % MOD);

// i * a[i].

LL cur2 = ft2.sum(x, x + 1);

ft2.add(x, ((LL)x * v % MOD + MOD - cur2) % MOD);

// a[i].

LL cur3 = ft3.sum(x, x + 1);

ft3.add(x, (v + MOD - cur3) % MOD);

}

// 3-3. クエリ 2.

if(f == 2){

int x;

scanf("%d", &x);

// 区間[1, x + 1) の合計について, 係数を考慮して, D[x] を計算.

// i * i * a[i].

LL q1 = ft1.sum(1, x + 1);

q1 %= MOD;

q1 *= 499122177;

q1 %= MOD;

// i * a[i].

LL q2 = ft2.sum(1, x + 1);

q2 %= MOD;

q2 *= (LL)(2 * x + 3);

q2 %= MOD;

q2 *= 499122177;

q2 %= MOD;

// a[i].

LL q3 = ft3.sum(1, x + 1);

q3 %= MOD;

q3 *= (LL)(x + 1);

q3 %= MOD;

q3 *= (LL)(x + 2);

q3 %= MOD;

q3 *= 499122177;

q3 %= MOD;

// 出力.

printf("%lld\n", (q1 + MOD - q2 + q3) % MOD);

}

return 0;

}

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

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

[入力例]
2 1
998244353 998244353
2 1

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

[入力例]
10 12
96 72 115 31 106 81 57 93 58 110
1 2 19
2 4
1 4 24
1 7 39
2 2
2 3
1 6 22
1 9 88
2 1
1 5 31
1 3 30
2 10

[出力例]
1450
307
748
96
10190

[入力例]
25 30
313 8610 7654 2423 10153 1535 3660 4317 5883 283 7992 11960 1433 4749 7542 2056 9888 11488 675 7366 11897 282 5976 5437 11428
1 6 8971
1 24 3267
1 4 9960
2 21
2 11
1 17 9538
1 12 7337
1 22 8217
2 5
1 7 3611
1 24 6398
2 1
1 8 6281
1 9 9255
2 20
1 25 4288
2 17
2 10
1 5 7164
2 9
1 5 7891
1 4 4727
1 6 10798
1 11 10804
2 6
1 3 3310
1 12 4743
1 1 3322
2 23
2 2

[出力例]
11237518
1812082
176752
313
10000172
6325030
1408711
994451
275096
13561647
18576

[入力例]
50 50
97481596 56913470 20484887 97096478 8115489 111339088 115734595 99553125 85805679 121521835 24333869 36476095 111254902 101662021 68076967 57341299 14384782 7293784 7875941 92252081 95759969 24033082 36749032 79866236 78001189 79367152 77999624 29485924 10388429 64605010 68553065 25993669 56292466 16701153 109941256 11883215 185713 77549992 44723274 60497153 97301159 48552987 114528531 37456326 109030675 59039954 43799330 103816886 78593941 78117787
1 27 95105201
2 7
2 39
2 28
1 2 68118522
1 28 80466466
2 13
1 20 92263222
1 32 88064950
2 28
2 27
1 48 31891698
2 28
2 1
1 22 123044304
1 23 106454807
1 35 110946673
2 16
2 20
1 23 93279411
2 28
1 35 105880627
1 20 96022444
1 41 11586305
2 40
1 4 67251518
1 30 107625160
1 37 1695555
1 39 24388502
1 31 31945776
1 6 53347729
1 31 37833570
2 35
2 1
2 21
2 48
1 32 111919251
2 13
1 37 5026234
1 47 79407780
2 49
1 40 33263713
1 8 57541998
1 28 16290230
2 12
1 17 62593179
2 6
2 50
1 22 82160853
2 25

[出力例]
710128671
621014119
183839522
507893529
477853653
882336553
477853653
97481596
884294293
786360386
444328416
89277185
153609680
97481596
656291952
695401962
771709217
754100544
68869899
760210461
434688344
583595921

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

[入力例]

3 3

1 2 3

2 3

1 2 0

2 3

[出力例]

※AtCoderテストケースより

[入力例]

2 1

998244353 998244353

2 1

[出力例]

※AtCoderテストケースより

[入力例]

10 12

96 72 115 31 106 81 57 93 58 110

1 2 19

2 4

1 4 24

1 7 39

2 2

2 3

1 6 22

1 9 88

2 1

1 5 31

1 3 30

2 10

[出力例]

1450

307

748

10190

[入力例]

25 30

313 8610 7654 2423 10153 1535 3660 4317 5883 283 7992 11960 1433 4749 7542 2056 9888 11488 675 7366 11897 282 5976 5437 11428

1 6 8971

1 24 3267

1 4 9960

2 21

2 11

1 17 9538

1 12 7337

1 22 8217

2 5

1 7 3611

1 24 6398

2 1

1 8 6281

1 9 9255

2 20

1 25 4288

2 17

2 10

1 5 7164

2 9

1 5 7891

1 4 4727

1 6 10798

1 11 10804

2 6

1 3 3310

1 12 4743

1 1 3322

2 23

2 2

[出力例]

11237518

1812082

176752

313

10000172

6325030

1408711

994451

275096

13561647

18576

[入力例]

50 50

97481596 56913470 20484887 97096478 8115489 111339088 115734595 99553125 85805679 121521835 24333869 36476095 111254902 101662021 68076967 57341299 14384782 7293784 7875941 92252081 95759969 24033082 36749032 79866236 78001189 79367152 77999624 29485924 10388429 64605010 68553065 25993669 56292466 16701153 109941256 11883215 185713 77549992 44723274 60497153 97301159 48552987 114528531 37456326 109030675 59039954 43799330 103816886 78593941 78117787

1 27 95105201

2 7

2 39

2 28

1 2 68118522

1 28 80466466

2 13

1 20 92263222

1 32 88064950

2 28

2 27

1 48 31891698

2 28

2 1

1 22 123044304

1 23 106454807

1 35 110946673

2 16

2 20

1 23 93279411

2 28

1 35 105880627

1 20 96022444

1 41 11586305

2 40

1 4 67251518

1 30 107625160

1 37 1695555

1 39 24388502

1 31 31945776

1 6 53347729

1 31 37833570

2 35

2 1

2 21

2 48

1 32 111919251

2 13

1 37 5026234

1 47 79407780

2 49

1 40 33263713

1 8 57541998

1 28 16290230

2 12

1 17 62593179

2 6

2 50

1 22 82160853

2 25

[出力例]

710128671

621014119

183839522

507893529

477853653

882336553

477853653

97481596

884294293

786360386

444328416

89277185

153609680

97481596

656291952

695401962

771709217

754100544

68869899

760210461

434688344

583595921

■参照サイト
東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）

2022年6月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 242 の問題E ((∀x∀)) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc242/editorial/3516
// 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 all(x) x.begin(), x.end()
const LL MOD = 998244353;

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. 26進数(数え上げ, MOD版).
    auto f = [&](string s) -> LL{
        LL ret = s.back() - 'A' + 1, d = 1;
        s.pop_back();
        for(auto i = s.rbegin(), e = s.rend(); i != e; ++i){
            d *= 26;
            d %= MOD;
            ret += d * (*i - 'A');
            ret %= MOD;
        }
        return ret;
    };
    
    // 3. 各テストケース.
    rep(i, T){
        // 3-1. テストケース入力情報.
        int N;
        scanf("%d", &N);
        char c[N + 2];
        scanf("%s", c);
        string s(c);
        
        // 3-2. 争点以下の回文は？
        int l = N / 2 + (N & 1);
        
        // 3-3. 数え上げ.
        string ls1 = s.substr(0, l);
        string ls2 = s.substr(0, l);
        LL ans = f(ls1);
        
        // 3-4. 争点を含むか？
        if(N & 1) ls2.pop_back();
        reverse(all(ls2));
        bool ok = (s >= (ls1 + ls2));
        
        // 3-5. 調整.
        if(!ok) ans = (ans + MOD - 1) % MOD;
        
        // 3-6. 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

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

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

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. 26進数(数え上げ, MOD版).

auto f = [&](string s) -> LL{

LL ret = s.back() - 'A' + 1, d = 1;

s.pop_back();

for(auto i = s.rbegin(), e = s.rend(); i != e; ++i){

d *= 26;

d %= MOD;

ret += d * (*i - 'A');

ret %= MOD;

}

return ret;

};

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

rep(i, T){

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

int N;

scanf("%d", &N);

char c[N + 2];

scanf("%s", c);

string s(c);

// 3-2. 争点以下の回文は？

int l = N / 2 + (N & 1);

// 3-3. 数え上げ.

string ls1 = s.substr(0, l);

string ls2 = s.substr(0, l);

LL ans = f(ls1);

// 3-4. 争点を含むか？

if(N & 1) ls2.pop_back();

reverse(all(ls2));

bool ok = (s >= (ls1 + ls2));

// 3-5. 調整.

if(!ok) ans = (ans + MOD - 1) % MOD;

// 3-6. 出力.

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

}

return 0;

}

[入力例]
5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

[出力例]
24
29
212370247
36523399
231364016
※AtCoderのテストケースより

[入力例]
15
1
Y
2
QV
3
WUB
4
EMLO
5
BRPYK
6
IOGENQ
7
GFVUUCZ
8
ZIVJKEYM
9
NDBSFVDYH
10
WZQZSCRLDQ
11
VJIXLFEULDB
12
DPFUNZWSZJGH
13
DCLBLJYXTODNY
14
BJZDDURALFRQKL
15
OBWIJRFKQCBOQJL

[出力例]
25
17
592
116
1134
5778
109402
445364
5994566
10504356
253778127
42600531
955562087
427327853
217862248

[入力例]
25
1
L
2
HY
3
YND
4
PBWS
5
ORNNI
6
IFNVBT
7
WJISVPH
8
EEDSQXLZ
9
DKAERSRFW
10
VPGHNOIXIA
11
CNGTEXXGTIZ
12
ZGOXEITISMBT
13
ZLZJBWQIWYBTP
14
BJZVLXZESZXWEB
15
LXTXUWGAHXRHXTA
16
VBJSDIVMYNAQMKEN
17
DVXDPPOHTLUBKFFKA
18
FTUURWFXQTDVJCVVMG
19
NMETRNMBEBQCFYYIGTN
20
ZOYRRWYQZETEGCQSFMEY
21
KBLMLWYCQVMDABYYHMYLC
22
TESOQWGINVBEZRSSOUAMMH
23
KHRNAOXSBCXIULNBGKIUTRR
24
THEQLJFLISRSERNCELIYORZP
25
WBDHWUJPAYTVWEOMDLGOAKHPB

[出力例]
12
8
637
392
9919
5552
392983
73104
1546810
9864388
29821868
300037981
877462913
427649715
858384390
388850462
706826887
279373158
289054454
614125680
129623060
618481925
127581610
608225133
666465408

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

[入力例]

AXA

ABCZAZ

QWERTYUIOPASDFGHJKLZXCVBNMQWER

JVIISNEOXHSNEAAENSHXOENSIIVJ

KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

[出力例]

212370247

36523399

231364016

※AtCoderのテストケースより

[入力例]

WUB

EMLO

BRPYK

IOGENQ

GFVUUCZ

ZIVJKEYM

NDBSFVDYH

WZQZSCRLDQ

VJIXLFEULDB

DPFUNZWSZJGH

DCLBLJYXTODNY

BJZDDURALFRQKL

OBWIJRFKQCBOQJL

[出力例]

592

116

1134

5778

109402

445364

5994566

10504356

253778127

42600531

955562087

427327853

217862248

[入力例]

YND

PBWS

ORNNI

IFNVBT

WJISVPH

EEDSQXLZ

DKAERSRFW

VPGHNOIXIA

CNGTEXXGTIZ

ZGOXEITISMBT

ZLZJBWQIWYBTP

BJZVLXZESZXWEB

LXTXUWGAHXRHXTA

VBJSDIVMYNAQMKEN

DVXDPPOHTLUBKFFKA

FTUURWFXQTDVJCVVMG

NMETRNMBEBQCFYYIGTN

ZOYRRWYQZETEGCQSFMEY

KBLMLWYCQVMDABYYHMYLC

TESOQWGINVBEZRSSOUAMMH

KHRNAOXSBCXIULNBGKIUTRR

THEQLJFLISRSERNCELIYORZP

WBDHWUJPAYTVWEOMDLGOAKHPB

[出力例]

637

392

9919

5552

392983

73104

1546810

9864388

29821868

300037981

877462913

427649715

858384390

388850462

706826887

279373158

289054454

614125680

129623060

618481925

127581610

608225133

666465408

■参照サイト
AtCoder Beginner Contest 242

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

C++の練習を兼ねて, AtCoder Regular Contest 118 の 問題C (Coprime Set) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 155 の 問題D (Pairs) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 257 の 問題E (Addition and Multiplication 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 257 の 問題C (Robot Takahashi) ～ 問題D (Jumping Takahashi 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 158 の 問題E (Divisible Substring) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 254 の 問題E (Small d and k) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 246 の 問題C (Coupon) ～ 問題D (2-variable Function) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 242 の 問題E ((∀x∀)) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 118 の問題C (Coprime Set) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 155 の問題D (Pairs) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 257 の問題E (Addition and Multiplication 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 257 の問題C (Robot Takahashi) ～問題D (Jumping Takahashi 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 158 の問題E (Divisible Substring) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 254 の問題E (Small d and k) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 246 の問題C (Coupon) ～問題D (2-variable Function) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 242 の問題E ((∀x∀)) を解いてみた.