C++ | 個人用メモ帳

2021年11月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 229 の問題C (Cheese) ～問題D (Longest X) を解いてみた.

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

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, W;
    scanf("%d %d", &N, &W);
    vp v;
    rep(i, N){
        int a, b;
        scanf("%d %d", &a, &b);
        v.pb({a, b});
    }
    
    // 2. sort.
    sort(all(v));
    reverse(all(v));
    
    // 3. おいしさの最大値は？
    LL ans = 0;
    for(auto &p : v){
        // 使用可能な重さ.
        int u = min(W, p.b);
        
        // おいしさ集計.
        ans += (LL)p.a * (LL)u;
        
        // 重さの上限を更新.
        W -= u;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

int main(){

// 1. 入力情報.

int N, W;

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

vp v;

rep(i, N){

int a, b;

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

v.pb({a, b});

}

// 2. sort.

sort(all(v));

reverse(all(v));

// 3. おいしさの最大値は？

LL ans = 0;

for(auto &p : v){

// 使用可能な重さ.

int u = min(W, p.b);

// おいしさ集計.

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

// 重さの上限を更新.

W -= u;

}

// 4. 出力.

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

return 0;

}

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

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

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

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

[入力例]
10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

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

[入力例]
20 2020
11129 114
9830 189
6935 203
10470 183
4882 269
8083 45
10131 101
9683 142
571 174
4186 208
10556 83
6067 128
2315 200
10052 283
6805 124
7139 63
727 261
175 205
3831 205
4787 239

[出力例]
16761809

[入力例]

3 5

3 1

4 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

4 100

6 2

1 5

3 9

8 7

[出力例]

100

※AtCoderテストケースより

[入力例]

10 3141

314944731 649

140276783 228

578012421 809

878510647 519

925326537 943

337666726 611

879137070 306

87808915 39

756059990 244

228622672 291

[出力例]

2357689932073

※AtCoderテストケースより

[入力例]

20 2020

11129 114

9830 189

6935 203

10470 183

4882 269

8083 45

10131 101

9683 142

571 174

4186 208

10556 83

6067 128

2315 200

10052 283

6805 124

7139 63

727 261

175 205

3831 205

4787 239

[出力例]

16761809

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

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

int main(){
    
    // 1. 入力情報.
    char s[202020];
    int K;
    scanf("%s %d", s, &K);
    int N = strlen(s);
    
    // 2. 累積和.
    rep(i, N) dCum[i + 1] = dCum[i] + (s[i] == '.');
    
    // 3. 評価関数.
    auto f = [&](int m) -> bool {
        // 3-1. 各区間で, K個以下 の '.' が 見つかるか？
        bool ok = false;
        rep(i, N + 1 - m){
            if(dCum[i + m] - dCum[i] <= K){
                ok = true;
                break;
            }
        }
        
        // 3-2. 判定結果.
        return ok;
    };
    
    // 4. 二分探索で確認してみる.
    int l = 0, h = N + 1, m;
    while(l + 1 < h){
        int m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    
    // 5. 出力.
    printf("%lld\n", l);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int dCum[202020];

int main(){

// 1. 入力情報.

char s[202020];

int K;

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

int N = strlen(s);

// 2. 累積和.

rep(i, N) dCum[i + 1] = dCum[i] + (s[i] == '.');

// 3. 評価関数.

auto f = [&](int m) -> bool {

// 3-1. 各区間で, K個以下の '.' が見つかるか？

bool ok = false;

rep(i, N + 1 - m){

if(dCum[i + m] - dCum[i] <= K){

ok = true;

break;

}

// 3-2. 判定結果.

return ok;

};

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

int l = 0, h = N + 1, m;

while(l + 1 < h){

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

if(f(m)) l = m;

else h = m;

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

}

// 5. 出力.

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

return 0;

}

[入力例]
XX...X.X.X.
2

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

[入力例]
XXXX
200000

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

[入力例]
X..X....X.X.XXX.XX.X.XXXXXX...XXX....XX.X.X.XX..X.
3

[出力例]
15

[入力例]
.XXX.XXX..X...XXX.X..XXXX.XXX.X...XXX..XXXX....X.XX.X.XXXXX.....X.XXXX....XX.XXX..XX..X....XX.X.XXXX
5

[出力例]
17

[入力例]
XX....X..XXX...X...XXX.X.XX..XX.X.X...X..XX...X...XXX.XXX.....XXXX.XX.X...X.X.XX..XXXX.XXX.X..XXXXXXX.....XXXXXXXX..XX..X.....X..XX...XX..XXX.X..X....X.X.X.X..X.X..X.X.X..XX.XX..X.X...X.XX........X.X.
7

[出力例]
25

[入力例]

XX...X.X.X.

[出力例]

※AtCoderテストケースより

[入力例]

XXXX

200000

[出力例]

※AtCoderテストケースより

[入力例]

X..X....X.X.XXX.XX.X.XXXXXX...XXX....XX.X.X.XX..X.

[出力例]

[入力例]

.XXX.XXX..X...XXX.X..XXXX.XXX.X...XXX..XXXX....X.XX.X.XXXXX.....X.XXXX....XX.XXX..XX..X....XX.X.XXXX

[出力例]

[入力例]

XX....X..XXX...X...XXX.X.XX..XX.X.X...X..XX...X...XXX.XXX.....XXXX.XX.X...X.X.XX..XXXX.XXX.X..XXXXXXX.....XXXXXXXX..XX..X.....X..XX...XX..XXX.X..X....X.X.X.X..X.X..X.X.X..XX.XX..X.X...X.XX........X.X.

[出力例]

■参照サイト
NECプログラミングコンテスト2021(AtCoder Beginner Contest 229)

2021年11月27日

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

C++の練習を兼ねて, AtCoder Regular Contest 008 の問題A (たこ焼き買えるかな？) ～問題B (謎のたこ焼きおじさん) を解いてみた.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, ans = 15 * N;
    scanf("%d", &N);
    
    // 2. 購入価格の最小値は？
    rep(a, N + 1){
        rep(b, (N + 10) / 10 + 1){
            // たこ焼きの購入個数.
            int n = a + 10 * b;
            
            // たこ焼きの購入金額.
            int p = 15 * a + 100 * b;
            
            // 判定.
            if(n >= N) ans = min(ans, p);
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N, ans = 15 * N;

scanf("%d", &N);

// 2. 購入価格の最小値は？

rep(a, N + 1){

rep(b, (N + 10) / 10 + 1){

// たこ焼きの購入個数.

int n = a + 10 * b;

// たこ焼きの購入金額.

int p = 15 * a + 100 * b;

// 判定.

if(n >= N) ans = min(ans, p);

}

// 3. 出力.

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

return 0;

}

[入力例]
2

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

[入力例]
5

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

[入力例]
7

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

[入力例]
9

[出力例]
100

[入力例]
11

[出力例]
115

[入力例]
17

[出力例]
200

[入力例]
47

[出力例]
500

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

100

※AtCoderのテストケースより

[入力例]

[出力例]

100

[入力例]

[出力例]

115

[入力例]

[出力例]

200

[入力例]

[出力例]

500

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    char s[101], t[101];
    scanf("%d %d %s %s", &N, &M, s, t);
    
    // 2. 出現回数をチェック.
    rep(i, N) n[s[i] - 'A']++;
    rep(i, M) k[t[i] - 'A']++;
    
    // 3. 例外チェック.
    bool ok = true;
    rep(i, 26) if(n[i] && !k[i]) ok = false;
    
    // 4. 必要な英字キット数は？
    int ans = 0;
    rep(i, 26){
        if(k[i]){
            int q = n[i] / k[i];
            int r = n[i] % k[i];
            if(r) q++;
            ans = max(ans, q);
        }
    }
    
    // 5. 出力.
    printf("%d\n", ok ? ans : -1);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int n[26], k[26];

int main(){

// 1. 入力情報.

int N, M;

char s[101], t[101];

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

// 2. 出現回数をチェック.

rep(i, N) n[s[i] - 'A']++;

rep(i, M) k[t[i] - 'A']++;

// 3. 例外チェック.

bool ok = true;

rep(i, 26) if(n[i] && !k[i]) ok = false;

// 4. 必要な英字キット数は？

int ans = 0;

rep(i, 26){

if(k[i]){

int q = n[i] / k[i];

int r = n[i] % k[i];

if(r) q++;

ans = max(ans, q);

}

// 5. 出力.

printf("%d\n", ok ? ans : -1);

return 0;

}

[入力例]
7 26
NAOHIRO
ABCDEFGHIJKLMNOPQRSTUVWXYZ

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

[入力例]
8 8
TAKOYAKI
TAKOYAKI

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

[入力例]
8 4
CHOKUDAI
MYON

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

[入力例]
6 6
MONAKA
NAMAKO

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

[入力例]
50 28
HRTHEWHWFTJNEIOYSODEAGKYZRPGVXQHEJNLJVRKJUUDZZQBZI
ABDEEFGHHIJJKLNOPQRSTUVWXYZZ

[出力例]
3

[入力例]
50 21
OJOFKJZDHFRDDKPCRCBLCFTKJFTGFRVJRECUHBBPUEMCOKUQIC
BCCDEFGHIJKLMOPQRTUVZ

[出力例]
5

[入力例]
50 21
FGQELDHUELBVQHHQRCQWQBGQQCTEEGEGVKRKDWRQPUEETBXSGZ
BCCDEFGHKLPQRRSTUVWXZ

[出力例]
8

[入力例]

7 26

NAOHIRO

ABCDEFGHIJKLMNOPQRSTUVWXYZ

[出力例]

※AtCoderのテストケースより

[入力例]

8 8

TAKOYAKI

[出力例]

※AtCoderのテストケースより

[入力例]

8 4

CHOKUDAI

MYON

[出力例]

-1

※AtCoderのテストケースより

[入力例]

6 6

MONAKA

NAMAKO

[出力例]

※AtCoderのテストケースより

[入力例]

50 28

HRTHEWHWFTJNEIOYSODEAGKYZRPGVXQHEJNLJVRKJUUDZZQBZI

ABDEEFGHHIJJKLNOPQRSTUVWXYZZ

[出力例]

[入力例]

50 21

OJOFKJZDHFRDDKPCRCBLCFTKJFTGFRVJRECUHBBPUEMCOKUQIC

BCCDEFGHIJKLMOPQRTUVZ

[出力例]

[入力例]

50 21

FGQELDHUELBVQHHQRCQWQBGQQCTEEGEGVKRKDWRQPUEETBXSGZ

BCCDEFGHKLPQRRSTUVWXZ

[出力例]

■参照サイト
AtCoder Regular Contest 008

2021年11月26日

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

C++の練習を兼ねて, AtCoder Regular Contest 129 の問題D (-1+2-1) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 数式の性質から操作回数を決めていくロジックが, 非常に面白い問題と感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL t = 0;
    rep(i, N){
        scanf("%lld", &A[i + 1]);
        t += A[i + 1];
    }
    A[0]     = A[N];
    A[N + 1] = A[1];
    
    // 2. 例外.
    if(t != 0){
        puts("-1");
        return 0;
    }
    
    // 3. 数列 b.
    // 3-1. 計算準備.
    // 
    // b[2] - b[1]     = A[2]
    // b[3] - b[2]     = A[3]
    // ...
    // b[N] - b[N - 1] = A[N]
    // 
    // -> 上記の (N - 1)個 の 数式は, 以下のように読み替えることができる.
    // b[2] - b[1] = A[2]
    // b[3] - b[1] = A[2] + A[3]
    // ...
    // b[N] - b[1] = A[2] + A[3] + ... + A[N]
    // 
    // -> 左辺 の 合計は？
    // (b[2] + b[3] + ... + b[N]) - b[1] * (N - 1) = -b[1] - b[1] * (N - 1) = - b[1] * N が 分かる.
    LL B1 = A[2];
    b[2] = A[2];
    rep(i, N - 2){
        b[i + 3] = b[i + 2] + A[i + 3];
        B1 += b[i + 3];
    }
    
    // 3-2. 例外.
    if(B1 % N != 0){
        puts("-1");
        return 0;
    }
    
    // 3-3. 計算.
    B1 /= -N;
    b[1] = B1;
    repx(i, 2, N + 1) b[i] += b[1];
    
    // 4. 数列 a.
    // 4-1. 計算準備.
    // a[2] - a[1]     = b[1]
    // a[3] - a[2]     = b[2]
    // ...
    // a[N] - a[N - 1] = b[N - 1]
    // 
    // -> 上記の (N - 1)個 の 数式は, 以下のように読み替えることができる.
    // a[2] - a[1] = b[1]
    // a[3] - a[1] = b[1] + b[2]
    // ...
    // a[N] - a[1] = b[1] + b[2] + ... + b[N - 1]
    LL aMin = 202020202020202020, bSum = 0;
    bSum = b[1];
    aMin = min(aMin, bSum);
    rep(i, N - 2){
        bSum += b[i + 2];
        aMin = min(aMin, bSum);
    }
    
    // 4-2. a[1] を 決める.
    a[1] = (aMin < 0) ? -aMin : 0;
    
    // 4-3. 計算.
    repx(i, 1, N) a[i + 1] = a[i] + b[i];
    
    // 5. 操作回数.
    LL ans = 0;
    rep(i, N) ans += a[i + 1];
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc129/editorial/2938

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL A[202020], a[202020], b[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL t = 0;

rep(i, N){

scanf("%lld", &A[i + 1]);

t += A[i + 1];

}

A[0] = A[N];

A[N + 1] = A[1];

// 2. 例外.

if(t != 0){

puts("-1");

return 0;

}

// 3. 数列 b.

// 3-1. 計算準備.

// b[2] - b[1] = A[2]

// b[3] - b[2] = A[3]

// ...

// b[N] - b[N - 1] = A[N]

// -> 上記の (N - 1)個の数式は, 以下のように読み替えることができる.

// b[2] - b[1] = A[2]

// b[3] - b[1] = A[2] + A[3]

// ...

// b[N] - b[1] = A[2] + A[3] + ... + A[N]

// -> 左辺の合計は？

// (b[2] + b[3] + ... + b[N]) - b[1] * (N - 1) = -b[1] - b[1] * (N - 1) = - b[1] * N が分かる.

LL B1 = A[2];

b[2] = A[2];

rep(i, N - 2){

b[i + 3] = b[i + 2] + A[i + 3];

B1 += b[i + 3];

}

// 3-2. 例外.

if(B1 % N != 0){

puts("-1");

return 0;

}

// 3-3. 計算.

B1 /= -N;

b[1] = B1;

repx(i, 2, N + 1) b[i] += b[1];

// 4. 数列 a.

// 4-1. 計算準備.

// a[2] - a[1] = b[1]

// a[3] - a[2] = b[2]

// ...

// a[N] - a[N - 1] = b[N - 1]

// -> 上記の (N - 1)個の数式は, 以下のように読み替えることができる.

// a[2] - a[1] = b[1]

// a[3] - a[1] = b[1] + b[2]

// ...

// a[N] - a[1] = b[1] + b[2] + ... + b[N - 1]

LL aMin = 202020202020202020, bSum = 0;

bSum = b[1];

aMin = min(aMin, bSum);

rep(i, N - 2){

bSum += b[i + 2];

aMin = min(aMin, bSum);

}

// 4-2. a[1] を決める.

a[1] = (aMin < 0) ? -aMin : 0;

// 4-3. 計算.

repx(i, 1, N) a[i + 1] = a[i] + b[i];

// 5. 操作回数.

LL ans = 0;

rep(i, N) ans += a[i + 1];

// 6. 出力.

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

return 0;

}

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

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

[入力例]
3
1 0 -2

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

[入力例]
4
1 -1 1 -1

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

[入力例]
10
-28 -3 90 -90 77 49 -31 48 -28 -84

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

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

[出力例]
12

[入力例]
20
32 114 -39 -57 12 -77 -51 70 -23 120 21 -26 77 -25 88 -93 11 -101 -80 27

[出力例]
6054

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

[出力例]
213

[入力例]

3 0 -1 -2

[出力例]

※AtCoderのテストケースより

[入力例]

1 0 -2

[出力例]

-1

※AtCoderのテストケースより

[入力例]

1 -1 1 -1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

-28 -3 90 -90 77 49 -31 48 -28 -84

[出力例]

962

※AtCoderのテストケースより

[入力例]

2 0 5 -3 -4

[出力例]

[入力例]

32 114 -39 -57 12 -77 -51 70 -23 120 21 -26 77 -25 88 -93 11 -101 -80 27

[出力例]

6054

[入力例]

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

[出力例]

213

■参照サイト
AtCoder Regular Contest 129

2021年11月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 129 の問題C (Multiple of 7) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 指定された個数となるように, 7の倍数となる範囲を決めていくロジックが, 非常に面白い問題と感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc129/editorial/2937
// 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 t[7][7];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 対応表.
    // -> ax = b (mod 7) となる x を 保存.
    repx(a, 1, 7) t[a][0] = 7;
    repx(b, 1, 7) t[1][b] = b;
    repx(a, 2, 7){
        repx(b, 1, 7){
            int nb = a * t[1][b] % 7;
            t[a][nb] = b;
        }
    }
    // rep(a, 7){
    //     rep(b, 7) printf("%d ", t[a][b]);
    //     puts("");
    // }
    
    // 3. c0, c1, ... , c6 を 求める(解説通り).
    // ex.
    // N = 20 ならば, 6, 3, 2, 2 と 分解.
    vi c;
    int n = N;
    while(n){
        int bef = -1, cur = 0;
        repx(i, 1, n + 2){
            // 今回分更新.
            cur = (i - 1) * i / 2;
            
            // 今回分が等しい場合.
            if(cur == n){
                c.pb(i);
                n -= cur;
                break;
            }
            
            // 今回分が大きい場合.
            if(cur > n){
                c.pb(i - 1);
                n -= bef;
                break;
            }
            
            // 前回分更新.
            bef = cur;
        }
    }
    // for(auto &p : c) printf("%d\n", p);
    
    // 4. 特殊ケース.
    // -> 余りゼロは, 一回多くカウントしているので減算(解説上, a[|s| + 1] = 0 とする部分に対応すると見る).
    c[0]--;
    
    // 5. s[i] を 後ろから決めていく.
    string ans = "";
    int curB = -1, befB = 0, mPow10 = 1;
    for(auto &p : c){
        // 5-1. 今回分余り.
        curB++;
        
        // 5-2. 文字列を構成.
        rep(i, p){
            // 条件式.
            // m = s[i] * (10 の 冪) % 7 + 前回分余り(befB = b[i + 1]) を 考えた時に, 
            // m = 今回分余り(curB = b[i]) (mod 7) となるように, s[i] を 決める必要がある.
            // -> ax = b (mod 7) の 形に変形して, 対応表を使うようにする.
            int a = mPow10 % 7;
            int b = (curB + 7 - befB) % 7;
            ans = (char)(t[a][b] + '0') + ans;
            
            // 次の桁.
            mPow10 *= 10;
            mPow10 %= 7;
            
            // 前回分余り.
            befB = curB;
        }
    }
    
    // 6. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc129/editorial/2937

// 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 t[7][7];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 対応表.

// -> ax = b (mod 7) となる x を保存.

repx(a, 1, 7) t[a][0] = 7;

repx(b, 1, 7) t[1][b] = b;

repx(a, 2, 7){

repx(b, 1, 7){

int nb = a * t[1][b] % 7;

t[a][nb] = b;

}

// rep(a, 7){

// rep(b, 7) printf("%d ", t[a][b]);

// puts("");

// }

// 3. c0, c1, ... , c6 を求める(解説通り).

// ex.

// N = 20 ならば, 6, 3, 2, 2 と分解.

vi c;

int n = N;

while(n){

int bef = -1, cur = 0;

repx(i, 1, n + 2){

// 今回分更新.

cur = (i - 1) * i / 2;

// 今回分が等しい場合.

if(cur == n){

c.pb(i);

n -= cur;

break;

}

// 今回分が大きい場合.

if(cur > n){

c.pb(i - 1);

n -= bef;

break;

}

// 前回分更新.

bef = cur;

}

// for(auto &p : c) printf("%d\n", p);

// 4. 特殊ケース.

// -> 余りゼロは, 一回多くカウントしているので減算(解説上, a[|s| + 1] = 0 とする部分に対応すると見る).

c[0]--;

// 5. s[i] を後ろから決めていく.

string ans = "";

int curB = -1, befB = 0, mPow10 = 1;

for(auto &p : c){

// 5-1. 今回分余り.

curB++;

// 5-2. 文字列を構成.

rep(i, p){

// 条件式.

// m = s[i] * (10 の冪) % 7 + 前回分余り(befB = b[i + 1]) を考えた時に,

// m = 今回分余り(curB = b[i]) (mod 7) となるように, s[i] を決める必要がある.

// -> ax = b (mod 7) の形に変形して, 対応表を使うようにする.

int a = mPow10 % 7;

int b = (curB + 7 - befB) % 7;

ans = (char)(t[a][b] + '0') + ans;

// 次の桁.

mPow10 *= 10;

mPow10 %= 7;

// 前回分余り.

befB = curB;

}

// 6. 出力.

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

return 0;

}

[入力例]
2

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

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

[入力例]
3

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

[入力例]
5

[出力例]
727477

[入力例]
7

[出力例]
76777

[入力例]
20

[出力例]
727477377777

[入力例]
2021

[出力例]
7471776777777777777777777777777777777777777777777777777777777777777777

[入力例]
5049

[出力例]
7376777377777777777776777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777

[入力例]
314159

[出力例]
76777727777777777777771777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777

[入力例]
20211123

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

[入力例]

[出力例]

142

※AtCoderのテストケースより

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

757

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

727477

[入力例]

[出力例]

76777

[入力例]

[出力例]

727477377777

[入力例]

2021

[出力例]

7471776777777777777777777777777777777777777777777777777777777777777777

[入力例]

5049

[出力例]

7376777377777777777776777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777

[入力例]

314159

[出力例]

76777727777777777777771777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777

[入力例]

20211123

[出力例]

77477727777777777777777777777777777777777777777777777777777777777777777776777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777

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

■参照サイト
AtCoder Regular Contest 129

2021年11月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 129 の問題A (Smaller XOR) ～問題B (Range Point Distance) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc129/editorial/2935
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    
    // 1. 入力情報.
    LL N, L, R;
    scanf("%lld %lld %lld", &N, &L, &R);
    
    // 2. 解説通り.
    LL t = 1, ans = 0;
    while(t <= N){
        if(t & N) ans += max(0LL, min(R, t * 2 - 1) - max(L, t) + 1);
        t <<= 1;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc129/editorial/2935

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報.

LL N, L, R;

scanf("%lld %lld %lld", &N, &L, &R);

// 2. 解説通り.

LL t = 1, ans = 0;

while(t <= N){

if(t & N) ans += max(0LL, min(R, t * 2 - 1) - max(L, t) + 1);

t <<= 1;

}

// 3. 出力.

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

return 0;

}

[入力例]
2 1 2

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

[入力例]
10 2 19

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

[入力例]
1000000000000000000 1 1000000000000000000

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

[入力例]
314159265358 9793238462 643383279502

[出力例]
309237645312

[入力例]
202020202020 101010101010 303030303030

[出力例]
137438953472

[入力例]

2 1 2

[出力例]

※AtCoderのテストケースより

[入力例]

10 2 19

[出力例]

※AtCoderのテストケースより

[入力例]

1000000000000000000 1 1000000000000000000

[出力例]

847078495393153025

※AtCoderのテストケースより

[入力例]

314159265358 9793238462 643383279502

[出力例]

309237645312

[入力例]

202020202020 101010101010 303030303030

[出力例]

137438953472

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. クエリ回答(解説通り).
    int a = 0, b = 2020202020;
    rep(i, N){
        // クエリ情報.
        int l, r;
        scanf("%d %d", &l, &r);
        
        // 最大, 最小値更新.
        a = max(a, l);
        b = min(b, r);
        
        // 出力.
        printf("%d\n", (a <= b) ? 0 : (a + 1 - b) / 2);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc129/editorial/2936

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

int a = 0, b = 2020202020;

rep(i, N){

// クエリ情報.

int l, r;

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

// 最大, 最小値更新.

a = max(a, l);

b = min(b, r);

// 出力.

printf("%d\n", (a <= b) ? 0 : (a + 1 - b) / 2);

}

return 0;

}

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

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

[入力例]
10
64 96
30 78
52 61
18 28
9 34
42 86
11 49
1 79
13 59
70 95

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

[入力例]
25
20 85
3 23
22 85
46 126
38 127
38 103
63 162
99 103
17 50
84 166
108 202
48 75
92 203
26 68
49 103
31 144
111 135
120 229
105 225
82 154
53 96
85 177
38 109
113 136
40 143

[出力例]
0
0
0
12
12
12
20
38
38
38
43
43
43
43
43
43
44
49
49
49
49
49
49
49
49

[入力例]
50
6637 7742
6846 7070
10593 14006
8994 16417
4804 16441
6719 12707
3250 11987
12320 23548
6530 18267
2361 11334
1680 7018
6250 7231
7722 15844
10055 12701
2482 7872
5831 7173
11736 11923
5401 9861
10325 14584
3305 13412
10218 12773
5757 15433
5089 5442
9280 14236
6360 15629
77 12037
7383 11602
7046 10451
5600 11303
7776 11996
1345 5184
947 3505
7507 8037
126 9954
4351 5354
1330 2679
6270 15592
30 572
3125 10136
4369 5900
6602 14016
4908 12608
5933 13907
7936 11915
5608 16210
233 8238
11615 18715
9657 14096
3987 14815
8168 16610

[出力例]
0
0
1762
1762
1762
1762
1762
2625
2625
2625
2651
2651
2651
2651
2651
2651
2651
2651
2651
2651
2651
2651
3439
3439
3439
3439
3439
3439
3439
3439
3568
4408
4408
4408
4408
4821
4821
5874
5874
5874
5874
5874
5874
5874
5874
5874
5874
5874
5874
5874

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

[入力例]

1 3

2 4

5 6

[出力例]

※AtCoderのテストケースより

[入力例]

64 96

30 78

52 61

18 28

9 34

42 86

11 49

1 79

13 59

70 95

[出力例]

※AtCoderのテストケースより

[入力例]

20 85

3 23

22 85

46 126

38 127

38 103

63 162

99 103

17 50

84 166

108 202

48 75

92 203

26 68

49 103

31 144

111 135

120 229

105 225

82 154

53 96

85 177

38 109

113 136

40 143

[出力例]

[入力例]

6637 7742

6846 7070

10593 14006

8994 16417

4804 16441

6719 12707

3250 11987

12320 23548

6530 18267

2361 11334

1680 7018

6250 7231

7722 15844

10055 12701

2482 7872

5831 7173

11736 11923

5401 9861

10325 14584

3305 13412

10218 12773

5757 15433

5089 5442

9280 14236

6360 15629

77 12037

7383 11602

7046 10451

5600 11303

7776 11996

1345 5184

947 3505

7507 8037

126 9954

4351 5354

1330 2679

6270 15592

30 572

3125 10136

4369 5900

6602 14016

4908 12608

5933 13907

7936 11915

5608 16210

233 8238

11615 18715

9657 14096

3987 14815

8168 16610

[出力例]

1762

2625

2651

3439

3568

4408

4821

5874

■参照サイト
AtCoder Regular Contest 129

2021年11月18日

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

C++の練習を兼ねて, AtCoder Beginner Contest 226 の問題G (The baggage) を解いてみた.

■感想.
1. 問題Gは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 荷物の重さと, 人の体力に応じて, 割り当てを決めていくロジックが, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. 各テストケース.
    rep(i, T){
        // 2-1. テストケース.
        LL a[5], b[5], r[5], o;
        rep(j, 5) scanf("%lld", &a[j]); // 荷物.
        rep(j, 5) scanf("%lld", &b[j]); // 体力.
        
        // 2-2. Step1.
        // -> 体力 5 の 人 が, 重さ 5 の 荷物 を持つ.
        o = min(a[4], b[4]);
        a[4] -= o;
        b[4] -= o;
        
        // 2-3. Step2.
        // -> 体力 4 の 人 が, 重さ 4 の 荷物 を持つ.
        o = min(a[3], b[3]);
        a[3] -= o;
        b[3] -= o;
        
        // 2-4. Step3.
        // -> 体力 5 の 人 が, 重さ 4 の 荷物 を持つ.
        o = min(a[3], b[4]);
        b[0] += o; // 残り体力 1 の 人 を 増やす.
        a[3] -= o;
        b[4] -= o;
        
        // 2-5. Step4.
        // -> 体力 3 の 人 が, 重さ 3 の 荷物 を持つ.
        o = min(a[2], b[2]);
        a[2] -= o;
        b[2] -= o;
        
        // 2-6. Step5.
        // -> 体力 5 の 人 が, 重さ 3 の 荷物 を持つ.
        o = min(a[2], b[4]);
        b[1] += o; // 残り体力 2 の 人 を 増やす.
        a[2] -= o;
        b[4] -= o;
        
        // 2-7. Step6.
        // -> 体力 4 の 人 が, 重さ 3 の 荷物 を持つ.
        o = min(a[2], b[3]);
        b[0] += o; // 残り体力 1 の 人 を 増やす.
        a[2] -= o;
        b[3] -= o;
        
        // 2-8. Step7.
        // -> 残り体力 2以上 の 人 が, 重さ 2 の 荷物 を持つ.
        // 残り体力 5.
        o = min(a[1], b[4]);
        b[2] += o; // 残り体力 3 の 人 を 増やす.
        a[1] -= o;
        b[4] -= o;
        
        // 残り体力 4.
        o = min(a[1], b[3]);
        b[1] += o; // 残り体力 2 の 人 を 増やす.
        a[1] -= o;
        b[3] -= o;
        
        // 残り体力 3.
        o = min(a[1], b[2]);
        b[0] += o; // 残り体力 1 の 人 を 増やす.
        a[1] -= o;
        b[2] -= o;
        
        // 残り体力 2.
        o = min(a[1], b[1]);
        a[1] -= o;
        b[1] -= o;
        
        // 2-9. Step8.
        // -> 残り体力 1以上 の 人 が, 重さ 1 の 荷物 を持つ.
        // 残り体力 5.
        o = min(a[0], b[4]);
        b[3] += o; // 残り体力 4 の 人 を 増やす.
        a[0] -= o;
        b[4] -= o;
        
        // 残り体力 4.
        o = min(a[0], b[3]);
        b[2] += o; // 残り体力 3 の 人 を 増やす.
        a[0] -= o;
        b[3] -= o;
        
        // 残り体力 3.
        o = min(a[0], b[2]);
        b[1] += o; // 残り体力 2 の 人 を 増やす.
        a[0] -= o;
        b[2] -= o;
        
        // 残り体力 2.
        o = min(a[0], b[1]);
        b[0] += o; // 残り体力 1 の 人 を 増やす.
        a[0] -= o;
        b[1] -= o;
        
        // 残り体力 1.
        o = min(a[0], b[0]);
        a[0] -= o;
        b[0] -= o;
        
        // 2-10. 出力.
        LL ans = 0;
        rep(j, 5) ans += a[j];
        printf("%s\n", ans ? "No" : "Yes");
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

// 解き直し.

// https://atcoder.jp/contests/abc226/editorial/2893

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

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

rep(i, T){

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

LL a[5], b[5], r[5], o;

rep(j, 5) scanf("%lld", &a[j]); // 荷物.

rep(j, 5) scanf("%lld", &b[j]); // 体力.

// 2-2. Step1.

// -> 体力 5 の人が, 重さ 5 の荷物を持つ.

o = min(a[4], b[4]);

a[4] -= o;

b[4] -= o;

// 2-3. Step2.

// -> 体力 4 の人が, 重さ 4 の荷物を持つ.

o = min(a[3], b[3]);

a[3] -= o;

b[3] -= o;

// 2-4. Step3.

// -> 体力 5 の人が, 重さ 4 の荷物を持つ.

o = min(a[3], b[4]);

b[0] += o; // 残り体力 1 の人を増やす.

a[3] -= o;

b[4] -= o;

// 2-5. Step4.

// -> 体力 3 の人が, 重さ 3 の荷物を持つ.

o = min(a[2], b[2]);

a[2] -= o;

b[2] -= o;

// 2-6. Step5.

// -> 体力 5 の人が, 重さ 3 の荷物を持つ.

o = min(a[2], b[4]);

b[1] += o; // 残り体力 2 の人を増やす.

a[2] -= o;

b[4] -= o;

// 2-7. Step6.

// -> 体力 4 の人が, 重さ 3 の荷物を持つ.

o = min(a[2], b[3]);

b[0] += o; // 残り体力 1 の人を増やす.

a[2] -= o;

b[3] -= o;

// 2-8. Step7.

// -> 残り体力 2以上の人が, 重さ 2 の荷物を持つ.

// 残り体力 5.

o = min(a[1], b[4]);

b[2] += o; // 残り体力 3 の人を増やす.

a[1] -= o;

b[4] -= o;

// 残り体力 4.

o = min(a[1], b[3]);

b[1] += o; // 残り体力 2 の人を増やす.

a[1] -= o;

b[3] -= o;

// 残り体力 3.

o = min(a[1], b[2]);

b[0] += o; // 残り体力 1 の人を増やす.

a[1] -= o;

b[2] -= o;

// 残り体力 2.

o = min(a[1], b[1]);

a[1] -= o;

b[1] -= o;

// 2-9. Step8.

// -> 残り体力 1以上の人が, 重さ 1 の荷物を持つ.

// 残り体力 5.

o = min(a[0], b[4]);

b[3] += o; // 残り体力 4 の人を増やす.

a[0] -= o;

b[4] -= o;

// 残り体力 4.

o = min(a[0], b[3]);

b[2] += o; // 残り体力 3 の人を増やす.

a[0] -= o;

b[3] -= o;

// 残り体力 3.

o = min(a[0], b[2]);

b[1] += o; // 残り体力 2 の人を増やす.

a[0] -= o;

b[2] -= o;

// 残り体力 2.

o = min(a[0], b[1]);

b[0] += o; // 残り体力 1 の人を増やす.

a[0] -= o;

b[1] -= o;

// 残り体力 1.

o = min(a[0], b[0]);

a[0] -= o;

b[0] -= o;

// 2-10. 出力.

LL ans = 0;

rep(j, 5) ans += a[j];

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

}

return 0;

}

[入力例]
3
5 1 0 0 1
0 0 0 2 1
0 3 0 0 0
0 0 2 0 0
10000000000000000 0 0 0 0
0 0 0 0 2000000000000000

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

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

[出力例]
Yes
Yes
Yes
Yes
Yes

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

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

[入力例]
30
4736 652 4583 6377 1597
8938 11245 5687 2942 1669
5463 1542 5058 2635 6214
7208 129 10478 10210 7131
3444 3342 3013 810 1573
363 1159 4324 99 1684
4683 6063 910 1382 7313
8436 2778 8775 3803 7507
4719 4910 8740 3752 8851
11313 2566 10001 9487 8976
8823 5515 9340 11275 10231
9358 2676 2884 451 2384
4857 3539 2594 4775 3193
3007 2610 4228 10693 3277
4608 4158 11708 6559 3383
2359 2399 6914 1167 4975
8141 4933 5370 2458 4976
1670 1881 2905 1144 1017
11820 8030 3539 8741 1074
209 5655 5606 4350 2281
174 8883 3762 7666 2423
12244 2773 2089 10577 3312
363 694 9803 6172 3573
5009 8611 11 3200 6165
3653 9811 6193 508 5619
5646 11988 6557 10264 7174
7962 1308 3615 9979 7739
1514 8295 10587 776 10807
5104 58 274 2361 11025
9355 225 7506 10287 11062
5367 9615 7668 7538 10932
371 1729 2728 10289 11516
8743 10524 6069 8198 10158
2925 6812 4133 11672 11499
2503 11237 2692 577 10567
3170 1318 9652 2333 10572
5369 1267 8608 2146 9466
3422 7021 5493 3181 9636
6025 4947 11230 3907 1864
1877 11256 1516 793 1997
1577 2439 8331 8472 4652
5496 723 4187 6943 4853
1773 11463 634 2337 1877
985 7083 11433 5979 1997
8012 1682 11478 3820 5897
5654 12342 3699 8523 5996
7786 3524 3335 6034 9057
3193 11703 10927 9535 9948
2676 480 7916 5608 9541
4481 1611 9242 6065 9740
1241 9799 3907 437 6700
9516 7654 1774 9564 8078
1462 723 2367 3068 7547
10838 361 10818 11597 7606
7872 4023 8552 5344 5425
1414 12181 2373 3322 6531
3928 10822 4620 2205 5016
1788 825 1998 11854 7000
7980 10848 3678 593 6726
9115 7408 6206 10854 6732

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

[入力例]
10
507748368 726522441 716842295 896598460 320433421
807756860 1178694558 696537829 675310808 321433525
1100909478 52594898 732721689 103256278 673683127
491553713 300979021 676273796 175896042 673693246
733173811 157956974 318073620 1203738633 103785639
574388248 204673136 539204115 1293133539 103788739
797087955 846601242 160116906 647766959 1164301869
84091606 868364510 1139454715 309964343 1164301884
467107126 467648868 300152068 23853124 708038233
192141104 1014838572 217300457 575553789 708038242
406340697 1217472541 176376639 1057125688 838469709
316724026 430450759 862185393 569966560 838469747
770761652 169240487 470842492 261863093 144541641
619970914 889107620 228698634 972783556 144541683
199041083 986396475 933182708 881589693 265895695
509144341 28749492 1164256597 972818486 265895787
1064560339 275860069 734979313 470598359 499844092
589489072 264860113 1187179191 738120897 499844130
176821395 342098591 214641446 636905853 801658981
552727141 433876986 568539870 870496264 801659031

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

[入力例]

5 1 0 0 1

0 0 0 2 1

0 3 0 0 0

0 0 2 0 0

10000000000000000 0 0 0 0

0 0 0 0 2000000000000000

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 4 3 2 1

4 2 2 4 1

6 5 4 3 2

2 1 3 6 3

7 6 5 4 3

1 6 4 5 4

8 7 6 5 4

0 9 3 6 6

9 8 7 6 5

3 6 9 7 5

[出力例]

Yes

[入力例]

9 3 5 0 1

3 7 0 1 10

3 0 1 3 5

4 10 11 3 1

1 1 6 11 11

2 5 7 6 7

0 4 10 3 3

11 11 9 8 9

10 7 8 11 1

1 3 10 9 3

5 8 8 9 0

10 8 10 10 5

9 0 6 3 0

1 5 5 8 4

0 2 2 1 9

4 2 6 3 10

1 1 8 3 9

3 2 1 7 0

10 0 9 7 9

3 1 11 7 8

9 8 6 3 1

9 2 7 10 11

6 6 5 9 4

3 10 0 8 10

2 0 10 11 1

5 8 3 5 7

5 8 6 8 9

5 5 4 11 10

0 6 11 4 9

2 3 8 3 13

[出力例]

Yes

[入力例]

4736 652 4583 6377 1597

8938 11245 5687 2942 1669

5463 1542 5058 2635 6214

7208 129 10478 10210 7131

3444 3342 3013 810 1573

363 1159 4324 99 1684

4683 6063 910 1382 7313

8436 2778 8775 3803 7507

4719 4910 8740 3752 8851

11313 2566 10001 9487 8976

8823 5515 9340 11275 10231

9358 2676 2884 451 2384

4857 3539 2594 4775 3193

3007 2610 4228 10693 3277

4608 4158 11708 6559 3383

2359 2399 6914 1167 4975

8141 4933 5370 2458 4976

1670 1881 2905 1144 1017

11820 8030 3539 8741 1074

209 5655 5606 4350 2281

174 8883 3762 7666 2423

12244 2773 2089 10577 3312

363 694 9803 6172 3573

5009 8611 11 3200 6165

3653 9811 6193 508 5619

5646 11988 6557 10264 7174

7962 1308 3615 9979 7739

1514 8295 10587 776 10807

5104 58 274 2361 11025

9355 225 7506 10287 11062

5367 9615 7668 7538 10932

371 1729 2728 10289 11516

8743 10524 6069 8198 10158

2925 6812 4133 11672 11499

2503 11237 2692 577 10567

3170 1318 9652 2333 10572

5369 1267 8608 2146 9466

3422 7021 5493 3181 9636

6025 4947 11230 3907 1864

1877 11256 1516 793 1997

1577 2439 8331 8472 4652

5496 723 4187 6943 4853

1773 11463 634 2337 1877

985 7083 11433 5979 1997

8012 1682 11478 3820 5897

5654 12342 3699 8523 5996

7786 3524 3335 6034 9057

3193 11703 10927 9535 9948

2676 480 7916 5608 9541

4481 1611 9242 6065 9740

1241 9799 3907 437 6700

9516 7654 1774 9564 8078

1462 723 2367 3068 7547

10838 361 10818 11597 7606

7872 4023 8552 5344 5425

1414 12181 2373 3322 6531

3928 10822 4620 2205 5016

1788 825 1998 11854 7000

7980 10848 3678 593 6726

9115 7408 6206 10854 6732

[出力例]

Yes

[入力例]

507748368 726522441 716842295 896598460 320433421

807756860 1178694558 696537829 675310808 321433525

1100909478 52594898 732721689 103256278 673683127

491553713 300979021 676273796 175896042 673693246

733173811 157956974 318073620 1203738633 103785639

574388248 204673136 539204115 1293133539 103788739

797087955 846601242 160116906 647766959 1164301869

84091606 868364510 1139454715 309964343 1164301884

467107126 467648868 300152068 23853124 708038233

192141104 1014838572 217300457 575553789 708038242

406340697 1217472541 176376639 1057125688 838469709

316724026 430450759 862185393 569966560 838469747

770761652 169240487 470842492 261863093 144541641

619970914 889107620 228698634 972783556 144541683

199041083 986396475 933182708 881589693 265895695

509144341 28749492 1164256597 972818486 265895787

1064560339 275860069 734979313 470598359 499844092

589489072 264860113 1187179191 738120897 499844130

176821395 342098591 214641446 636905853 801658981

552727141 433876986 568539870 870496264 801659031

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 226

2021年11月16日2021年11月16日

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

C++の練習を兼ねて, 第八回アルゴリズム実技検定の問題M (バランス) を解いてみた.

■感想.
1. 問題Mは, 方針が見えなかったので, 解説を参考に提出して, AC版に到達出来た.
2. 実装に苦労したものの, 個人的には, 各頂点に割り当て可能な, 0以上の整数が決まっていくロジックが面白いと感じた.
3. 幅優先探索の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第八回アルゴリズム実技検定の各リンクをご覧下さい.

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    map<P, int> sum, use;
    rep(i, M){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
        
        // 辺情報を保存.
        sum[{a, b}] = c;
        use[{a, b}] = 0;
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* memo){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s を 訪問.
        memo[s] = 1;
        C[s].insert({0, 1});
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &v : G[u]){
                // 辺を設定.
                P eCur = {min(u, v), max(u, v)};
                P cCur = *C[u].begin();
                
                // 頂点が訪問済みで無い場合.
                if(!memo[v]){
                    // 訪問済みを設定.
                    memo[v] = 1;
                    q.push(v);
                    use[eCur] = 1;
                    
                    // 隣接頂点の条件を設定.
                    P cNex;
                    cNex.a = sum[eCur] - cCur.a;
                    
                    // (p + x)型.
                    if(cCur.b == 1) cNex.b = -1;
                    
                    // (q - x)型.
                    if(cCur.b == -1) cNex.b = 1;
                    
                    // 保存.
                    C[v].insert(cNex);
                    
                    // 次へ.
                    continue;
                }
                
                // 頂点が訪問済みでも, 辺については, 未訪問の場合.
                if(!use[eCur]){
                    // 隣接頂点の条件を設定.
                    P cNex;
                    cNex.a = sum[eCur] - cCur.a;
                    
                    // (p + x)型.
                    if(cCur.b == 1) cNex.b = -1;
                    
                    // (q - x)型.
                    if(cCur.b == -1) cNex.b = 1;
                    
                    // 保存.
                    C[v].insert(cNex);
                }
            }
        }
        return;
    };
    
    // 3. 書き込む数に関する条件を抽出.
    int memo[N];
    rep(i, N) memo[i] = 0;
    bfs(G, 0, memo);
    
    // 4. 区間をチェック.
    int cMin = -2020202020, cMax = 2020202020;
    set<int> st;
    bool ok = true;
    rep(i, N){
        // (p + x)型, (q - x)型 を カウント.
        int pCount = 0, mCount = 0;
        for(auto &p : C[i]){
            if(p.b == 1) pCount++;
            else         mCount++;
        }
        
        // 両者のいずれかが, 二個以上ある.
        if(pCount > 1 || mCount > 1){
            ok = false;
            break;
        }
        
        // (p + x)型, (q - x)型 が, 一個ずつある.
        if(pCount == 1 && mCount == 1){
            int x = 0;
            for(auto &p : C[i]){
                if(p.b == -1) x += p.a;
                else          x -= p.a;
            }
            
            // 負数の場合.
            if(x < 0) ok = false;
            
            // 正数の場合.
            if(x >= 0){
                 // 偶数の場合.
                 if(x % 2 == 0) st.insert(x / 2);
                 
                 // 奇数の場合.
                 if(x % 2 != 0) ok = false;
            }
            
            // 次へ.
            continue;
        }
        
        // (p + x)型のみ.
        if(pCount == 1){
            P p = *C[i].begin();
            cMin = max(cMin, -p.a);
        }
        
        // (q - x)型のみ.
        if(mCount == 1){
            P p = *C[i].begin();
            cMax = min(cMax, p.a);
        }
    }
    
    // 5. 例外.
    // 5-1. 一意に定まる値が, 二通り以上存在する場合.
    if(st.size() > 1) ok = false;
    
    // 5-2. 大小逆転の場合.
    if(cMax < cMin) ok = false;
    
    // 5-3. 一意に定まる値が, 範囲外の場合.
    if(st.size() == 1){
        int x = *st.begin();
        if(x < cMin || x > cMax) ok = false;
    }
    
    // 5-4. 出力.
    if(!ok){
        puts("-1");
        return 0;
    }
    
    // 6. 上記以外.
    int x = cMin;
    if(st.size() == 1) x = *st.begin();
    rep(i, N){
        P p = *C[i].begin();
        printf("%d\n", (p.b == 1) ? x + p.a : p.a - x);
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

// 解き直し.

// https://atcoder.jp/contests/past202109-open/editorial/2659

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

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

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

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

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

#define a first

#define b second

#define pb push_back

set<P> C[101010];

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

map<P, int> sum, use;

rep(i, M){

int a, b, c;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

// 辺情報を保存.

sum[{a, b}] = c;

use[{a, b}] = 0;

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

// 探索地点 s を訪問.

memo[s] = 1;

C[s].insert({0, 1});

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &v : G[u]){

// 辺を設定.

P eCur = {min(u, v), max(u, v)};

P cCur = *C[u].begin();

// 頂点が訪問済みで無い場合.

if(!memo[v]){

// 訪問済みを設定.

memo[v] = 1;

q.push(v);

use[eCur] = 1;

// 隣接頂点の条件を設定.

P cNex;

cNex.a = sum[eCur] - cCur.a;

// (p + x)型.

if(cCur.b == 1) cNex.b = -1;

// (q - x)型.

if(cCur.b == -1) cNex.b = 1;

// 保存.

C[v].insert(cNex);

// 次へ.

continue;

}

// 頂点が訪問済みでも, 辺については, 未訪問の場合.

if(!use[eCur]){

// 隣接頂点の条件を設定.

P cNex;

cNex.a = sum[eCur] - cCur.a;

// (p + x)型.

if(cCur.b == 1) cNex.b = -1;

// (q - x)型.

if(cCur.b == -1) cNex.b = 1;

// 保存.

C[v].insert(cNex);

}

return;

};

// 3. 書き込む数に関する条件を抽出.

int memo[N];

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

bfs(G, 0, memo);

// 4. 区間をチェック.

int cMin = -2020202020, cMax = 2020202020;

set<int> st;

bool ok = true;

rep(i, N){

// (p + x)型, (q - x)型をカウント.

int pCount = 0, mCount = 0;

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

if(p.b == 1) pCount++;

else mCount++;

}

// 両者のいずれかが, 二個以上ある.

if(pCount > 1 || mCount > 1){

ok = false;

break;

}

// (p + x)型, (q - x)型が, 一個ずつある.

if(pCount == 1 && mCount == 1){

int x = 0;

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

if(p.b == -1) x += p.a;

else x -= p.a;

}

// 負数の場合.

if(x < 0) ok = false;

// 正数の場合.

if(x >= 0){

// 偶数の場合.

if(x % 2 == 0) st.insert(x / 2);

// 奇数の場合.

if(x % 2 != 0) ok = false;

}

// 次へ.

continue;

}

// (p + x)型のみ.

if(pCount == 1){

P p = *C[i].begin();

cMin = max(cMin, -p.a);

}

// (q - x)型のみ.

if(mCount == 1){

P p = *C[i].begin();

cMax = min(cMax, p.a);

}

// 5. 例外.

// 5-1. 一意に定まる値が, 二通り以上存在する場合.

if(st.size() > 1) ok = false;

// 5-2. 大小逆転の場合.

if(cMax < cMin) ok = false;

// 5-3. 一意に定まる値が, 範囲外の場合.

if(st.size() == 1){

int x = *st.begin();

if(x < cMin || x > cMax) ok = false;

}

// 5-4. 出力.

if(!ok){

puts("-1");

return 0;

}

// 6. 上記以外.

int x = cMin;

if(st.size() == 1) x = *st.begin();

rep(i, N){

P p = *C[i].begin();

printf("%d\n", (p.b == 1) ? x + p.a : p.a - x);

}

return 0;

}

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

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

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

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

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

[出力例]
-1

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

[出力例]
0
6
4
7
1

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

[出力例]
-1

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

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

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

[出力例]
0
0
1

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

[出力例]
-1

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

[出力例]
2
2
3
3
2

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

[入力例]

3 2

1 2 2

2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 2 0

2 3 0

1 3 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 4

1 2 3

2 3 4

3 4 5

1 4 6

[出力例]

-1

[入力例]

5 5

1 2 6

2 3 10

3 5 5

4 5 8

1 4 7

[出力例]

[入力例]

7 8

1 2 5

2 4 4

2 3 7

3 6 5

6 7 9

3 7 6

4 5 2

5 7 8

[出力例]

-1

[入力例]

10 10

1 2 8

1 5 10

1 4 6

2 10 5

2 3 7

3 9 6

3 7 9

7 8 10

8 9 7

6 7 5

[出力例]

[入力例]

3 3

1 2 0

1 3 1

2 3 1

[出力例]

[入力例]

5 5

1 2 4

1 5 4

2 4 6

3 4 6

3 5 5

[出力例]

-1

[入力例]

5 5

1 2 4

1 5 4

2 4 5

3 4 6

3 5 5

[出力例]

[入力例]

18 25

1 5 8

2 5 6

1 6 12

2 6 10

2 3 5

2 8 7

3 6 13

4 6 10

4 7 3

3 7 6

7 15 11

7 16 5

15 16 12

1 12 11

12 13 17

13 14 16

12 14 15

8 9 11

9 10 8

9 11 10

10 11 8

9 17 7

11 17 7

11 18 8

17 18 5

[出力例]

■参照サイト
第八回アルゴリズム実技検定

2021年11月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 226 の問題F (Score of Permutations) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 実装に苦労したものの, 何とか分割数の実装(TLE回避版)が出来たので, 良かったと思う.
3. 深さ優先探索(応用版, 分割数) の復習が出来たので, 非常に, 良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc226/editorial/2878
// C++(GCC 9.2.1)
#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--)
#define pb push_back
#define all(x) x.begin(), x.end()
const LL MOD = 998244353;
LL FAC[66], INV[66];
set<vi> st[66];

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

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, 66) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, 66)     INV[i] = mPow(FAC[i], MOD - 2);
    
    // 3. 分割数(その１).
    // -> TLE版(N = 30 (5604個) で, 495[ms]かかってしまう).
    /*
    auto f = [&](int cur) -> void {
        st[cur].insert({cur});
        repx(i, 1, cur / 2 + 1){
            set<vi> l = st[i];
            set<vi> r = st[cur - i];
            for(auto &p : l){
                for(auto &q : r){
                    vi v;
                    for(auto &x : p) v.pb(x);
                    for(auto &x : q) v.pb(x);
                    sort(all(v));
                    st[cur].insert(v);
                }
            }
        }
    };
    repx(i, 1, N + 1) f(i);
    */
    /*
    repx(i, 1, 31) f(i);
    printf("%d\n", st[30].size());
    for(auto &p : st[30]){
        for(auto &q : p) printf("%d ", q);
        puts("");
    }
    */
    
    // 4. 分割数(その２).
    // -> TLE回避版(N = 50 (204226個) で, 237[ms]程度).
    set<vi> pf;
    auto dfs = [&](auto &&self, vi vCur, int tCur) -> void {
        // 4-1. 終了条件.
        if(tCur > N) return;
        
        // 4-2. 分割完了.
        if(tCur == N){
            pf.insert(vCur);
            return;
        }
        
        
        // 4-3. すでに分割済みの状態から, 分割を繰り返す.
        int s = 1;
        if(vCur.size()) s = vCur.back();
        repx(i, s, N + 1 - tCur){
            vi vNex = vCur;
            int tNex = tCur;
            vNex.pb(i);
            tNex += i;
            self(self, vNex, tNex);
        }
    };
    dfs(dfs, {}, 0);
    /*
    for(auto &p : pf){
        for(auto &q : p) printf("%d ", q);
        puts("");
    }
    */
    
    // 5. スコアを集計.
    LL ans = 0;
    for(auto &p : pf){
        // 5-1. 巡回置換の分割を一つ取ってくる.
        int c[66];
        rep(i, 66) c[i] = 0;
        for(auto &q : p) c[q]++;
        
        // 5-2. 前項の巡回置換の分割を満たす個数を計算.
        // -> 解説にある数式を適用.
        vi v;
        LL s = FAC[N];
        rep(i, 66){
            if(c[i]){
                s *= mPow(INV[i], c[i]);
                s %= MOD;
                s *= INV[c[i]];
                s %= MOD;
                s *= mPow(FAC[i - 1], c[i]);
                s %= MOD;
                
                // 巡回置換の長さを保存.
                v.pb(i);
            }
        }
        
        // 5-3. スコアを計算.
        // -> MOD版使わずに, とりあえず, 実装.
        LL lcm = 1;
        for(auto &q : v){
            LL g = __gcd(lcm, (LL)q);
            lcm *= q;
            lcm /= g;
        }
        
        // 5-4. スコアを集計.
        ans += mPow(lcm, K) * s;
        ans %= MOD;
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

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

// 解き直し.

// https://atcoder.jp/contests/abc226/editorial/2878

// C++(GCC 9.2.1)

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

#define pb push_back

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

const LL MOD = 998244353;

LL FAC[66], INV[66];

set<vi> st[66];

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

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

// @param b: 指数.

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

LL mPow(LL a, LL b){

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

int main(){

// 1. 入力情報.

int N, K;

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

// 2. 事前計算.

FAC[0] = 1;

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

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

// 3. 分割数(その１).

// -> TLE版(N = 30 (5604個) で, 495[ms]かかってしまう).

auto f = [&](int cur) -> void {

st[cur].insert({cur});

repx(i, 1, cur / 2 + 1){

set<vi> l = st[i];

set<vi> r = st[cur - i];

for(auto &p : l){

for(auto &q : r){

vi v;

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

for(auto &x : q) v.pb(x);

sort(all(v));

st[cur].insert(v);

}

};

repx(i, 1, N + 1) f(i);

repx(i, 1, 31) f(i);

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

for(auto &p : st[30]){

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

puts("");

}

// 4. 分割数(その２).

// -> TLE回避版(N = 50 (204226個) で, 237[ms]程度).

set<vi> pf;

auto dfs = [&](auto &&self, vi vCur, int tCur) -> void {

// 4-1. 終了条件.

if(tCur > N) return;

// 4-2. 分割完了.

if(tCur == N){

pf.insert(vCur);

return;

}

// 4-3. すでに分割済みの状態から, 分割を繰り返す.

int s = 1;

if(vCur.size()) s = vCur.back();

repx(i, s, N + 1 - tCur){

vi vNex = vCur;

int tNex = tCur;

vNex.pb(i);

tNex += i;

self(self, vNex, tNex);

}

};

dfs(dfs, {}, 0);

for(auto &p : pf){

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

puts("");

}

// 5. スコアを集計.

LL ans = 0;

for(auto &p : pf){

// 5-1. 巡回置換の分割を一つ取ってくる.

int c[66];

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

for(auto &q : p) c[q]++;

// 5-2. 前項の巡回置換の分割を満たす個数を計算.

// -> 解説にある数式を適用.

vi v;

LL s = FAC[N];

rep(i, 66){

if(c[i]){

s *= mPow(INV[i], c[i]);

s %= MOD;

s *= INV[c[i]];

s %= MOD;

s *= mPow(FAC[i - 1], c[i]);

s %= MOD;

// 巡回置換の長さを保存.

v.pb(i);

}

// 5-3. スコアを計算.

// -> MOD版使わずに, とりあえず, 実装.

LL lcm = 1;

for(auto &q : v){

LL g = __gcd(lcm, (LL)q);

lcm *= q;

lcm /= g;

}

// 5-4. スコアを集計.

ans += mPow(lcm, K) * s;

ans %= MOD;

}

// 6. 出力.

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

return 0;

}

[入力例]
2 2

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

[入力例]
3 3

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

[入力例]
50 10000

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

[入力例]
5 1

[出力例]
471

[入力例]
7 3

[出力例]
1922299

[入力例]
20 21

[出力例]
147970674

[入力例]
60 2021

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

[入力例]

2 2

[出力例]

※AtCoderテストケースより

[入力例]

3 3

[出力例]

※AtCoderテストケースより

[入力例]

50 10000

[出力例]

77436607

※AtCoderテストケースより

[入力例]

5 1

[出力例]

471

[入力例]

7 3

[出力例]

1922299

[入力例]

20 21

[出力例]

147970674

[入力例]

60 2021

[出力例]

139835665

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

■参照サイト
AtCoder Beginner Contest 226

2021年11月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 227 の問題C (ABC conjecture) ～問題D (Project Planning) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. B を 固定したときの A, C の 個数.
    LL ans = 0;
    repx(b, 1, (int)sqrt(N) + 1){
        repx(a, 1, b + 1){
            LL c = N / (a * b);
            if(c >= b) ans += (c - b) + 1;
            else       break;
        }
    }
    
    // 3. 出力.
    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. B を固定したときの A, C の個数.

LL ans = 0;

repx(b, 1, (int)sqrt(N) + 1){

repx(a, 1, b + 1){

LL c = N / (a * b);

if(c >= b) ans += (c - b) + 1;

else break;

}

// 3. 出力.

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

return 0;

}

[入力例]
4

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

[入力例]
100

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

[入力例]
100000000000

[出力例]
5745290566750

[入力例]
7

[出力例]
9

[入力例]
2021

[出力例]
13439

[入力例]
20211114

[出力例]
536312958

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

100

[出力例]

323

※AtCoderテストケースより

[入力例]

100000000000

[出力例]

5745290566750

[入力例]

[出力例]

[入力例]

2021

[出力例]

13439

[入力例]

20211114

[出力例]

536312958

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 評価関数.
    auto f = [&](LL m) -> bool {
        // 2-1. m個以上のプロジェクトを作成できるか？
        LL o = 0;
        rep(i, N) o += min(a[i], m);
        
        // 2-2. 判定結果.
        return (m <= o / K);
    };
    
    // 3. 二分探索で確認してみる.
    // LL l = 0, h = 2e17 + 1, m;
    LL l = 0, h = 2e18 + 1, m; // テストケース(case_04.txt) で NG となったため, 修正.
    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("%lld\n", l);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc227/editorial/2911

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[202020];

int main(){

// 1. 入力情報.

int N;

LL K;

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

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

// 2. 評価関数.

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

// 2-1. m個以上のプロジェクトを作成できるか？

LL o = 0;

rep(i, N) o += min(a[i], m);

// 2-2. 判定結果.

return (m <= o / K);

};

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

// LL l = 0, h = 2e17 + 1, m;

LL l = 0, h = 2e18 + 1, m; // テストケース(case_04.txt) で NG となったため, 修正.

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("%lld\n", l);

return 0;

}

[入力例]
3 3
2 3 4

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

[入力例]
4 2
1 1 3 4

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

[入力例]
4 3
1 1 3 4

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

[入力例]
5 3
2 5 12 16 25

[出力例]
17

[入力例]
5 3
2 5 12 18 19

[出力例]
18

[入力例]
5 3
2 5 12 25 26

[出力例]
19

[入力例]
30 5
51 40 69 20 57 53 85 103 59 45 54 36 106 36 108 54 23 74 54 115 51 98 28 111 14 60 105 51 106 60

[出力例]
385

[入力例]
60 7
143968 673147 442360 836832 419701 312333 409321 1052604 331047 1152522 1050980 374482 36309 862087 876431 904817 118489 796446 1075067 1170994 850846 564510 466887 368936 520578 128485 1061395 1169029 636245 797907 612395 861793 1156053 1219440 820464 953251 694532 670293 620020 845759 563298 230762 218198 784660 496413 377992 686019 1183415 1064335 386372 1031504 1034102 1108929 150314 530511 209176 571970 680992 514704 620123

[出力例]
5786077

[入力例]
100 11
1024501679 432300252 711933293 751510314 817097636 571084915 913664931 290328615 202462701 497433395 551433422 794760635 1032819249 158046377 685486175 364539343 797691083 786118670 768254660 271146884 1090909860 530625902 1194134546 233219966 1167927310 466581498 11363299141 941737868 22896929 2442499370 4822707 630671761 198619739 247153309 567133826 201648231 201283771 17250183 653527938 1196698698 540477135 681998865 10802691547 607194413 705916648 711159161 557757099 465991201 726423073 1152413183 661237656 967111521 1177078300 491129186 1126170273 288057207 478189316 746709355 244663800 431617238 839108540 926642182 301630237 791946161 1051559761 1230751212 596770253 242151194 333912399 1110331404 480986811 911846005 730919848 1171935205 368032628 968229990 1189200274 965768086 472393882 260047484 1045594673 905464959 862626471 8810402505 831520978 610164180 227037971 771013523 118804047 894125994 4550884525 599408963 818696628 1124244223 1174937406 152595882 271334769 716664895 807452882 3370179580

[出力例]
8977841209

[入力例]

3 3

2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

4 2

1 1 3 4

[出力例]

※AtCoderテストケースより

[入力例]

4 3

1 1 3 4

[出力例]

※AtCoderテストケースより

[入力例]

5 3

2 5 12 16 25

[出力例]

[入力例]

5 3

2 5 12 18 19

[出力例]

[入力例]

5 3

2 5 12 25 26

[出力例]

[入力例]

30 5

51 40 69 20 57 53 85 103 59 45 54 36 106 36 108 54 23 74 54 115 51 98 28 111 14 60 105 51 106 60

[出力例]

385

[入力例]

60 7

143968 673147 442360 836832 419701 312333 409321 1052604 331047 1152522 1050980 374482 36309 862087 876431 904817 118489 796446 1075067 1170994 850846 564510 466887 368936 520578 128485 1061395 1169029 636245 797907 612395 861793 1156053 1219440 820464 953251 694532 670293 620020 845759 563298 230762 218198 784660 496413 377992 686019 1183415 1064335 386372 1031504 1034102 1108929 150314 530511 209176 571970 680992 514704 620123

[出力例]

5786077

[入力例]

100 11

1024501679 432300252 711933293 751510314 817097636 571084915 913664931 290328615 202462701 497433395 551433422 794760635 1032819249 158046377 685486175 364539343 797691083 786118670 768254660 271146884 1090909860 530625902 1194134546 233219966 1167927310 466581498 11363299141 941737868 22896929 2442499370 4822707 630671761 198619739 247153309 567133826 201648231 201283771 17250183 653527938 1196698698 540477135 681998865 10802691547 607194413 705916648 711159161 557757099 465991201 726423073 1152413183 661237656 967111521 1177078300 491129186 1126170273 288057207 478189316 746709355 244663800 431617238 839108540 926642182 301630237 791946161 1051559761 1230751212 596770253 242151194 333912399 1110331404 480986811 911846005 730919848 1171935205 368032628 968229990 1189200274 965768086 472393882 260047484 1045594673 905464959 862626471 8810402505 831520978 610164180 227037971 771013523 118804047 894125994 4550884525 599408963 818696628 1124244223 1174937406 152595882 271334769 716664895 807452882 3370179580

[出力例]

8977841209

■参照サイト
キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)

2021年11月10日2021年11月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 226 の問題E (Just one) を解いてみた.

■感想.
1. 問題Eは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 個人的には, 向き付けを行う際に, 頂点次数の制約が発生する点が, 非常に面白いと思った.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vs = vector<set<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--)
const LL MOD = 998244353;

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vs G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        G[u].insert(v);
        G[v].insert(u);
    }
    
    // 2. 頂点次数が, 0 のものがある.
    rep(i, N){
        if(!G[i].size()){
            puts("0");
            return 0;
        }
    }
    
    // 3. 頂点次数が, 1 のものを削除.
    int memo[N];
    rep(i, N) memo[i] = 0;
    queue<int> q;
    rep(i, N) if(G[i].size() == 1) q.push(i), memo[i] = 1;
    while(!q.empty()){
        // キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 辺を削除.
        int v = *G[u].begin();
        G[v].erase(u);
        G[u].erase(v);
        
        // 次数が, 1 ならば追加.
        if(!memo[v] && G[v].size() == 1) q.push(v), memo[v] = 1;
    }
    
    // 4. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vs &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]){
                // 未訪問の頂点を処理.
                if(!c[e] && e != s) c[e] = l, q.push(e);
            }
        }
        return;
    };
    
    // 5. 連結成分に分解.
    // -> 頂点次数が, 0 となる頂点は, 除外.
    int connection[N], idx = 0;
    rep(i, N) connection[i] = 0;
    rep(i, N) if(!memo[i] && !connection[i]) bfs(G, i, connection, ++idx);
    
    // 6. 連結成分が無い.
    if(!idx){
        puts("0");
        return 0;
    }
    
    // 7. 頂点次数が, 2 でないものがある場合.
    // -> 連結成分に分解した頂点に限定することに注意.
    rep(i, N){
        if(connection[i] && G[i].size() != 2){
            puts("0");
            return 0;
        }
    }
    
    // 8. 集計.
    LL ans = 1;
    rep(i, idx) ans <<= 1, ans %= MOD;
    
    // 9. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vs = vector<set<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--)

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

int N, M;

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

vs G(N);

rep(i, M){

int u, v;

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

u--, v--;

G[u].insert(v);

G[v].insert(u);

}

// 2. 頂点次数が, 0 のものがある.

rep(i, N){

if(!G[i].size()){

puts("0");

return 0;

}

// 3. 頂点次数が, 1 のものを削除.

int memo[N];

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

queue<int> q;

rep(i, N) if(G[i].size() == 1) q.push(i), memo[i] = 1;

while(!q.empty()){

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

int u = q.front();

q.pop();

// 辺を削除.

int v = *G[u].begin();

G[v].erase(u);

G[u].erase(v);

// 次数が, 1 ならば追加.

if(!memo[v] && G[v].size() == 1) q.push(v), memo[v] = 1;

}

// 4. bfs.

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

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

// 空のキュー.

queue<int> q;

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

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 未訪問の頂点を処理.

if(!c[e] && e != s) c[e] = l, q.push(e);

}

return;

};

// 5. 連結成分に分解.

// -> 頂点次数が, 0 となる頂点は, 除外.

int connection[N], idx = 0;

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

rep(i, N) if(!memo[i] && !connection[i]) bfs(G, i, connection, ++idx);

// 6. 連結成分が無い.

if(!idx){

puts("0");

return 0;

}

// 7. 頂点次数が, 2 でないものがある場合.

// -> 連結成分に分解した頂点に限定することに注意.

rep(i, N){

if(connection[i] && G[i].size() != 2){

puts("0");

return 0;

}

// 8. 集計.

LL ans = 1;

rep(i, idx) ans <<= 1, ans %= MOD;

// 9. 出力.

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

return 0;

}

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

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

[入力例]
2 1
1 2

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

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

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

[入力例]
3 1
2 3

[出力例]
0

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

[出力例]
2

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

[出力例]
64

[入力例]

3 3

1 2

1 3

2 3

[出力例]

※AtCoderテストケースより

[入力例]

2 1

1 2

[出力例]

※AtCoderテストケースより

[入力例]

7 7

1 2

2 3

3 4

4 2

5 6

6 7

7 5

[出力例]

※AtCoderテストケースより

[入力例]

3 1

2 3

[出力例]

[入力例]

5 5

1 2

2 3

3 4

4 5

5 1

[出力例]

[入力例]

30 30

1 2

2 3

3 1

2 7

4 5

5 6

6 4

8 4

9 10

10 11

11 9

9 12

12 13

12 16

11 14

15 14

17 18

18 19

19 17

25 19

20 21

21 22

22 23

23 24

24 20

22 30

26 27

27 28

28 29

29 26

[出力例]

■参照サイト
AtCoder Beginner Contest 226

C++の練習を兼ねて, AtCoder Beginner Contest 229 の 問題C (Cheese) ～ 問題D (Longest X) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 008 の 問題A (たこ焼き買えるかな？) ～ 問題B (謎のたこ焼きおじさん) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 129 の 問題D (-1+2-1) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 129 の 問題C (Multiple of 7) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 129 の 問題A (Smaller XOR) ～ 問題B (Range Point Distance) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 226 の 問題G (The baggage) を解いてみた.

C++の練習を兼ねて, 第八回 アルゴリズム実技検定 の 問題M (バランス) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 226 の 問題F (Score of Permutations) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 227 の 問題C (ABC conjecture) ～ 問題D (Project Planning) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 226 の 問題E (Just one) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 229 の問題C (Cheese) ～問題D (Longest X) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 008 の問題A (たこ焼き買えるかな？) ～問題B (謎のたこ焼きおじさん) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 129 の問題D (-1+2-1) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 129 の問題C (Multiple of 7) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 129 の問題A (Smaller XOR) ～問題B (Range Point Distance) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 226 の問題G (The baggage) を解いてみた.

C++の練習を兼ねて, 第八回アルゴリズム実技検定の問題M (バランス) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 226 の問題F (Score of Permutations) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 227 の問題C (ABC conjecture) ～問題D (Project Planning) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 226 の問題E (Just one) を解いてみた.