個人用メモ帳

2023年10月14日

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

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

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

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

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

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

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

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

// 2. dfs.

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

set<LL> st;

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

// 2-1. 保存.

st.insert(d);

// 2-2. 終了条件.

int r = d % 10;

if(r == 0) return;

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

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

};

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

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

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

// 4. K 番目は？

LL ans = 0;

for(auto &x : st){

ans = x;

if(--K == 0) break;

}

// 5. 出力.

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

return 0;

}

[入力例]
15

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

[入力例]
321

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

[入力例]
777

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

[入力例]
20

[出力例]
50

[入力例]
100

[出力例]
750

[入力例]
753

[出力例]
975421

[入力例]
1022

[出力例]
9876543210

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

321

[出力例]

9610

※AtCoderテストケースより

[入力例]

777

[出力例]

983210

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

100

[出力例]

750

[入力例]

753

[出力例]

975421

[入力例]

1022

[出力例]

9876543210

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

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

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

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

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

int main(){

// 1. 入力情報.

int N, M, P;

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

vl a(N), b(M);

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

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

// 2. sort.

sort(all(a));

sort(all(b));

// 3. 累積和.

vl bCum(M + 1, 0);

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

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

LL ans = 0;

rep(i, N){

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

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

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

}

// 5. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
150

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

[出力例]
150

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

[出力例]
14227081

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

[出力例]
3402202

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

[出力例]
282120162

[入力例]

2 2 7

3 5

6 1

[出力例]

※AtCoderテストケースより

[入力例]

1 3 2

1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

7 12 25514963

2436426 24979445 61648772 23690081 33933447 76190629 62703497

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

[出力例]

2115597124

※AtCoderテストケースより

[入力例]

5 3 123

1 2 3 4 5

6 7 8

[出力例]

150

[入力例]

5 3 10

11 12 13 14 15

16 17 18

[出力例]

150

[入力例]

12 15 100000

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

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

[出力例]

14227081

[入力例]

30 50 2500

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

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

[出力例]

3402202

[入力例]

100 120 33333

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

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

[出力例]

282120162

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

2023年10月9日2023年10月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 323 の問題C (World Tour Finals) ～問題D (Merge Slimes) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D で, スライム合成の繰り返す処理が, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vi a(M);
    rep(i, M) scanf("%d", &a[i]);
    vs s(N);
    rep(i, N){
        char c[202];
        scanf("%s", c);
        string b(c);
        s[i] = b;
    }
    
    // 2. 各プレイヤーの現在の総合得点は？
    vi scores(N, 0);
    rep(i, N){
        scores[i] = i + 1;
        rep(j, M) scores[i] += a[j] * (s[i][j] == 'o');
    }
    
    // 3. 各プレイヤーが解いてない問題の各得点は？
    vvi notSolved(N);
    rep(i, N){
        rep(j, M) if(s[i][j] == 'x') notSolved[i].pb(a[j]);
        sort(all(notSolved[i]));
        reverse(all(notSolved[i]));
    }
    
    // 4. 他プレイヤーの現在の総合得点の最大値は？
    vi maxScoreOnOtherPlayers(N, 0);
    rep(i, N){
        int maxScore = 0;
        rep(j, N) if(i != j) maxScore = max(maxScore, scores[j]);
        maxScoreOnOtherPlayers[i] = maxScore;
    }
    
    // 5. 出力.
    rep(i, N){
        int ans = 0;
        int cur = scores[i];
        for(auto &p : notSolved[i]){
            if(maxScoreOnOtherPlayers[i] >= cur){
                ++ans;
                cur += p;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using vs = vector<string>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

int N, M;

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

vi a(M);

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

vs s(N);

rep(i, N){

char c[202];

scanf("%s", c);

string b(c);

s[i] = b;

}

// 2. 各プレイヤーの現在の総合得点は？

vi scores(N, 0);

rep(i, N){

scores[i] = i + 1;

rep(j, M) scores[i] += a[j] * (s[i][j] == 'o');

}

// 3. 各プレイヤーが解いてない問題の各得点は？

vvi notSolved(N);

rep(i, N){

rep(j, M) if(s[i][j] == 'x') notSolved[i].pb(a[j]);

sort(all(notSolved[i]));

reverse(all(notSolved[i]));

}

// 4. 他プレイヤーの現在の総合得点の最大値は？

vi maxScoreOnOtherPlayers(N, 0);

rep(i, N){

int maxScore = 0;

rep(j, N) if(i != j) maxScore = max(maxScore, scores[j]);

maxScoreOnOtherPlayers[i] = maxScore;

}

// 5. 出力.

rep(i, N){

int ans = 0;

int cur = scores[i];

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

if(maxScoreOnOtherPlayers[i] >= cur){

++ans;

cur += p;

}

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

}

return 0;

}

[入力例]
3 4
1000 500 700 2000
xxxo
ooxx
oxox

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

[入力例]
5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

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

[入力例]
7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

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

[入力例]
3 5
500 500 1000 1000 2500
xxxxo
xxxox
xooxx

[出力例]
0
1
1

[入力例]
5 7
500 500 500 500 1000 1000 1500
ooxooxx
xoxxxxx
xxxxxxx
xxooxox
ooxxoxo

[出力例]
1
3
4
2
0

[入力例]

3 4

1000 500 700 2000

xxxo

ooxx

oxox

[出力例]

※AtCoderテストケースより

[入力例]

5 5

1000 1500 2000 2000 2500

xxxxx

oxxxx

xxxxx

oxxxx

[出力例]

※AtCoderテストケースより

[入力例]

7 8

500 500 500 500 500 500 500 500

xxxxxxxx

oxxxxxxx

ooxxxxxx

oooxxxxx

ooooxxxx

oooooxxx

ooooooxx

[出力例]

※AtCoderテストケースより

[入力例]

3 5

500 500 1000 1000 2500

xxxxo

xxxox

xooxx

[出力例]

[入力例]

5 7

500 500 500 500 1000 1000 1500

ooxooxx

xoxxxxx

xxxxxxx

xxooxox

ooxxoxo

[出力例]

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp slimes(N);
    rep(i, N) scanf("%lld %lld", &slimes[i].a, &slimes[i].b);
    
    // 2. sort.
    sort(all(slimes));
    
    // 3. スライムの合成.
    map<LL, LL> m;
    rep(i, N){
        // 初期化(スライムのサイズ, 匹数).
        LL slimeSize = slimes[i].a;
        LL slimeCount = slimes[i].b;
        
        // 前回以前を反映.
        if(m.count(slimes[i].a)) slimeCount += m[slimes[i].a];
        else                     m[slimes[i].a] = slimes[i].b;
        
        // 合成対象のスライム匹数が, 0匹になるまで, 繰り返し.
        while(slimeCount){
            // スライム出現.
            m[slimeSize * 2] += slimeCount / 2;
            
            // スライム消滅.
            m[slimeSize] = slimeCount % 2;
            
            // 更新(スライムのサイズ, 匹数).
            slimeSize *= 2;
            slimeCount = m[slimeSize];
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    for(auto &x : m) ans += x.b;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using P = pair<LL, LL>;

using vp = vector<P>;

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

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

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

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

#define a first

#define b second

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp slimes(N);

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

// 2. sort.

sort(all(slimes));

// 3. スライムの合成.

map<LL, LL> m;

rep(i, N){

// 初期化(スライムのサイズ, 匹数).

LL slimeSize = slimes[i].a;

LL slimeCount = slimes[i].b;

// 前回以前を反映.

if(m.count(slimes[i].a)) slimeCount += m[slimes[i].a];

else m[slimes[i].a] = slimes[i].b;

// 合成対象のスライム匹数が, 0匹になるまで, 繰り返し.

while(slimeCount){

// スライム出現.

m[slimeSize * 2] += slimeCount / 2;

// スライム消滅.

m[slimeSize] = slimeCount % 2;

// 更新(スライムのサイズ, 匹数).

slimeSize *= 2;

slimeCount = m[slimeSize];

}

// 4. 集計.

LL ans = 0;

for(auto &x : m) ans += x.b;

// 5. 出力.

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

return 0;

}

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

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

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

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

[入力例]
1
1000000000 1000000000

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

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

[出力例]
5

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

[出力例]
15

[入力例]
20
19 81
8 52
7 104
3 94
14 26
16 47
1 46
6 108
11 113
20 52
5 105
15 5
18 95
17 20
10 121
4 53
12 65
9 14
2 15
13 96

[出力例]
36

[入力例]
30
14 929755
10 812758
26 405849
5 775226
19 916477
13 786895
17 119046
30 492339
7 429931
1 267396
11 892144
24 812785
20 480207
2 516830
25 749069
18 430046
6 653612
22 1122701
28 336222
29 1020713
27 203310
12 441113
21 729150
9 414670
8 432888
23 510440
15 250019
4 956264
16 239998
3 783368

[出力例]
157

[入力例]
100
63 802
2 1186
54 547
22 466
95 387
41 615
90 1071
76 1087
74 1017
27 877
30 704
86 1126
82 286
68 348
37 30
11 128
100 824
48 720
1 870
9 794
38 188
17 646
24 844
99 8
23 1017
18 209
8 661
83 243
50 766
87 1030
65 406
66 632
53 299
69 843
4 232
29 152
81 819
85 1064
97 80
14 526
71 470
75 816
13 22
42 217
33 188
93 898
10 721
40 780
44 1078
84 31
98 468
60 816
45 585
91 404
61 1176
28 389
36 913
51 472
94 1203
88 472
57 1130
73 1183
12 788
62 691
5 1056
43 330
46 406
19 708
67 1213
55 983
96 30
52 817
21 1049
32 1178
92 1202
70 19
6 373
35 450
25 112
15 434
72 858
3 706
79 238
26 312
34 521
49 112
56 51
7 474
78 631
31 242
59 231
20 1049
80 678
64 906
39 286
58 106
77 473
89 233
16 1168
47 591

[出力例]
278

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

[入力例]

3 3

5 1

6 1

[出力例]

※AtCoderテストケースより

[入力例]

1 1

2 1

3 1

[出力例]

※AtCoderテストケースより

[入力例]

1000000000 1000000000

[出力例]

※AtCoderテストケースより

[入力例]

1 3

2 2

3 1

4 5

8 2

[出力例]

[入力例]

11 4

3 1

12 9

2 10

10 10

5 2

7 6

15 2

24 3

8 1

[出力例]

[入力例]

19 81

8 52

7 104

3 94

14 26

16 47

1 46

6 108

11 113

20 52

5 105

15 5

18 95

17 20

10 121

4 53

12 65

9 14

2 15

13 96

[出力例]

[入力例]

14 929755

10 812758

26 405849

5 775226

19 916477

13 786895

17 119046

30 492339

7 429931

1 267396

11 892144

24 812785

20 480207

2 516830

25 749069

18 430046

6 653612

22 1122701

28 336222

29 1020713

27 203310

12 441113

21 729150

9 414670

8 432888

23 510440

15 250019

4 956264

16 239998

3 783368

[出力例]

157

[入力例]

100

63 802

2 1186

54 547

22 466

95 387

41 615

90 1071

76 1087

74 1017

27 877

30 704

86 1126

82 286

68 348

37 30

11 128

100 824

48 720

1 870

9 794

38 188

17 646

24 844

99 8

23 1017

18 209

8 661

83 243

50 766

87 1030

65 406

66 632

53 299

69 843

4 232

29 152

81 819

85 1064

97 80

14 526

71 470

75 816

13 22

42 217

33 188

93 898

10 721

40 780

44 1078

84 31

98 468

60 816

45 585

91 404

61 1176

28 389

36 913

51 472

94 1203

88 472

57 1130

73 1183

12 788

62 691

5 1056

43 330

46 406

19 708

67 1213

55 983

96 30

52 817

21 1049

32 1178

92 1202

70 19

6 373

35 450

25 112

15 434

72 858

3 706

79 238

26 312

34 521

49 112

56 51

7 474

78 631

31 242

59 231

20 1049

80 678

64 906

39 286

58 106

77 473

89 233

16 1168

47 591

[出力例]

278

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

2023年10月1日

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

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題D (Sum of SCC) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc163/editorial/6696
// 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 C[33][33], dp[33][33][33 * 33];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. パスカルの三角形.
    C[0][0] = 1;
    repx(i, 1, 33){
        rep(j, 33){
            C[i][j] = (!j || j == i) ? 1LL : C[i - 1][j - 1] + C[i - 1][j];
            C[i][j] %= MOD;
        }
    }
    
    // 3. dp更新.
    dp[0][0][0] = 1;
    rep(n, N){
        rep(i, n + 1){
            rep(j, M + 1){
                // 3-1. 頂点 n + 1 を A に 追加.
                rep(k, i + 1){
                    dp[n + 1][i + 1][j + k] += dp[n][i][j] * C[i][k];
                    dp[n + 1][i + 1][j + k] %= MOD;
                }
                
                // 3-2. 頂点 n + 1 を B に 追加.
                rep(k, n - i + 1){
                    dp[n + 1][i][j + i + k] += dp[n][i][j] * C[n - i][k];
                    dp[n + 1][i][j + i + k] %= MOD;
                }
            }
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    repx(i, 1, N + 1){
        ans += dp[N][i][M];
        ans %= MOD;
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc163/editorial/6696

// 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 C[33][33], dp[33][33][33 * 33];

int main(){

// 1. 入力情報.

int N, M;

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

// 2. パスカルの三角形.

C[0][0] = 1;

repx(i, 1, 33){

rep(j, 33){

C[i][j] = (!j || j == i) ? 1LL : C[i - 1][j - 1] + C[i - 1][j];

C[i][j] %= MOD;

}

// 3. dp更新.

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

rep(n, N){

rep(i, n + 1){

rep(j, M + 1){

// 3-1. 頂点 n + 1 を A に追加.

rep(k, i + 1){

dp[n + 1][i + 1][j + k] += dp[n][i][j] * C[i][k];

dp[n + 1][i + 1][j + k] %= MOD;

}

// 3-2. 頂点 n + 1 を B に追加.

rep(k, n - i + 1){

dp[n + 1][i][j + i + k] += dp[n][i][j] * C[n - i][k];

dp[n + 1][i][j + i + k] %= MOD;

}

// 4. 集計.

LL ans = 0;

repx(i, 1, N + 1){

ans += dp[N][i][M];

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
3 1

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

[入力例]
6 2

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

[入力例]
25 156

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

[入力例]
1 0

[出力例]
1

[入力例]
2 1

[出力例]
2

[入力例]
5 1

[出力例]
34

[入力例]
7 5

[出力例]
33909

[入力例]
10 15

[出力例]
754406117

[入力例]
20 100

[出力例]
979610315

[入力例]
30 345

[出力例]
807062684

[入力例]

3 1

[出力例]

※AtCoderのテストケースより

[入力例]

6 2

[出力例]

300

※AtCoderのテストケースより

[入力例]

25 156

[出力例]

902739687

※AtCoderのテストケースより

[入力例]

1 0

[出力例]

[入力例]

2 1

[出力例]

[入力例]

5 1

[出力例]

[入力例]

7 5

[出力例]

33909

[入力例]

10 15

[出力例]

754406117

[入力例]

20 100

[出力例]

979610315

[入力例]

30 345

[出力例]

807062684

■参照サイト
AtCoder Regular Contest 163

2023年9月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題C (Harmonic Mean) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. N = k * (k - 1) のパターンは？
    set<int> st;
    repx(i, 1, 23) st.insert(i * (i + 1));
    
    // 3. 各テストケース.
    rep(i, T){
        // 3-1. テストケース入力情報.
        int N;
        scanf("%d", &N);
        
        // 3-2. N = 1.
        if(N == 1) puts("Yes\n1");
        
        // 3-3. N = 2.
        if(N == 2){
            puts("No");
        }
        
        // 3-4. N >= 3.
        if(N >= 3){
            // N = k * (k - 1) のパターン.
            vi ans;
            if(st.count(N)){
                ans.pb(2);
                repx(j, 1, N - 1) ans.pb(2 * j * (j + 1));
                ans.pb(2 * (N - 1));
            }
            
            // 上記以外.
            if(!st.count(N)){
                repx(j, 1, N) ans.pb(j * (j + 1));
                ans.pb(N);
            }
            
            // 出力.
            puts("Yes");
            rep(j, N) printf("%d%s", ans[j], (j < N - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc163/editorial/6695

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. N = k * (k - 1) のパターンは？

set<int> st;

repx(i, 1, 23) st.insert(i * (i + 1));

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

rep(i, T){

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

int N;

scanf("%d", &N);

// 3-2. N = 1.

if(N == 1) puts("Yes\n1");

// 3-3. N = 2.

if(N == 2){

puts("No");

}

// 3-4. N >= 3.

if(N >= 3){

// N = k * (k - 1) のパターン.

vi ans;

if(st.count(N)){

ans.pb(2);

repx(j, 1, N - 1) ans.pb(2 * j * (j + 1));

ans.pb(2 * (N - 1));

}

// 上記以外.

if(!st.count(N)){

repx(j, 1, N) ans.pb(j * (j + 1));

ans.pb(N);

}

// 出力.

puts("Yes");

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

}

return 0;

}

[入力例]
2
3
5

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
Yes
2 6 3
Yes
2 6 12 20 5

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

[出力例]
Yes
1
No
Yes
2 6 3
Yes
2 6 12 4
Yes
2 6 12 20 5
Yes
2 4 12 24 40 10
Yes
2 6 12 20 30 42 7
Yes
2 6 12 20 30 42 56 8
Yes
2 6 12 20 30 42 56 72 9
Yes
2 6 12 20 30 42 56 72 90 10

[入力例]
20
11
12
18
24
30
55
72
77
99
100
111
132
125
200
222
240
333
345
462
500

[出力例]
Yes
2 6 12 20 30 42 56 72 90 110 11
Yes
2 4 12 24 40 60 84 112 144 180 220 22
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 18
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 24
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 58
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 55
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 142
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 77
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 99
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 100
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 111
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 262
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 125
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 200
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 222
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 34584 35112 35644 36180 36720 37264 37812 38364 38920 39480 40044 40612 41184 41760 42340 42924 43512 44104 44700 45300 45904 46512 47124 47740 48360 48984 49612 50244 50880 51520 52164 52812 53464 54120 54780 55444 56112 56784 57460 58140 58824 59512 60204 60900 61600 62304 63012 63724 64440 65160 65884 66612 67344 68080 68820 69564 70312 71064 71820 72580 73344 74112 74884 75660 76440 77224 78012 78804 79600 80400 81204 82012 82824 83640 84460 85284 86112 86944 87780 88620 89464 90312 91164 92020 92880 93744 94612 95484 96360 97240 98124 99012 99904 100800 101700 102604 103512 104424 105340 106260 107184 108112 109044 109980 110920 111864 112812 113764 478
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 333
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 111222 111890 112560 113232 113906 114582 115260 115940 116622 117306 117992 118680 345
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 34584 35112 35644 36180 36720 37264 37812 38364 38920 39480 40044 40612 41184 41760 42340 42924 43512 44104 44700 45300 45904 46512 47124 47740 48360 48984 49612 50244 50880 51520 52164 52812 53464 54120 54780 55444 56112 56784 57460 58140 58824 59512 60204 60900 61600 62304 63012 63724 64440 65160 65884 66612 67344 68080 68820 69564 70312 71064 71820 72580 73344 74112 74884 75660 76440 77224 78012 78804 79600 80400 81204 82012 82824 83640 84460 85284 86112 86944 87780 88620 89464 90312 91164 92020 92880 93744 94612 95484 96360 97240 98124 99012 99904 100800 101700 102604 103512 104424 105340 106260 107184 108112 109044 109980 110920 111864 112812 113764 114720 115680 116644 117612 118584 119560 120540 121524 122512 123504 124500 125500 126504 127512 128524 129540 130560 131584 132612 133644 134680 135720 136764 137812 138864 139920 140980 142044 143112 144184 145260 146340 147424 148512 149604 150700 151800 152904 154012 155124 156240 157360 158484 159612 160744 161880 163020 164164 165312 166464 167620 168780 169944 171112 172284 173460 174640 175824 177012 178204 179400 180600 181804 183012 184224 185440 186660 187884 189112 190344 191580 192820 194064 195312 196564 197820 199080 200344 201612 202884 204160 205440 206724 208012 209304 210600 211900 213204 214512 215824 217140 218460 219784 221112 222444 223780 225120 226464 227812 229164 230520 231880 233244 234612 235984 237360 238740 240124 241512 242904 244300 245700 247104 248512 249924 251340 252760 254184 255612 257044 258480 259920 261364 262812 264264 265720 267180 268644 270112 271584 273060 274540 276024 277512 279004 280500 282000 283504 285012 286524 288040 289560 291084 292612 294144 295680 297220 298764 300312 301864 303420 304980 306544 308112 309684 311260 312840 314424 316012 317604 319200 320800 322404 324012 325624 327240 328860 330484 332112 333744 335380 337020 338664 340312 341964 343620 345280 346944 348612 350284 351960 353640 355324 357012 358704 360400 362100 363804 365512 367224 368940 370660 372384 374112 375844 377580 379320 381064 382812 384564 386320 388080 389844 391612 393384 395160 396940 398724 400512 402304 404100 405900 407704 409512 411324 413140 414960 416784 418612 420444 422280 424120 922
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 111222 111890 112560 113232 113906 114582 115260 115940 116622 117306 117992 118680 119370 120062 120756 121452 122150 122850 123552 124256 124962 125670 126380 127092 127806 128522 129240 129960 130682 131406 132132 132860 133590 134322 135056 135792 136530 137270 138012 138756 139502 140250 141000 141752 142506 143262 144020 144780 145542 146306 147072 147840 148610 149382 150156 150932 151710 152490 153272 154056 154842 155630 156420 157212 158006 158802 159600 160400 161202 162006 162812 163620 164430 165242 166056 166872 167690 168510 169332 170156 170982 171810 172640 173472 174306 175142 175980 176820 177662 178506 179352 180200 181050 181902 182756 183612 184470 185330 186192 187056 187922 188790 189660 190532 191406 192282 193160 194040 194922 195806 196692 197580 198470 199362 200256 201152 202050 202950 203852 204756 205662 206570 207480 208392 209306 210222 211140 212060 212982 213906 214832 215760 216690 217622 218556 219492 220430 221370 222312 223256 224202 225150 226100 227052 228006 228962 229920 230880 231842 232806 233772 234740 235710 236682 237656 238632 239610 240590 241572 242556 243542 244530 245520 246512 247506 248502 249500 500

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

[出力例]

Yes

2 3 6

Yes

3 4 5 6 20

※AtCoderのテストケースより

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

Yes

2 6 3

Yes

2 6 12 20 5

[入力例]

[出力例]

Yes

2 6 3

Yes

2 6 12 4

Yes

2 6 12 20 5

Yes

2 4 12 24 40 10

Yes

2 6 12 20 30 42 7

Yes

2 6 12 20 30 42 56 8

Yes

2 6 12 20 30 42 56 72 9

Yes

2 6 12 20 30 42 56 72 90 10

[入力例]

100

111

132

125

200

222

240

333

345

462

500

[出力例]

Yes

2 6 12 20 30 42 56 72 90 110 11

Yes

2 4 12 24 40 60 84 112 144 180 220 22

Yes

2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 18

Yes

2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 24

Yes

2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 58

Yes

2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 34584 35112 35644 36180 36720 37264 37812 38364 38920 39480 40044 40612 41184 41760 42340 42924 43512 44104 44700 45300 45904 46512 47124 47740 48360 48984 49612 50244 50880 51520 52164 52812 53464 54120 54780 55444 56112 56784 57460 58140 58824 59512 60204 60900 61600 62304 63012 63724 64440 65160 65884 66612 67344 68080 68820 69564 70312 71064 71820 72580 73344 74112 74884 75660 76440 77224 78012 78804 79600 80400 81204 82012 82824 83640 84460 85284 86112 86944 87780 88620 89464 90312 91164 92020 92880 93744 94612 95484 96360 97240 98124 99012 99904 100800 101700 102604 103512 104424 105340 106260 107184 108112 109044 109980 110920 111864 112812 113764 114720 115680 116644 117612 118584 119560 120540 121524 122512 123504 124500 125500 126504 127512 128524 129540 130560 131584 132612 133644 134680 135720 136764 137812 138864 139920 140980 142044 143112 144184 145260 146340 147424 148512 149604 150700 151800 152904 154012 155124 156240 157360 158484 159612 160744 161880 163020 164164 165312 166464 167620 168780 169944 171112 172284 173460 174640 175824 177012 178204 179400 180600 181804 183012 184224 185440 186660 187884 189112 190344 191580 192820 194064 195312 196564 197820 199080 200344 201612 202884 204160 205440 206724 208012 209304 210600 211900 213204 214512 215824 217140 218460 219784 221112 222444 223780 225120 226464 227812 229164 230520 231880 233244 234612 235984 237360 238740 240124 241512 242904 244300 245700 247104 248512 249924 251340 252760 254184 255612 257044 258480 259920 261364 262812 264264 265720 267180 268644 270112 271584 273060 274540 276024 277512 279004 280500 282000 283504 285012 286524 288040 289560 291084 292612 294144 295680 297220 298764 300312 301864 303420 304980 306544 308112 309684 311260 312840 314424 316012 317604 319200 320800 322404 324012 325624 327240 328860 330484 332112 333744 335380 337020 338664 340312 341964 343620 345280 346944 348612 350284 351960 353640 355324 357012 358704 360400 362100 363804 365512 367224 368940 370660 372384 374112 375844 377580 379320 381064 382812 384564 386320 388080 389844 391612 393384 395160 396940 398724 400512 402304 404100 405900 407704 409512 411324 413140 414960 416784 418612 420444 422280 424120 922

Yes

2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 111222 111890 112560 113232 113906 114582 115260 115940 116622 117306 117992 118680 119370 120062 120756 121452 122150 122850 123552 124256 124962 125670 126380 127092 127806 128522 129240 129960 130682 131406 132132 132860 133590 134322 135056 135792 136530 137270 138012 138756 139502 140250 141000 141752 142506 143262 144020 144780 145542 146306 147072 147840 148610 149382 150156 150932 151710 152490 153272 154056 154842 155630 156420 157212 158006 158802 159600 160400 161202 162006 162812 163620 164430 165242 166056 166872 167690 168510 169332 170156 170982 171810 172640 173472 174306 175142 175980 176820 177662 178506 179352 180200 181050 181902 182756 183612 184470 185330 186192 187056 187922 188790 189660 190532 191406 192282 193160 194040 194922 195806 196692 197580 198470 199362 200256 201152 202050 202950 203852 204756 205662 206570 207480 208392 209306 210222 211140 212060 212982 213906 214832 215760 216690 217622 218556 219492 220430 221370 222312 223256 224202 225150 226100 227052 228006 228962 229920 230880 231842 232806 233772 234740 235710 236682 237656 238632 239610 240590 241572 242556 243542 244530 245520 246512 247506 248502 249500 500

■参照サイト
AtCoder Regular Contest 163

2023年9月18日

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

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題A (Divide String) ～問題B (Favorite Game) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        int N;
        char c[2020];
        scanf("%d %s", &N, c);
        string s(c);
        
        // 2-2. 長さ 2 の分割方法が存在するか？
        bool ok = false;
        rep(i, N - 1){
            string l = s.substr(0, i + 1);
            string r = s.substr(i + 1, N - i - 1);
            // printf("l=%s r=%s\n", l.c_str(), r.c_str());
            // 狭義単調増加に注意(等号は含めない).
            if(l < r){
                ok = true;
                break;
            }
        }
        
        // 2-3. 出力.
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc163/editorial/6693

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

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

int N;

char c[2020];

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

string s(c);

// 2-2. 長さ 2 の分割方法が存在するか？

bool ok = false;

rep(i, N - 1){

string l = s.substr(0, i + 1);

string r = s.substr(i + 1, N - i - 1);

// printf("l=%s r=%s\n", l.c_str(), r.c_str());

// 狭義単調増加に注意(等号は含めない).

if(l < r){

ok = true;

break;

}

// 2-3. 出力.

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

}

return 0;

}

[入力例]
5
4
abac
3
cac
2
ab
12
abababababab
5
edcba

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

[入力例]
9
2
aa
3
aba
4
zyyx
5
qqqqp
6
zyxwvx
7
pqrsqrp
8
zyxzxyzy
9
pqrpqrpqr
10
srqposrqpo

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

[入力例]

abac

cac

abababababab

edcba

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

aba

zyyx

qqqqp

zyxwvx

pqrsqrp

zyxzxyzy

pqrpqrpqr

srqposrqpo

[出力例]

Yes

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 数列 B.
    sort(a + 2, a + N);
    
    // 3. 全探索.
    LL ans = 202020202020202020;
    repx(i, 2, N - M + 1){
        // 左端, 右端.
        LL l = a[i];
        LL r = a[i + M - 1];
        
        // 操作回数.
        LL op = 0;
        op += max(0LL, a[0] - l);
        op += max(0LL, r - a[1]);
        
        // 最小値更新.
        ans = min(ans, op);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc163/editorial/6699

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[202020];

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. 数列 B.

sort(a + 2, a + N);

// 3. 全探索.

LL ans = 202020202020202020;

repx(i, 2, N - M + 1){

// 左端, 右端.

LL l = a[i];

LL r = a[i + M - 1];

// 操作回数.

LL op = 0;

op += max(0LL, a[0] - l);

op += max(0LL, r - a[1]);

// 最小値更新.

ans = min(ans, op);

}

// 4. 出力.

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

return 0;

}

[入力例]
3 1
2 3 5

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

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

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

[入力例]
8 5
15 59 64 96 31 17 88 9

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

[入力例]
7 5
31 14 91 40 16 56 99

[出力例]
100

[入力例]
20 12
81 43 53 37 98 14 38 92 84 31 8 17 77 72 123 83 6 57 117 51

[出力例]
105

[入力例]
30 15
830 698 320 654 1055 357 16 713 244 523 463 1020 912 514 298 528 549 801 424 490 323 246 1163 301 392 290 645 458 1099 776

[出力例]
525

[入力例]

3 1

2 3 5

[出力例]

※AtCoderのテストケースより

[入力例]

5 2

1 4 2 3 5

[出力例]

※AtCoderのテストケースより

[入力例]

8 5

15 59 64 96 31 17 88 9

[出力例]

※AtCoderのテストケースより

[入力例]

7 5

31 14 91 40 16 56 99

[出力例]

100

[入力例]

20 12

81 43 53 37 98 14 38 92 84 31 8 17 77 72 123 83 6 57 117 51

[出力例]

105

[入力例]

30 15

830 698 320 654 1055 357 16 713 244 523 463 1020 912 514 298 528 549 801 424 490 323 246 1163 301 392 290 645 458 1099 776

[出力例]

525

■参照サイト
AtCoder Regular Contest 163

2023年9月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 284 の問題E (Count Simple Paths) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 訪問済みフラグ(往路, 復路)を活用して, 数え上げできるロジックが, 興味深く思った.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    int ans = 0;
    auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m) -> void {
        // 終了条件.
        if(m[cur]) return;
        
        // 終了条件(TLE回避のため, ロジック追加).
        // -> 対象のテストケースは, 02_random_00.txt ～ 02_random_03.txt.
        if(ans == 1000000) return;
        
        // 訪問済みフラグ(往路).
        ++m[cur];
        ans = min(++ans, 1000000);
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            if(nex == bef) continue;
            self(self, G, nex, cur, m);
        }
        
        // 訪問済みフラグ(復路).
        --m[cur];
    };
    int memo[N];
    rep(i, N) memo[i] = 0;
    dfs(dfs, G, 0, -1, memo);
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc284/editorial/5494

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

rep(i, M){

int u, v;

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

--u, --v;

G[u].pb(v);

G[v].pb(u);

}

// 2. dfs.

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

int ans = 0;

auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m) -> void {

// 終了条件.

if(m[cur]) return;

// 終了条件(TLE回避のため, ロジック追加).

// -> 対象のテストケースは, 02_random_00.txt ～ 02_random_03.txt.

if(ans == 1000000) return;

// 訪問済みフラグ(往路).

++m[cur];

ans = min(++ans, 1000000);

// 隣接頂点.

for(auto &nex : G[cur]){

if(nex == bef) continue;

self(self, G, nex, cur, m);

}

// 訪問済みフラグ(復路).

--m[cur];

};

int memo[N];

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

dfs(dfs, G, 0, -1, memo);

// 3. 出力.

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

return 0;

}

[入力例]
4 2
1 2
2 3

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

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

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

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

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

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

[出力例]
3

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

[出力例]
10

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

[出力例]
26

[入力例]

4 2

1 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

4 6

1 2

1 3

1 4

2 3

2 4

3 4

[出力例]

※AtCoderテストケースより

[入力例]

8 21

2 6

1 3

5 6

3 8

3 6

4 7

4 6

3 4

1 5

2 4

1 2

2 7

1 4

3 5

2 5

2 3

4 5

3 7

6 7

5 7

2 8

[出力例]

2023

※AtCoderテストケースより

[入力例]

5 3

1 2

2 3

4 5

[出力例]

[入力例]

10 9

1 2

2 3

2 4

1 5

5 6

5 7

7 8

7 9

7 10

[出力例]

[入力例]

18 20

1 2

2 3

3 4

4 5

5 3

1 6

6 8

6 9

9 8

9 10

11 9

7 1

7 12

18 7

12 13

12 14

12 15

13 16

16 17

17 13

[出力例]

■参照サイト
AtCoder Beginner Contest 284

2023年8月27日

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

C++の練習を兼ねて, AtCoder Grand Contest 049 の問題A (Erasing Vertices) ～問題B (Flip Digits) を解いてみた.

■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 問題A で, 幅優先探索の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 問題A, B のいずれも, 解説のロジックが, 非常に不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/agc049/editorial/281
// 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;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N){
        char c[101];
        scanf("%s", c);
        rep(j, N) if(c[j] == '1') G[i].pb(j); // 有向辺.
    }
    
    // 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 &v : G[u]) if(d[v] == -1 && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    
    // 3. S[v] の 計算(解説通り).
    vvi S(N);
    rep(i, N){
        // 頂点 i から, 到達可能な頂点は？
        int d[N];
        rep(j, N) d[j] = -1;
        bfs(G, i, d);
        
        // S[v] に 保存.
        rep(v, N) if(d[v] != -1) S[v].pb(i);
    }
    
    // 4. 集計.
    double ans = 0.0;
    rep(v, N) ans += 1.0 / (double)S[v].size();
    
    // 5. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/agc049/editorial/281

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

scanf("%d", &N);

vvi G(N);

rep(i, N){

char c[101];

scanf("%s", c);

rep(j, N) if(c[j] == '1') G[i].pb(j); // 有向辺.

}

// 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 &v : G[u]) if(d[v] == -1 && v != s) d[v] = d[u] + 1, q.push(v);

}

};

// 3. S[v] の計算(解説通り).

vvi S(N);

rep(i, N){

// 頂点 i から, 到達可能な頂点は？

int d[N];

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

bfs(G, i, d);

// S[v] に保存.

rep(v, N) if(d[v] != -1) S[v].pb(i);

}

// 4. 集計.

double ans = 0.0;

rep(v, N) ans += 1.0 / (double)S[v].size();

// 5. 出力.

printf("%.12lf\n", ans);

return 0;

}

[入力例]
3
010
001
010

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

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

[入力例]
3
000
000
000

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

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

[入力例]
3
011
101
110

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

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

[入力例]
4
0100
0010
0001
0100

[出力例]
1.750000000000

[入力例]
5
01001
00100
00010
01000
00000

[出力例]
2.250000000000

[入力例]
10
0100000100
0010010000
0001000001
0000100000
0000000000
0000001000
0000000000
0000000010
0000000000
0000000000

[出力例]
3.950000000000

[入力例]
15
010000000010000
000000000000000
000100000000100
000010000000010
000000000100001
000000000000100
000000000010001
000000000000000
000000010000000
000001000000000
000010000000000
000100000000000
000000000000010
010000000000000
110000000000000

[出力例]
5.795609945610

[入力例]

010

001

010

[出力例]

1.66666666666666666667

※AtCoderのテストケースより

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

1.666666666667

[入力例]

000

[出力例]

3.00000000000000000000

※AtCoderのテストケースより

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

3.000000000000

[入力例]

011

101

110

[出力例]

1.00000000000000000000

※AtCoderのテストケースより

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

1.000000000000

[入力例]

0100

0010

0001

0100

[出力例]

1.750000000000

[入力例]

01001

00100

00010

01000

00000

[出力例]

2.250000000000

[入力例]

0100000100

0010010000

0001000001

0000100000

0000000000

0000001000

0000000000

0000000010

0000000000

[出力例]

3.950000000000

[入力例]

010000000010000

000000000000000

000100000000100

000010000000010

000000000100001

000000000000100

000000000010001

000000000000000

000000010000000

000001000000000

000010000000000

000100000000000

000000000000010

010000000000000

110000000000000

[出力例]

5.795609945610

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

// 解き直し.
// https://atcoder.jp/contests/agc049/editorial/330
// 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 sXorCum[505050], tXorCum[505050], cur[2];

int main(){
    
    // 1. 入力情報.
    int N;
    char s[505050], t[505050];
    scanf("%d %s %s", &N, s, t);
    
    // 2. 累積XOR.
    rep(i, N){
        sXorCum[i + 1] = sXorCum[i] ^ (s[i] == '1');
        tXorCum[i + 1] = tXorCum[i] ^ (t[i] == '1');
    }
    
    // 3. 操作(解説通り).
    int k = -1, jMax = -1;
    LL ans = 0;
    bool ok = true;
    repx(i, 1, N + 1){
        // すでに, tXorCum と sXorCum が 一致しているときは, Skip.
        if(cur[tXorCum[i]] >= i) continue;
        
        // 探索開始位置(今回分).
        k = max(jMax, i);
        
        // 探索済みにも関わらず, tXorCum と sXorCum が 一致しない場合は, NG.
        if(k == N + 1) ok = false;
        
        // tXorCum の i番目 と sXorCum の j番目 が 等しくなるものは？
        repx(j, k, N + 1){
            // 探索開始位置(次回分).
            jMax = max(jMax, j + 1);
            
            // 見つかった.
            if(tXorCum[i] == sXorCum[j]){
                // 集計.
                ans += (j - i);
                
                // 操作履歴保存.
                cur[tXorCum[i]] = j;
                cur[!tXorCum[i]] = -1;
                
                // 次へ.
                break;
            }
            
            // 見つからなかった.
            if(jMax == N + 1) ok = false;
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ok ? ans : -1);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/agc049/editorial/330

// 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 sXorCum[505050], tXorCum[505050], cur[2];

int main(){

// 1. 入力情報.

int N;

char s[505050], t[505050];

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

// 2. 累積XOR.

rep(i, N){

sXorCum[i + 1] = sXorCum[i] ^ (s[i] == '1');

tXorCum[i + 1] = tXorCum[i] ^ (t[i] == '1');

}

// 3. 操作(解説通り).

int k = -1, jMax = -1;

LL ans = 0;

bool ok = true;

repx(i, 1, N + 1){

// すでに, tXorCum と sXorCum が一致しているときは, Skip.

if(cur[tXorCum[i]] >= i) continue;

// 探索開始位置(今回分).

k = max(jMax, i);

// 探索済みにも関わらず, tXorCum と sXorCum が一致しない場合は, NG.

if(k == N + 1) ok = false;

// tXorCum の i番目と sXorCum の j番目が等しくなるものは？

repx(j, k, N + 1){

// 探索開始位置(次回分).

jMax = max(jMax, j + 1);

// 見つかった.

if(tXorCum[i] == sXorCum[j]){

// 集計.

ans += (j - i);

// 操作履歴保存.

cur[tXorCum[i]] = j;

cur[!tXorCum[i]] = -1;

// 次へ.

break;

}

// 見つからなかった.

if(jMax == N + 1) ok = false;

}

// 4. 出力.

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

return 0;

}

[入力例]
3
001
100

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

[入力例]
3
001
110

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

[入力例]
5
10111
01010

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

[入力例]
7
0101101
1001100

[出力例]
-1

[入力例]
7
0111101
1001100

[出力例]
5

[入力例]
10
1010111101
1000101100

[出力例]
-1

[入力例]
10
1010111101
1100101100

[出力例]
5

[入力例]
30
001010001110011100110110111101
110001010100011100100110011000

[出力例]
18

[入力例]

001

100

[出力例]

※AtCoderのテストケースより

[入力例]

001

110

[出力例]

-1

※AtCoderのテストケースより

[入力例]

10111

01010

[出力例]

※AtCoderのテストケースより

[入力例]

0101101

1001100

[出力例]

-1

[入力例]

0111101

1001100

[出力例]

[入力例]

1010111101

1000101100

[出力例]

-1

[入力例]

1010111101

1100101100

[出力例]

[入力例]

001010001110011100110110111101

110001010100011100100110011000

[出力例]

■参照サイト
AtCoder Grand Contest 049

2023年8月20日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc189/editorial/541
// 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 a[202020];
double dp[202020], dpCum[202020], pd[202020], pdCum[202020];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vi v;
    rep(i, K){
        int idx;
        scanf("%d", &idx);
        ++a[idx];
        v.pb(idx);
    }
    
    // 2. マス N に, 到達不可能.
    if(K >= M){
        rep(i, K - M + 1){
            if(v[i + M - 1] - v[i] == M - 1){
                puts("-1");
                return 0;
            }
        }
    }
    
    // 3. dp更新.
    repr(i, N - 1, 0){
        // 振り出しに戻るマス.
        if(a[i]){
            // g[i].
            dp[i] = 0.0;
            dpCum[i] = dp[i] + dpCum[i + 1];
            
            // x の 係数.
            pd[i] = 1.0;
            pdCum[i] = pd[i] + pdCum[i + 1];
            
            // 次へ.
            continue;
        }
        
        // それ以外.
        // g[i].
        dp[i] = 1.0 / M * (dpCum[i + 1] - dpCum[i + M + 1]) + 1.0;
        dpCum[i] = dp[i] + dpCum[i + 1];
        
        // x の 係数.
        pd[i] = 1.0 / M * (pdCum[i + 1] - pdCum[i + M + 1]);
        pdCum[i] = pd[i] + pdCum[i + 1];
    }
    
    // 4. 出力.
    printf("%.6lf\n", dp[0] / (1.0 - pd[0]));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc189/editorial/541

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

double dp[202020], dpCum[202020], pd[202020], pdCum[202020];

int main(){

// 1. 入力情報.

int N, M, K;

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

vi v;

rep(i, K){

int idx;

scanf("%d", &idx);

++a[idx];

v.pb(idx);

}

// 2. マス N に, 到達不可能.

if(K >= M){

rep(i, K - M + 1){

if(v[i + M - 1] - v[i] == M - 1){

puts("-1");

return 0;

}

// 3. dp更新.

repr(i, N - 1, 0){

// 振り出しに戻るマス.

if(a[i]){

// g[i].

dp[i] = 0.0;

dpCum[i] = dp[i] + dpCum[i + 1];

// x の係数.

pd[i] = 1.0;

pdCum[i] = pd[i] + pdCum[i + 1];

// 次へ.

continue;

}

// それ以外.

// g[i].

dp[i] = 1.0 / M * (dpCum[i + 1] - dpCum[i + M + 1]) + 1.0;

dpCum[i] = dp[i] + dpCum[i + 1];

// x の係数.

pd[i] = 1.0 / M * (pdCum[i + 1] - pdCum[i + M + 1]);

pdCum[i] = pd[i] + pdCum[i + 1];

}

// 4. 出力.

printf("%.6lf\n", dp[0] / (1.0 - pd[0]));

return 0;

}

[入力例]
2 2 0

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

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

[入力例]
2 2 1
1

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

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

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

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

[入力例]
100000 2 2
2997 92458

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

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

[入力例]
5 4 2
2 3

[出力例]
4.166667

[入力例]
5 3 3
2 4 5

[出力例]
6.000000

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

[出力例]
-1

[入力例]
7 5 3
1 4 5

[出力例]
6.821429

[入力例]
2023 3 8
123 234 345 456 567 678 789 890 

[出力例]
30397.833333

[入力例]
12345 3 5
1234 2345 3456 4567 5678

[出力例]
39742.833332

[入力例]

2 2 0

[出力例]

1.5000

※AtCoderテストケースより

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

1.500000

[入力例]

2 2 1

[出力例]

2.0000

※AtCoderテストケースより

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

2.000000

[入力例]

100 6 10

11 12 13 14 15 16 17 18 19 20

[出力例]

-1

※AtCoderテストケースより

[入力例]

100000 2 2

2997 92458

[出力例]

201932.2222

※AtCoderテストケースより

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

201932.225051

[入力例]

5 4 2

2 3

[出力例]

4.166667

[入力例]

5 3 3

2 4 5

[出力例]

6.000000

[入力例]

6 3 4

1 3 4 5

[出力例]

-1

[入力例]

7 5 3

1 4 5

[出力例]

6.821429

[入力例]

2023 3 8

123 234 345 456 567 678 789 890

[出力例]

30397.833333

[入力例]

12345 3 5

1234 2345 3456 4567 5678

[出力例]

39742.833332

■参照サイト
AtCoder Beginner Contest 189

2023年8月18日2023年8月18日

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

C++の練習を兼ねて, AtCoder Beginner Contest 205 の問題F (Grid and Tokens) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. Dinic法に触れることが出来たので, 非常に良かったと思う.
※ 競プロ典型 90 問のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc205/editorial/2057
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
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 pb push_back
const int MAX = 2020;
int PA[101], PB[101], PC[101], PD[101];

struct Edge{
    int to, cap, rev;
};

// Dinic
// https://github.com/E869120/kyopro_educational_90/blob/main/sol/077-04a.cpp
// -> 一部改変(2022/04/23).
struct Dinic{
    int size_;
    vi level, iter;
    vector<Edge> G[MAX];
    
    Dinic(int n = 0) : size_(n), level(n + 1), iter(n + 1) {}
    void edge(int u, int v, int c){
        G[u].pb(Edge{v, c, (int)G[v].size()});
        G[v].pb(Edge{u, 0, (int)G[u].size() - 1});
    }
    void bfs(int s){
        rep(i, size_ + 1) level[i] = -1;
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while(!q.empty()){
            int pos = q.front();
            q.pop();
            rep(i, G[pos].size()){
                if(G[pos][i].cap == 0 || level[G[pos][i].to] != -1) continue;
                q.push(G[pos][i].to);
                level[G[pos][i].to] = level[pos] + 1;
            }
        }
    }
    int dfs(int pos, int to, int f){
        if(pos == to) return f;
        for(int& i = iter[pos]; i < G[pos].size(); i++){
            if(G[pos][i].cap > 0 && level[pos] < level[G[pos][i].to]){
                int z = dfs(G[pos][i].to, to, min(f, G[pos][i].cap));
                if(z > 0){
                    G[pos][i].cap -= z;
                    G[G[pos][i].to][G[pos][i].rev].cap += z;
                    return z;
                }
            }
        }
        return 0;
    }
    int maxFlow(int s, int t){
        int ret = 0;
        while(1){
            bfs(s);
            if(level[t] == -1) break;
            rep(i, size_ + 1) iter[i] = 0;
            while(1){
                int f = dfs(s, t, 1000000007);
                if(f == 0) break;
                ret += f;
            }
        }
        return ret;
    }
};

int main(){
    
    // 1. 入力情報.
    int H, W, N;
    scanf("%d %d %d", &H, &W, &N);
    rep(i, N) scanf("%d %d %d %d", &PA[i], &PB[i], &PC[i], &PD[i]);
    rep(i, N){
        PB[i] += H;
        PD[i] += H;
    }
    
    // 2. グラフ構築(解説通り).
    // -> 頂点番号は, 以下のように設定.
    // src = 0
    // R = 1 ～ H
    // C = H + 1 ～ H + W
    // U = H + W + 1 ～ H + W + N
    // V = H + W + N + 1 ～ H + W + N + N
    // dst = H + W + N + N + 1
    // 
    int src = 0, dst = H + W + N + N + 1;
    Dinic D(H + W + N + N + 5);
    repx(r, 1, H + 1) D.edge(src, r, 1);
    rep(i, N){
        int u = H + W + i + 1;
        repx(r, PA[i], PC[i] + 1) D.edge(r, u, 1);
    }
    rep(i, N){
        int u = H + W + i + 1;
        int v = H + W + N + i + 1;
        D.edge(u, v, 1);
    }
    rep(i, N){
        int v = H + W + N + i + 1;
        repx(c, PB[i], PD[i] + 1) D.edge(v, c, 1);
    }
    repx(c, H + 1, H + W + 1) D.edge(c, dst, 1);
    
    // 3. 出力.
    printf("%d\n", D.maxFlow(src, dst));
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

// 解き直し.

// https://atcoder.jp/contests/abc205/editorial/2057

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

const int MAX = 2020;

int PA[101], PB[101], PC[101], PD[101];

struct Edge{

int to, cap, rev;

};

// Dinic

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/077-04a.cpp

// -> 一部改変(2022/04/23).

struct Dinic{

int size_;

vi level, iter;

vector<Edge> G[MAX];

Dinic(int n = 0) : size_(n), level(n + 1), iter(n + 1) {}

void edge(int u, int v, int c){

G[u].pb(Edge{v, c, (int)G[v].size()});

G[v].pb(Edge{u, 0, (int)G[u].size() - 1});

}

void bfs(int s){

rep(i, size_ + 1) level[i] = -1;

queue<int> q;

q.push(s);

level[s] = 0;

while(!q.empty()){

int pos = q.front();

q.pop();

rep(i, G[pos].size()){

if(G[pos][i].cap == 0 || level[G[pos][i].to] != -1) continue;

q.push(G[pos][i].to);

level[G[pos][i].to] = level[pos] + 1;

}

int dfs(int pos, int to, int f){

if(pos == to) return f;

for(int& i = iter[pos]; i < G[pos].size(); i++){

if(G[pos][i].cap > 0 && level[pos] < level[G[pos][i].to]){

int z = dfs(G[pos][i].to, to, min(f, G[pos][i].cap));

if(z > 0){

G[pos][i].cap -= z;

G[G[pos][i].to][G[pos][i].rev].cap += z;

return z;

}

return 0;

}

int maxFlow(int s, int t){

int ret = 0;

while(1){

bfs(s);

if(level[t] == -1) break;

rep(i, size_ + 1) iter[i] = 0;

while(1){

int f = dfs(s, t, 1000000007);

if(f == 0) break;

ret += f;

}

return ret;

}

};

int main(){

// 1. 入力情報.

int H, W, N;

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

rep(i, N) scanf("%d %d %d %d", &PA[i], &PB[i], &PC[i], &PD[i]);

rep(i, N){

PB[i] += H;

PD[i] += H;

}

// 2. グラフ構築(解説通り).

// -> 頂点番号は, 以下のように設定.

// src = 0

// R = 1 ～ H

// C = H + 1 ～ H + W

// U = H + W + 1 ～ H + W + N

// V = H + W + N + 1 ～ H + W + N + N

// dst = H + W + N + N + 1

int src = 0, dst = H + W + N + N + 1;

Dinic D(H + W + N + N + 5);

repx(r, 1, H + 1) D.edge(src, r, 1);

rep(i, N){

int u = H + W + i + 1;

repx(r, PA[i], PC[i] + 1) D.edge(r, u, 1);

}

rep(i, N){

int u = H + W + i + 1;

int v = H + W + N + i + 1;

D.edge(u, v, 1);

}

rep(i, N){

int v = H + W + N + i + 1;

repx(c, PB[i], PD[i] + 1) D.edge(v, c, 1);

}

repx(c, H + 1, H + W + 1) D.edge(c, dst, 1);

// 3. 出力.

printf("%d\n", D.maxFlow(src, dst));

return 0;

}

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

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

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

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

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

[出力例]
2

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

[出力例]
6

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

[出力例]
10

[入力例]

2 3 3

1 1 2 2

1 2 2 3

1 1 1 3

[出力例]

※AtCoderテストケースより

[入力例]

5 5 3

1 1 5 5

1 1 4 4

2 2 3 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2 2

1 1 1 1

1 1 2 2

[出力例]

[入力例]

7 10 12

3 3 6 4

3 3 5 5

3 8 4 10

2 9 5 10

3 3 5 5

2 7 3 8

3 8 3 10

2 9 7 10

3 4 5 5

3 5 5 5

2 3 3 6

2 9 6 10

[出力例]

[入力例]

12 15 18

5 4 7 7

5 5 6 6

5 4 7 8

4 5 5 7

3 5 9 6

3 6 10 6

3 5 9 7

2 6 8 7

2 7 7 8

2 8 7 9

1 6 5 7

1 5 6 7

1 6 7 9

1 3 3 4

1 5 2 6

10 12 12 12

10 12 11 13

10 11 11 13

[出力例]

■参照サイト
AtCoder Beginner Contest 205
競プロ典型 90 問の問題077

2023年8月16日

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

C++の練習を兼ねて, AtCoder Beginner Contest 182 の問題F (Valid payments) を解いてみた.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d %lld", &N, &X);
    rep(i, N) scanf("%lld", &a[i]);
    rep(i, N - 1) b[i] = a[i + 1] / a[i];
    b[N - 1] = INF;
    
    // 2. dp更新.
    map<LL, LL> dp[N + 1];
    dp[N][-X] = 1;
    repr(i, N - 1, 0){
        for(auto &j : dp[i + 1]){
            // x の 出現チェック.
            set<LL> st;
            
            // x を -2 ～ 2 の差分に渡り, 余分に見る.
            for(auto &p : {-2, -1, 0, 1, 2}){
                // x, d の 計算.
                LL x = -j.a / a[i] + p;
                LL d = a[i] * x + j.a;
                
                // 条件を満たすか？
                if(!st.count(x) && abs(d) < a[i] && abs(x) < b[i]){
                    // dp更新.
                    dp[i][d] += dp[i + 1][j.a];
                    
                    // 出現済.
                    st.insert(x);
                }
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[0][0]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc182/editorial/293

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

const LL INF = 202020202020202020;

LL a[55], b[55];

int main(){

// 1. 入力情報.

int N;

LL X;

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

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

rep(i, N - 1) b[i] = a[i + 1] / a[i];

b[N - 1] = INF;

// 2. dp更新.

map<LL, LL> dp[N + 1];

dp[N][-X] = 1;

repr(i, N - 1, 0){

for(auto &j : dp[i + 1]){

// x の出現チェック.

set<LL> st;

// x を -2 ～ 2 の差分に渡り, 余分に見る.

for(auto &p : {-2, -1, 0, 1, 2}){

// x, d の計算.

LL x = -j.a / a[i] + p;

LL d = a[i] * x + j.a;

// 条件を満たすか？

if(!st.count(x) && abs(d) < a[i] && abs(x) < b[i]){

// dp更新.

dp[i][d] += dp[i + 1][j.a];

// 出現済.

st.insert(x);

}

// 3. 出力.

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

return 0;

}

[入力例]
3 9
1 5 10

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

[入力例]
5 198
1 5 10 50 100

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

[入力例]
4 44
1 4 20 100

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

[入力例]
9 11837029798
1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

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

[入力例]
15 304050607080
1 111 333 1665 11655 34965 244755 734265 2202795 11013975 33041925 99125775 198251550 396503100 1189509300

[出力例]
2160

[入力例]
23 20230816
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304

[出力例]
2675

[入力例]
25 202011082100
1 3 9 27 81 243 729 2187 6561 19683 59049 177147 531441 1594323 4782969 14348907 43046721 129140163 387420489 1162261467 3486784401 10460353203 31381059609 94143178827 282429536481

[出力例]
1075200

[入力例]

3 9

1 5 10

[出力例]

※AtCoderテストケースより

[入力例]

5 198

1 5 10 50 100

[出力例]

※AtCoderテストケースより

[入力例]

4 44

1 4 20 100

[出力例]

※AtCoderテストケースより

[入力例]

9 11837029798

1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

[出力例]

※AtCoderテストケースより

[入力例]

15 304050607080

1 111 333 1665 11655 34965 244755 734265 2202795 11013975 33041925 99125775 198251550 396503100 1189509300

[出力例]

2160

[入力例]

23 20230816

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304

[出力例]

2675

[入力例]

25 202011082100

1 3 9 27 81 243 729 2187 6561 19683 59049 177147 531441 1594323 4782969 14348907 43046721 129140163 387420489 1162261467 3486784401 10460353203 31381059609 94143178827 282429536481

[出力例]

1075200

■参照サイト
AtCoder Beginner Contest 182

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

C++の練習を兼ねて, AtCoder Beginner Contest 323 の 問題C (World Tour Finals) ～ 問題D (Merge Slimes) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の 問題D (Sum of SCC) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の 問題C (Harmonic Mean) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の 問題A (Divide String) ～ 問題B (Favorite Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 284 の 問題E (Count Simple Paths) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 049 の 問題A (Erasing Vertices) ～ 問題B (Flip Digits) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 205 の 問題F (Grid and Tokens) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 182 の 問題F (Valid payments) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 323 の問題C (World Tour Finals) ～問題D (Merge Slimes) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題D (Sum of SCC) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題C (Harmonic Mean) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題A (Divide String) ～問題B (Favorite Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 284 の問題E (Count Simple Paths) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 049 の問題A (Erasing Vertices) ～問題B (Flip Digits) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 205 の問題F (Grid and Tokens) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 182 の問題F (Valid payments) を解いてみた.