C++ | 個人用メモ帳

2021年9月15日

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

C++の練習を兼ねて, AtCoder Beginner Contest 210 の問題C (Colorful Candies) ～問題D (National Railway) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    map<int, int> m;
    int ans = 0;
    rep(i, N){
        scanf("%d", &c[i]);
        // K番目まで.
        if(i < K){
            m[c[i]]++;
            ans = m.size();
        }
        
        // (K + 1)番目以降.
        if(i >= K){
            // (i - K)番目を除外.
            m[c[i - K]]--;
            if(m[c[i - K]] == 0) m.erase(c[i - K]);
            
            // i番目を追加.
            m[c[i]]++;
            
            // 最大値更新.
            ans = max(ans, (int)m.size());
        }
    }
    
    // 2. 出力.
    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 c[303030];

int main(){

// 1. 入力情報.

int N, K;

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

map<int, int> m;

int ans = 0;

rep(i, N){

scanf("%d", &c[i]);

// K番目まで.

if(i < K){

m[c[i]]++;

ans = m.size();

}

// (K + 1)番目以降.

if(i >= K){

// (i - K)番目を除外.

m[c[i - K]]--;

if(m[c[i - K]] == 0) m.erase(c[i - K]);

// i番目を追加.

m[c[i]]++;

// 最大値更新.

ans = max(ans, (int)m.size());

}

// 2. 出力.

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

return 0;

}

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

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

[入力例]
5 5
4 4 4 4 4

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

[入力例]
10 6
304621362 506696497 304621362 506696497 834022578 304621362 414720753 304621362 304621362 414720753

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

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

[出力例]
3

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

[出力例]
6

[入力例]

7 3

1 2 1 2 3 3 1

[出力例]

※AtCoderテストケースより

[入力例]

5 5

4 4 4 4 4

[出力例]

※AtCoderテストケースより

[入力例]

10 6

304621362 506696497 304621362 506696497 834022578 304621362 414720753 304621362 304621362 414720753

[出力例]

※AtCoderテストケースより

[入力例]

30 7

2 1 5 1 2 1 2 2 2 1 1 3 1 1 1 4 3 3 4 1 1 3 3 3 1 1 5 3 5 1

[出力例]

[入力例]

100 11

1 2 1 2 2 2 1 3 2 1 2 1 1 1 2 2 3 3 3 4 4 4 1 1 4 1 3 2 4 2 4 4 1 3 3 2 2 1 2 1 1 1 1 3 2 3 3 2 1 2 3 1 3 2 1 1 3 1 1 3 2 5 3 2 4 4 6 4 1 1 6 5 1 4 1 2 6 5 5 5 6 2 1 4 6 6 2 5 3 3 2 3 3 3 1 4 3 2 3 4

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/abc210/editorial/2298
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#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 INF = 202020202020202020;

int main(){
    
    // 1. 入力情報.
    int H, W;
    LL C;
    scanf("%d %d %lld", &H, &W, &C);
    vvl o, r;
    rep(i, H){
        vl x;
        rep(j, W){
            LL a;
            scanf("%lld", &a);
            x.pb(a);
        }
        o.pb(x);
        
        // グリッド(左右反転版).
        reverse(all(x));
        r.pb(x);
    }
    
    // 2. 最小コスト計算.
    auto f = [&](vvl &a) -> LL{
        // 2-1. dp初期化.
        LL dp[H + 1][W + 1], pd[H + 1][W + 1];
        rep(i, H + 1){
            rep(j, W + 1){
                // 解説通り.
                dp[i][j] = 0;
                pd[i][j] = 0;
                if(i == 0 || j == 0) dp[i][j] = INF;
            }
        }
        
        // 2-2. dp更新.
        repx(i, 1, H + 1){
            repx(j, 1, W + 1){
                dp[i][j] = min({a[i - 1][j - 1], dp[i - 1][j] + C, dp[i][j - 1] + C});
            }
        }
        
        // 2-3. pd更新.
        repx(i, 1, H + 1){
            repx(j, 1, W + 1){
                pd[i][j] = min(dp[i - 1][j] + C + a[i - 1][j - 1], dp[i][j - 1] + C + a[i - 1][j - 1]);
            }
        }
        
        // 2-4. 最小コストは？
        LL ret = INF;
        repx(i, 1, H + 1) repx(j, 1, W + 1) ret = min(ret, pd[i][j]);
        
        // 2-5. 返却.
        return ret;
    };
    
    // 3. 出力.
    printf("%lld\n", min(f(o), f(r)));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc210/editorial/2298

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

#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 INF = 202020202020202020;

int main(){

// 1. 入力情報.

int H, W;

LL C;

scanf("%d %d %lld", &H, &W, &C);

vvl o, r;

rep(i, H){

vl x;

rep(j, W){

LL a;

scanf("%lld", &a);

x.pb(a);

}

o.pb(x);

// グリッド(左右反転版).

reverse(all(x));

r.pb(x);

}

// 2. 最小コスト計算.

auto f = [&](vvl &a) -> LL{

// 2-1. dp初期化.

LL dp[H + 1][W + 1], pd[H + 1][W + 1];

rep(i, H + 1){

rep(j, W + 1){

// 解説通り.

dp[i][j] = 0;

pd[i][j] = 0;

if(i == 0 || j == 0) dp[i][j] = INF;

}

// 2-2. dp更新.

repx(i, 1, H + 1){

repx(j, 1, W + 1){

dp[i][j] = min({a[i - 1][j - 1], dp[i - 1][j] + C, dp[i][j - 1] + C});

}

// 2-3. pd更新.

repx(i, 1, H + 1){

repx(j, 1, W + 1){

pd[i][j] = min(dp[i - 1][j] + C + a[i - 1][j - 1], dp[i][j - 1] + C + a[i - 1][j - 1]);

}

// 2-4. 最小コストは？

LL ret = INF;

repx(i, 1, H + 1) repx(j, 1, W + 1) ret = min(ret, pd[i][j]);

// 2-5. 返却.

return ret;

};

// 3. 出力.

printf("%lld\n", min(f(o), f(r)));

return 0;

}

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

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

[入力例]
3 3 1000000000
1000000 1000000 1
1000000 1000000 1000000
1 1000000 1000000

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

[入力例]
7 10 15
700 485 632 445 516 312 402 613 610 623
481 512 264 601 556 586 218 531 448 360
235 660 602 112 448 511 643 621 518 290
475 552 506 466 346 266 507 595 467 477
416 320 522 565 232 489 654 685 360 280
598 357 598 695 532 455 300 286 101 580
227 366 520 671 247 611 376 387 292 674

[出力例]
333

[入力例]
20 15 1111
69063 33529 70578 50473 33471 52692 59471 57207 41725 73815 75990 58995 39558 34738 49390
47707 78277 43559 38292 55222 31209 41636 54607 61137 68448 36770 59629 42720 78848 37025
31609 57109 52053 64466 34145 76388 54801 69362 53657 43378 78784 43989 58151 69935 75943
67146 71389 89098 48517 49145 40974 77705 48244 74143 45828 48442 41498 42878 78315 58550
72032 61268 54425 74660 35074 79791 34745 34377 57131 48088 33329 67736 53202 48549 67432
69402 54219 46534 34541 71061 63496 78626 69645 30327 35236 35039 56727 68706 76467 39552
42314 77814 38446 51468 66049 76406 68834 71865 63726 37778 60911 61255 53232 58945 62656
59630 41382 33943 72670 39640 77778 54823 62697 59889 67380 69919 55597 79104 53231 42149
66203 43153 64211 74574 60586 23900 53138 58149 72500 42190 40920 76979 67916 64220 78405
52320 59411 67566 76096 61546 65448 44318 33146 77883 65354 61381 66288 57002 62162 66443
57886 71760 33859 68348 76774 76808 74974 79765 55667 44448 58907 77074 50676 52163 51846
50856 55845 35800 70185 71215 73791 54767 77859 54498 74996 63781 73995 77765 45745 62157
75593 68722 31381 62576 71971 72569 62767 39665 48665 68091 53402 66721 53620 55335 56359
78114 49803 63406 41829 69565 73215 60739 69744 79310 61955 55631 68519 41628 70338 71592
53919 45273 47108 70105 79995 41198 65080 52365 39594 50123 63601 70300 52884 57012 67253
73311 53015 51435 77753 71262 57758 69687 68265 69790 50121 71519 59045 71228 68859 64313
79813 44042 59482 41806 67679 39375 51816 77314 78514 79956 51152 46028 53674 49413 71485
37928 73924 60817 41926 77080 44004 65161 54692 48732 59836 71124 45275 72694 12768 57388
47231 73723 54306 34425 77777 66795 61515 54203 69957 57813 49482 58912 62337 73125 54917
72717 32344 75565 33948 51856 64994 62686 76308 67035 41810 68473 45145 48847 74636 44683

[出力例]
55555

[入力例]

3 4 2

1 7 7 9

9 6 3 7

7 8 6 4

[出力例]

※AtCoderテストケースより

[入力例]

3 3 1000000000

1000000 1000000 1

1000000 1000000 1000000

1 1000000 1000000

[出力例]

1001000001

※AtCoderテストケースより

[入力例]

7 10 15

700 485 632 445 516 312 402 613 610 623

481 512 264 601 556 586 218 531 448 360

235 660 602 112 448 511 643 621 518 290

475 552 506 466 346 266 507 595 467 477

416 320 522 565 232 489 654 685 360 280

598 357 598 695 532 455 300 286 101 580

227 366 520 671 247 611 376 387 292 674

[出力例]

333

[入力例]

20 15 1111

69063 33529 70578 50473 33471 52692 59471 57207 41725 73815 75990 58995 39558 34738 49390

47707 78277 43559 38292 55222 31209 41636 54607 61137 68448 36770 59629 42720 78848 37025

31609 57109 52053 64466 34145 76388 54801 69362 53657 43378 78784 43989 58151 69935 75943

67146 71389 89098 48517 49145 40974 77705 48244 74143 45828 48442 41498 42878 78315 58550

72032 61268 54425 74660 35074 79791 34745 34377 57131 48088 33329 67736 53202 48549 67432

69402 54219 46534 34541 71061 63496 78626 69645 30327 35236 35039 56727 68706 76467 39552

42314 77814 38446 51468 66049 76406 68834 71865 63726 37778 60911 61255 53232 58945 62656

59630 41382 33943 72670 39640 77778 54823 62697 59889 67380 69919 55597 79104 53231 42149

66203 43153 64211 74574 60586 23900 53138 58149 72500 42190 40920 76979 67916 64220 78405

52320 59411 67566 76096 61546 65448 44318 33146 77883 65354 61381 66288 57002 62162 66443

57886 71760 33859 68348 76774 76808 74974 79765 55667 44448 58907 77074 50676 52163 51846

50856 55845 35800 70185 71215 73791 54767 77859 54498 74996 63781 73995 77765 45745 62157

75593 68722 31381 62576 71971 72569 62767 39665 48665 68091 53402 66721 53620 55335 56359

78114 49803 63406 41829 69565 73215 60739 69744 79310 61955 55631 68519 41628 70338 71592

53919 45273 47108 70105 79995 41198 65080 52365 39594 50123 63601 70300 52884 57012 67253

73311 53015 51435 77753 71262 57758 69687 68265 69790 50121 71519 59045 71228 68859 64313

79813 44042 59482 41806 67679 39375 51816 77314 78514 79956 51152 46028 53674 49413 71485

37928 73924 60817 41926 77080 44004 65161 54692 48732 59836 71124 45275 72694 12768 57388

47231 73723 54306 34425 77777 66795 61515 54203 69957 57813 49482 58912 62337 73125 54917

72717 32344 75565 33948 51856 64994 62686 76308 67035 41810 68473 45145 48847 74636 44683

[出力例]

55555

■参照サイト
AtCoder Beginner Contest 210

2021年9月14日

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

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

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. Union-Find木, 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc218/editorial/2580
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vl = vector<LL>;
using T3 = tuple<LL, int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
LL c[202020];
int a[202020], b[202020];

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    LL cTotal = 0;
    rep(i, M){
        scanf("%d %d %lld", &a[i], &b[i], &c[i]);
        a[i]--;
        b[i]--;
        cTotal += c[i]; // コスト合計.
    }
    
    // 2. sort.
    vector<T3> t;
    rep(i, M) t.emplace_back(c[i], a[i], b[i]);
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm)を計算.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    LL cSum = 0;
    UnionFind uf(N + 2);
    rep(i, t.size()){
        // 3-1. グラフ情報.
        int u = get<1>(t[i]);
        int v = get<2>(t[i]);
        LL cost = get<0>(t[i]);
        
        // 3-2. コストが負.
        // -> 必ず, 辺を追加.
        if(cost < 0){
            uf.unite(u, v);
            cSum += cost;
        }
        
        // 3-3. コストがゼロ以上.
        // -> 最小全域木に必要な場合に, 追加.
        if(cost >= 0){
            if(!uf.same(u, v)){
                uf.unite(u, v);
                cSum += cost;
            }
        }
    }
    
    // 4. 出力.
    printf("%lld\n", cTotal - cSum);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc218/editorial/2580

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vl = vector<LL>;

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

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

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

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

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

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

LL c[202020];

int a[202020], b[202020];

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

// UnionFind

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

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

// -> 一部改変.

struct UnionFind{

vi d;

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

int find(int x){

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

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

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

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

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

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

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

LL cTotal = 0;

rep(i, M){

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

a[i]--;

b[i]--;

cTotal += c[i]; // コスト合計.

}

// 2. sort.

vector<T3> t;

rep(i, M) t.emplace_back(c[i], a[i], b[i]);

sort(all(t));

// 3. 最小全域木(Kruskal's Algorithm)を計算.

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

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

LL cSum = 0;

UnionFind uf(N + 2);

rep(i, t.size()){

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

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

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

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

// 3-2. コストが負.

// -> 必ず, 辺を追加.

if(cost < 0){

uf.unite(u, v);

cSum += cost;

}

// 3-3. コストがゼロ以上.

// -> 最小全域木に必要な場合に, 追加.

if(cost >= 0){

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

uf.unite(u, v);

cSum += cost;

}

// 4. 出力.

printf("%lld\n", cTotal - cSum);

return 0;

}

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

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

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

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

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

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

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

[出力例]
13

※実際, 辺 1, 4, 5 を 取り除いて, 合計 4 + 3 + 6 = 13 の 報酬となる.

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

[出力例]
49

※実際, 辺 5, 7, 8, 10, 13, 15, 16 を 取り除いて, 合計 3 + 6 + 7 + 11 + 6 + 7 + 9 = 49 の 報酬となる.

[入力例]

4 5

1 2 1

1 3 1

1 4 1

3 2 2

4 2 2

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 2 1

2 3 0

3 1 -1

[出力例]

※AtCoderテストケースより

[入力例]

2 3

1 2 -1

1 2 2

1 1 3

[出力例]

※AtCoderテストケースより

[入力例]

5 7

1 3 4

3 4 3

1 2 -1

2 5 3

2 5 6

2 4 2

5 4 -2

[出力例]

※実際, 辺 1, 4, 5 を取り除いて, 合計 4 + 3 + 6 = 13 の報酬となる.

[入力例]

10 16

1 3 -4

7 1 3

5 3 2

3 6 -1

5 6 3

5 2 7

5 7 6

7 9 7

4 9 -3

8 9 11

4 8 4

4 2 5

2 8 6

2 10 2

6 10 7

8 10 9

[出力例]

※実際, 辺 5, 7, 8, 10, 13, 15, 16 を取り除いて, 合計 3 + 6 + 7 + 11 + 6 + 7 + 9 = 49 の報酬となる.

■参照サイト
AtCoder Beginner Contest 218
Union-Find木
 競プロ典型 90 問の問題049

2021年9月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題C (Shapes) ～問題D (Rectangles) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 問題D の解説で, 全探索で数え上げていく方針が, なるほどと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vs S, T000;
    rep(i, N){
        char c[202];
        scanf("%s", c);
        string s(c);
        S.pb(s);
    }
    rep(i, N){
        char c[202];
        scanf("%s", c);
        string s(c);
        T000.pb(s);
    }
    
    // 2. T を 90度, 180度, 270度回転させる.
    vs T090, T180, T270;
    string x(N, '.');
    rep(i, N){
        T090.pb(x);
        T180.pb(x);
        T270.pb(x);
    }
    rep(i, N) rep(j, N) T090[N - 1 - j][i] = T000[i][j];
    rep(i, N) rep(j, N) T180[N - 1 - j][i] = T090[i][j];
    rep(i, N) rep(j, N) T270[N - 1 - j][i] = T180[i][j];
    
    // 3. 図形 について, # の 位置関係を取得.
    auto f = [&](vs &s) -> set<P> {
        // 3-1. 基準となる場所を取得.
        set<P> ret;
        int sx = -1, sy = -1;
        rep(i, N){
            bool ok = false;
            rep(j, N){
                if(s[i][j] == '#'){
                    sx = i;
                    sy = j;
                    ok = true;
                    break;
                }
            }
            if(ok) break;
        }
        
        // 3-2. 位置関係を取得.
        rep(i, N) rep(j, N) if(s[i][j] == '#') ret.insert({i - sx, j - sy});
        
        // 3-3. 返却.
        return ret;
    };
    
    // 4. 各図形 について, # の 位置関係を保存.
    set<P> q0 = f(S);
    set<P> q1 = f(T000);
    set<P> q2 = f(T090);
    set<P> q3 = f(T180);
    set<P> q4 = f(T270);
    
    // 5. 出力.
    bool ans = false;
    if(q0 == q1 || q0 == q2 || q0 == q3 || q0 == q4) ans = true;
    printf("%s\n", ans ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vs S, T000;

rep(i, N){

char c[202];

scanf("%s", c);

string s(c);

S.pb(s);

}

rep(i, N){

char c[202];

scanf("%s", c);

string s(c);

T000.pb(s);

}

// 2. T を 90度, 180度, 270度回転させる.

vs T090, T180, T270;

string x(N, '.');

rep(i, N){

T090.pb(x);

T180.pb(x);

T270.pb(x);

}

rep(i, N) rep(j, N) T090[N - 1 - j][i] = T000[i][j];

rep(i, N) rep(j, N) T180[N - 1 - j][i] = T090[i][j];

rep(i, N) rep(j, N) T270[N - 1 - j][i] = T180[i][j];

// 3. 図形について, # の位置関係を取得.

auto f = [&](vs &s) -> set {

// 3-1. 基準となる場所を取得.

set ret;

int sx = -1, sy = -1;

rep(i, N){

bool ok = false;

rep(j, N){

if(s[i][j] == '#'){

sx = i;

sy = j;

ok = true;

break;

}

if(ok) break;

}

// 3-2. 位置関係を取得.

rep(i, N) rep(j, N) if(s[i][j] == '#') ret.insert({i - sx, j - sy});

// 3-3. 返却.

return ret;

};

// 4. 各図形について, # の位置関係を保存.

set q0 = f(S);

set q1 = f(T000);

set q2 = f(T090);

set q3 = f(T180);

set q4 = f(T270);

// 5. 出力.

bool ans = false;

if(q0 == q1 || q0 == q2 || q0 == q3 || q0 == q4) ans = true;

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

return 0;

}

[入力例]
5
.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

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

[入力例]
5
#####
##..#
#..##
#####
.....
#####
#..##
##..#
#####
.....

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

[入力例]
4
#...
..#.
..#.
....
#...
#...
..#.
....

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

[入力例]
4
#...
.##.
..#.
....
##..
#...
..#.
....

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

[入力例]
3
#..
.#.
...
..#
.#.
...

[出力例]
Yes

[入力例]
5
..#..
.#.#.
.###.
#...#
#...#
...##
.##..
#.#..
.##..
...##

[出力例]
Yes

[入力例]
17
.................
...#...###...###.
..#.#..#..#.#....
..#.#..#..#.#....
..###..####.#....
.#...#.#..#.#....
.#...#.#..#.#....
.#...#.###...###.
.................
.####..##..#####.
....#...#..#...#.
....#...#..#...#.
.####...#..#####.
.#......#..#...#.
.#......#..#...#.
.####..###.#####.
.................
.................
.................
####..#.###......
#..#..#....###...
#..#..#....#..#..
#..####....###...
........###......
.................
#.....#.#######..
#######.#..#..#..
#.......#..#..#..
.........#####...
#######..........
#..#..#..#####...
#..#..#.#.....#..
#..#..#.#.....#..
#######.#.....#..

[出力例]
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

[入力例]

.....

..#..

.###.

.....

....#

...##

....#

[出力例]

Yes

※AtCoderテストケースより

[入力例]

#####

##..#

#..##

#####

.....

#####

#..##

##..#

#####

.....

[出力例]

※AtCoderテストケースより

[入力例]

#...

..#.

....

#...

..#.

....

[出力例]

Yes

※AtCoderテストケースより

[入力例]

#...

.##.

..#.

....

##..

#...

..#.

....

[出力例]

※AtCoderテストケースより

[入力例]

#..

.#.

...

..#

.#.

...

[出力例]

Yes

[入力例]

..#..

.#.#.

.###.

#...#

...##

.##..

#.#..

.##..

...##

[出力例]

Yes

[入力例]

.................

...#...###...###.

..#.#..#..#.#....

..###..####.#....

.#...#.#..#.#....

.#...#.###...###.

.................

.####..##..#####.

....#...#..#...#.

.####...#..#####.

.#......#..#...#.

.####..###.#####.

.................

####..#.###......

#..#..#....###...

#..#..#....#..#..

#..####....###...

........###......

.................

#.....#.#######..

#######.#..#..#..

#.......#..#..#..

.........#####...

#######..........

#..#..#..#####...

#..#..#.#.....#..

#######.#.....#..

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/abc218/editorial/2605
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    set<P> st;
    rep(i, N){
        int x, y;
        scanf("%d %d", &x, &y);
        st.insert({x, y});
    }
    
    // 2. 全探索.
    int ans = 0;
    for(auto &p : st){
        // 左下.
        int ldX = p.a;
        int ldY = p.b;
        for(auto &q : st){
            // 右上.
            int ruX = q.a;
            int ruY = q.b;
            
            // 条件を満たすかチェック.
            if(ruX <= ldX || ruY <= ldY) continue;
            
            // 左上 を 含むか？
            bool ok = true;
            if(st.count({ldX, ruY}) == 0) ok = false;
            
            // 右下 を 含むか？
            if(st.count({ruX, ldY}) == 0) ok = false;
            
            // カウント.
            if(ok) ans++;
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc218/editorial/2605

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

set st;

rep(i, N){

int x, y;

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

st.insert({x, y});

}

// 2. 全探索.

int ans = 0;

for(auto &p : st){

// 左下.

int ldX = p.a;

int ldY = p.b;

for(auto &q : st){

// 右上.

int ruX = q.a;

int ruY = q.b;

// 条件を満たすかチェック.

if(ruX <= ldX || ruY <= ldY) continue;

// 左上を含むか？

bool ok = true;

if(st.count({ldX, ruY}) == 0) ok = false;

// 右下を含むか？

if(st.count({ruX, ldY}) == 0) ok = false;

// カウント.

if(ok) ans++;

}

// 3. 出力.

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

return 0;

}

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

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

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

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

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

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

[入力例]
12
3 2
3 7
3 11
5 4
5 7
5 11
7 2
7 4
7 7
7 11
9 7
9 11

[出力例]
10

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

[出力例]
22

[入力例]

0 0

0 1

1 0

1 1

2 0

2 1

[出力例]

※AtCoderテストケースより

[入力例]

0 1

1 2

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

0 1

1 0

2 0

2 1

2 2

3 0

3 2

[出力例]

※AtCoderテストケースより

[入力例]

3 2

3 7

3 11

5 4

5 7

5 11

7 2

7 4

7 7

7 11

9 7

9 11

[出力例]

[入力例]

1 0

1 5

1 8

0 5

0 9

0 12

3 0

3 2

3 5

3 8

2 3

2 9

10 8

10 9

10 11

2 7

5 8

5 11

5 2

5 3

2 12

9 8

9 11

4 3

4 9

6 0

6 5

7 0

7 2

7 3

7 5

7 7

7 9

[出力例]

■参照サイト
AtCoder Beginner Contest 218

2021年9月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題G (01Sequence) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc216/editorial/2474
// 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 pb push_back
const LL INF = 202020202020202020;

struct edge{
    int n; // 次の頂点.
    LL c;  // コスト.
    bool operator < (const edge &E) const{ return c > E.c; }
};

vector<edge> G[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, M){
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        edge e;
        e.n = r;
        e.c = (LL)(r - l + 1 - x);
        G[l - 1].pb(e);
    }
    
    // 2. グラフに辺を追加.
    rep(i, N){
        edge e1;
        e1.n = i + 1;
        e1.c = 1LL;
        G[i].pb(e1);
        
        edge e2;
        e2.n = i;
        e2.c = 0LL;
        G[i + 1].pb(e2);
    }
    
    // 3. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* memo){
        // 3-1. 初期化.
        priority_queue<edge> pq;
        
        // 3-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // 3-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 3-4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 3-5. 訪問済みフラグ設定.
            if(memo[cn]) continue;
            memo[cn]++;
            
            // 3-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : G[cn]){
                // 移動コスト更新.
                int nn = g.n;
                LL nc = cc + g.c;
                if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
            }
        }
        return;
    };
    
    // 4. 各頂点までの, 最短コストを求める.
    LL d[N + 1];     // 頂点 0 からの距離.
    int memo[N + 1]; // 訪問済みフラグ.
    rep(i, N + 1) d[i] = INF, memo[i] = 0;
    dijkstra(0, d, memo);
    
    // 5. 数列 A に含まれる 1 の 個数.
    LL a[N];
    rep(i, N) a[i] = 1LL - (d[i + 1] - d[i]);
    
    // 6. 出力.
    rep(i, N){
        printf("%lld", a[i]);
        printf("%s", (i < N - 1) ? " " : "\n");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2474

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

const LL INF = 202020202020202020;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

bool operator < (const edge &E) const{ return c > E.c; }

};

vector<edge> G[202020];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, M){

int l, r, x;

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

edge e;

e.n = r;

e.c = (LL)(r - l + 1 - x);

G[l - 1].pb(e);

}

// 2. グラフに辺を追加.

rep(i, N){

edge e1;

e1.n = i + 1;

e1.c = 1LL;

G[i].pb(e1);

edge e2;

e2.n = i;

e2.c = 0LL;

G[i + 1].pb(e2);

}

// 3. ダイクストラ法.

// https://ja.wikipedia.org/wiki/ダイクストラ法

auto dijkstra = [&](int s, LL* d, int* memo){

// 3-1. 初期化.

priority_queue<edge> pq;

// 3-2. 始点設定.

d[s] = 0;

pq.push({s, 0LL});

// 3-3. キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 3-4. 探索を継続するために, 頂点を取得.

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 3-5. 訪問済みフラグ設定.

if(memo[cn]) continue;

memo[cn]++;

// 3-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.

for(auto &g : G[cn]){

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});

}

return;

};

// 4. 各頂点までの, 最短コストを求める.

LL d[N + 1]; // 頂点 0 からの距離.

int memo[N + 1]; // 訪問済みフラグ.

rep(i, N + 1) d[i] = INF, memo[i] = 0;

dijkstra(0, d, memo);

// 5. 数列 A に含まれる 1 の個数.

LL a[N];

rep(i, N) a[i] = 1LL - (d[i + 1] - d[i]);

// 6. 出力.

rep(i, N){

printf("%lld", a[i]);

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

}

return 0;

}

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

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

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

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

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

[出力例]
0 0 1 1 1 1 0 1 0 0

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

[出力例]
0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1

[入力例]

6 3

1 4 3

2 2 1

4 6 2

[出力例]

0 1 1 1 0 1

※AtCoderテストケースより

[入力例]

8 2

2 6 1

3 5 3

[出力例]

0 0 1 1 1 0 0 0

※AtCoderテストケースより

[入力例]

10 5

3 7 3

1 6 4

5 5 1

6 8 2

8 10 1

[出力例]

0 0 1 1 1 1 0 1 0 0

[入力例]

25 12

9 13 2

3 5 1

6 18 6

1 6 3

10 22 6

5 18 7

9 11 1

8 15 4

7 25 9

4 5 1

3 17 7

2 11 5

[出力例]

0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1

■参照サイト
AtCoder Beginner Contest 216

2021年9月11日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc216/editorial/2560
// 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 all(x) x.begin(), x.end()
#define a first
#define b second
const LL MOD = 998244353;
LL dp[5050][5050], a[5050], b[5050];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. sort.
    vp v;
    rep(i, N) v.pb({a[i], b[i]});
    sort(all(v));
    
    // 3. dp更新.
    // Typical DP Contest (A - コンテスト) を ベース に 実装.
    // https://atcoder.jp/contests/tdpc/tasks/tdpc_contest
    dp[0][0] = 1;
    repx(i, 1, N + 1){
        // 前回分反映.
        rep(j, 5000) dp[i][j] += dp[i - 1][j];
        
        // 今回分反映.
        repr(j, 5000, 0){
            if(j + v[i - 1].b <= 5000){
                dp[i][j + v[i - 1].b] += dp[i][j];
                dp[i][j + v[i - 1].b] %= MOD;
            }
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    // 並び替え前の情報を使っていたので, index も含めて, ロジック修正(000.txt などで, WA版となった).
    // repx(i, 1, N + 1){
    //     rep(j, a[i - 1] - b[i - 1] + 1){
    rep(i, N){
        rep(j, v[i].a - v[i].b + 1){
            ans += dp[i][j];
            ans %= MOD;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2560

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vp = vector;

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

#define a first

#define b second

const LL MOD = 998244353;

LL dp[5050][5050], a[5050], b[5050];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

// 2. sort.

vp v;

rep(i, N) v.pb({a[i], b[i]});

sort(all(v));

// 3. dp更新.

// Typical DP Contest (A - コンテスト) をベースに実装.

// https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

dp[0][0] = 1;

repx(i, 1, N + 1){

// 前回分反映.

rep(j, 5000) dp[i][j] += dp[i - 1][j];

// 今回分反映.

repr(j, 5000, 0){

if(j + v[i - 1].b <= 5000){

dp[i][j + v[i - 1].b] += dp[i][j];

dp[i][j + v[i - 1].b] %= MOD;

}

// 4. 集計.

LL ans = 0;

// 並び替え前の情報を使っていたので, index も含めて, ロジック修正(000.txt などで, WA版となった).

// repx(i, 1, N + 1){

// rep(j, a[i - 1] - b[i - 1] + 1){

rep(i, N){

rep(j, v[i].a - v[i].b + 1){

ans += dp[i][j];

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
2
3 1
1 2

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

[入力例]
2
1 1
2 2

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

[入力例]
20
1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247
4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

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

[入力例]
5
11 7 8 10 1
8 8 5 4 1

[出力例]
9

[入力例]
31
41 59 26 53 58 97 93 23 84 62 64 33 83 27 9 50 28 84 19 71 69 39 93 75 10 58 20 97 49 44 59
2 30 78 16 40 62 86 20 89 98 62 80 34 82 53 42 11 70 67 98 21 4 80 86 51 32 82 30 66 4 70

[出力例]
858

[入力例]
50
24 65 106 21 21 8 21 93 35 83 20 21 18 104 82 13 74 53 26 84 94 97 120 44 117 115 109 26 123 11 18 54 106 53 53 79 57 111 29 92 26 25 65 28 55 86 11 76 19 74
14 8 115 35 57 118 76 48 7 41 63 49 41 29 10 51 95 47 95 4 36 106 108 115 70 116 48 62 58 39 81 66 101 53 17 68 73 35 90 9 111 91 20 64 4 96 39 101 30 123

[出力例]
11620

[入力例]
100
1540 1174 910 995 418 1478 131 730 2216 1677 1056 704 648 1114 794 276 1839 297 2082 83 566 913 458 1788 1528 287 281 1475 1998 570 1319 1719 1752 1008 88 953 599 235 1229 2067 1064 1590 306 1747 756 1277 146 1367 539 725 2139 1061 617 395 1947 194 703 100 441 1979 631 1717 1619 463 275 1283 1433 1788 1309 48 867 1758 997 37 1951 54 106 71 1621 1051 1502 1783 593 1097 900 249 511 934 944 1099 1826 1080 1430 1175 486 1056 2202 700 569 1914
1445 1448 56 875 681 807 1791 707 397 1056 1073 866 2079 598 722 1514 490 788 196 93 607 769 685 851 475 703 1924 1606 1414 1291 96 1641 1717 1500 852 1995 1198 469 122 619 2123 1417 277 1321 658 1783 855 1653 1938 752 1011 223 1134 1616 2032 2009 75 1369 114 1775 2126 549 1691 778 412 1636 1404 1822 822 1997 821 168 315 263 529 65 142 393 2090 1871 1385 1702 963 1838 1513 619 1996 1788 1750 180 35 1231 846 24 1355 1463 1354 885 582 674

[出力例]
10146452

[入力例]

3 1

1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 1

2 2

[出力例]

※AtCoderテストケースより

[入力例]

1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247

4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

[出力例]

476

※AtCoderテストケースより

[入力例]

11 7 8 10 1

8 8 5 4 1

[出力例]

[入力例]

41 59 26 53 58 97 93 23 84 62 64 33 83 27 9 50 28 84 19 71 69 39 93 75 10 58 20 97 49 44 59

2 30 78 16 40 62 86 20 89 98 62 80 34 82 53 42 11 70 67 98 21 4 80 86 51 32 82 30 66 4 70

[出力例]

858

[入力例]

24 65 106 21 21 8 21 93 35 83 20 21 18 104 82 13 74 53 26 84 94 97 120 44 117 115 109 26 123 11 18 54 106 53 53 79 57 111 29 92 26 25 65 28 55 86 11 76 19 74

14 8 115 35 57 118 76 48 7 41 63 49 41 29 10 51 95 47 95 4 36 106 108 115 70 116 48 62 58 39 81 66 101 53 17 68 73 35 90 9 111 91 20 64 4 96 39 101 30 123

[出力例]

11620

[入力例]

100

1540 1174 910 995 418 1478 131 730 2216 1677 1056 704 648 1114 794 276 1839 297 2082 83 566 913 458 1788 1528 287 281 1475 1998 570 1319 1719 1752 1008 88 953 599 235 1229 2067 1064 1590 306 1747 756 1277 146 1367 539 725 2139 1061 617 395 1947 194 703 100 441 1979 631 1717 1619 463 275 1283 1433 1788 1309 48 867 1758 997 37 1951 54 106 71 1621 1051 1502 1783 593 1097 900 249 511 934 944 1099 1826 1080 1430 1175 486 1056 2202 700 569 1914

1445 1448 56 875 681 807 1791 707 397 1056 1073 866 2079 598 722 1514 490 788 196 93 607 769 685 851 475 703 1924 1606 1414 1291 96 1641 1717 1500 852 1995 1198 469 122 619 2123 1417 277 1321 658 1783 855 1653 1938 752 1011 223 1134 1616 2032 2009 75 1369 114 1775 2126 549 1691 778 412 1636 1404 1822 822 1997 821 168 315 263 529 65 142 393 2090 1871 1385 1702 963 1838 1513 619 1996 1788 1750 180 35 1231 846 24 1355 1463 1354 885 582 674

[出力例]

10146452

■参照サイト
AtCoder Beginner Contest 216

2021年9月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題E (Amusement Park) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    LL K, b = 0, bSum = 0;
    scanf("%d %lld", &N, &K);
    rep(i, N){
        scanf("%lld", &a[i]);
        b += a[i];
        bSum += (a[i] + 1) * a[i] / 2;
    }
    
    // 2. 数列B の 項数が, K以下.
    if(b <= K){
        printf("%lld\n", bSum);
        return 0;
    }
    
    // 3. 評価関数.
    auto f = [&](LL m) -> bool {
        // 3-1. 数列B で, m以上となる個数.
        LL ret = 0;
        rep(i, N) ret += max(a[i] - m + 1, 0LL);
        
        // 3-2. 判定結果.
        return (ret <= K);
    };
    
    // 4. 二分探索で確認してみる.
    LL l = 1, h = 2e9 + 1, m;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    
    // 5. 集計.
    LL t = 0, ans = 0;
    rep(i, N){
        if(a[i] >= h){
            ans += (h + a[i]) * (a[i] - h + 1) / 2; // 合計.
            t += (a[i] - h + 1);                    // 項数.
        }
    }
    
    // 6. 残り.
    if(t < K) ans += (h - 1) * (K - t);
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2469

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[101010];

int main(){

// 1. 入力情報.

int N;

LL K, b = 0, bSum = 0;

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

rep(i, N){

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

b += a[i];

bSum += (a[i] + 1) * a[i] / 2;

}

// 2. 数列B の項数が, K以下.

if(b <= K){

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

return 0;

}

// 3. 評価関数.

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

// 3-1. 数列B で, m以上となる個数.

LL ret = 0;

rep(i, N) ret += max(a[i] - m + 1, 0LL);

// 3-2. 判定結果.

return (ret <= K);

};

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

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

while(l + 1 < h){

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

if(f(m)) h = m;

else l = m;

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

}

// 5. 集計.

LL t = 0, ans = 0;

rep(i, N){

if(a[i] >= h){

ans += (h + a[i]) * (a[i] - h + 1) / 2; // 合計.

t += (a[i] - h + 1); // 項数.

}

// 6. 残り.

if(t < K) ans += (h - 1) * (K - t);

// 7. 出力.

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

return 0;

}

[入力例]
3 5
100 50 102

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

[入力例]
2 2021
2 3

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

[入力例]
1 5
7

[出力例]
25

[入力例]
3 5
7 5 3

[出力例]
27

[入力例]
10 314
5 75 74 87 48 102 35 18 41 21

[出力例]
15734

[入力例]
20 2021
113 23 11 120 50 116 38 168 140 169 205 190 144 81 154 169 149 210 142 180

[出力例]
192343

[入力例]
50 20210910
5511573 1823734 1537335 3718321 5263474 1794118 2046166 3165523 1869164 1553963 1194575 1642020 5484771 2214363 692014 1043993 909762 3261784 4060954 4078088 3464262 2525049 3121061 2078598 3962003 332254 1136135 4933593 4628158 4264588 3350207 4356224 3950236 2563276 4359650 4760678 2248995 1177972 2608249 389230 3856211 1569739 1668055 1712937 2083808 4737499 5340644 4022180 466263 3292659

[出力例]
82888537486520

[入力例]

3 5

100 50 102

[出力例]

502

※AtCoderテストケースより

[入力例]

2 2021

2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 5

[出力例]

[入力例]

3 5

7 5 3

[出力例]

[入力例]

10 314

5 75 74 87 48 102 35 18 41 21

[出力例]

15734

[入力例]

20 2021

113 23 11 120 50 116 38 168 140 169 205 190 144 81 154 169 149 210 142 180

[出力例]

192343

[入力例]

50 20210910

5511573 1823734 1537335 3718321 5263474 1794118 2046166 3165523 1869164 1553963 1194575 1642020 5484771 2214363 692014 1043993 909762 3261784 4060954 4078088 3464262 2525049 3121061 2078598 3962003 332254 1136135 4933593 4628158 4264588 3350207 4356224 3950236 2563276 4359650 4760678 2248995 1177972 2608249 389230 3856211 1569739 1668055 1712937 2083808 4737499 5340644 4022180 466263 3292659

[出力例]

82888537486520

■参照サイト
AtCoder Beginner Contest 216

2021年9月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題C (Many Balls) ～問題D (Pair of Balls) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 問題D で, 計算量を減らすための, キューの利用方法が, 大変勉強になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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. 魔法を使ってみる.
    string ans = "";
    while(N){
        ans = ((N % 2 > 0) ? "A" : "B") + ans;
        if(N % 2 > 0) N--;
        else          N >>= 1;
    }
    
    // 3. 出力.
    printf("%s\n", ans.c_str());
    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. 魔法を使ってみる.

string ans = "";

while(N){

ans = ((N % 2 > 0) ? "A" : "B") + ans;

if(N % 2 > 0) N--;

else N >>= 1;

}

// 3. 出力.

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

return 0;

}

[入力例]
5

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

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

[入力例]
14

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

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

[入力例]
2021

[出力例]
ABABABABABABBBABBA

[入力例]
20210909

[出力例]
ABBBABABBABBBBABABBBABBBABABBABABABBA

[入力例]
999999999999999999

[出力例]
ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBBABABABABABABABABABABABABABABABABABA

[入力例]
1000000000000000000

[出力例]
ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBABBBBBBBBBBBBBBBBBB

[入力例]

[出力例]

AABA

※AtCoderテストケースより

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

ABBA

[入力例]

[出力例]

BBABBAAAB

※AtCoderテストケースより

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

ABABAB

[入力例]

2021

[出力例]

ABABABABABABBBABBA

[入力例]

20210909

[出力例]

ABBBABABBABBBBABABBBABBBABABBABABABBA

[入力例]

999999999999999999

[出力例]

ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBBABABABABABABABABABABABABABABABABABA

[入力例]

1000000000000000000

[出力例]

ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBABBBBBBBBBBBBBBBBBB

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vector<deque<int>> v(M), b(N);
    rep(i, M){
        int k;
        scanf("%d", &k);
        rep(j, k){
            int a;
            scanf("%d", &a);
            a--;
            v[i].pub(a); // i番目の筒に保存.
            b[a].pub(i); // 色 a のボールに, 筒の番号 i を保存.
        }
    }
    
    // 2. 筒を順番に見ていく.
    deque<int> dq;
    rep(i, M){
        // 2-1. ボールを取得.
        int t = v[i].front();
        c[t]++;
        
        // 2-2. キューに追加.
        if(c[t] == 2) dq.pub(t);
        
        // 2-3. キューが空になるまで, 筒からボールを取り除く.
        while(!dq.empty()){
            // ボールを取得.
            int u = dq.front();
            dq.pof();
            
            // 筒番号を取得.
            int p1 = b[u].front();
            b[u].pof();
            int p2 = b[u].front();
            b[u].pof();
            
            // 筒から除去.
            v[p1].pof();
            v[p2].pof();
            
            // 筒から, 一番上のボールを取得.
            int b1 = -1;
            int b2 = -1;
            if(!v[p1].empty()) b1 = v[p1].front();
            if(!v[p2].empty()) b2 = v[p2].front();
            
            // 取得したボールの出現回数を確認し, 二回であれば, キューに追加.
            if(b1 != -1){
                c[b1]++;
                if(c[b1] == 2) dq.pub(b1);
            }
            if(b2 != -1){
                c[b2]++;
                if(c[b2] == 2) dq.pub(b2);
            }
        }
    }
    
    // 3. 判定.
    bool ok = true;
    rep(i, N) if(c[i] != 2) ok = false;
    
    // 4. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2559

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pof pop_front

#define pub push_back

int c[202020];

int main(){

// 1. 入力情報.

int N, M;

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

vector<deque<int>> v(M), b(N);

rep(i, M){

int k;

scanf("%d", &k);

rep(j, k){

int a;

scanf("%d", &a);

a--;

v[i].pub(a); // i番目の筒に保存.

b[a].pub(i); // 色 a のボールに, 筒の番号 i を保存.

}

// 2. 筒を順番に見ていく.

deque<int> dq;

rep(i, M){

// 2-1. ボールを取得.

int t = v[i].front();

c[t]++;

// 2-2. キューに追加.

if(c[t] == 2) dq.pub(t);

// 2-3. キューが空になるまで, 筒からボールを取り除く.

while(!dq.empty()){

// ボールを取得.

int u = dq.front();

dq.pof();

// 筒番号を取得.

int p1 = b[u].front();

b[u].pof();

int p2 = b[u].front();

b[u].pof();

// 筒から除去.

v[p1].pof();

v[p2].pof();

// 筒から, 一番上のボールを取得.

int b1 = -1;

int b2 = -1;

if(!v[p1].empty()) b1 = v[p1].front();

if(!v[p2].empty()) b2 = v[p2].front();

// 取得したボールの出現回数を確認し, 二回であれば, キューに追加.

if(b1 != -1){

c[b1]++;

if(c[b1] == 2) dq.pub(b1);

}

if(b2 != -1){

c[b2]++;

if(c[b2] == 2) dq.pub(b2);

}

// 3. 判定.

bool ok = true;

rep(i, N) if(c[i] != 2) ok = false;

// 4. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
Yes

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

[出力例]
No

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

[出力例]
Yes

[入力例]

2 2

1 2

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 2

1 2

2 1

[出力例]

※AtCoderテストケースより

[入力例]

10 6

9 4 2 1

10 9 8 4 2

5 3 1

8 6 5 3

7 6

10 7

[出力例]

Yes

[入力例]

3 3

2 1

3 2

1 3

[出力例]

[入力例]

25 10

17 9 1

22 9 6 2

25 23 17 16 14 10 5 1

24 20 16 8 2

18 14 11 6 3

19 18 15 10 8 3 4

24 22 19 15 13 12 11 7 4

23 20 12 5

21 13 7

25 21

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 216

2021年9月7日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc217/editorial/2584
// 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;
const int LIMIT = 1010;
LL FAC[LIMIT], INV[LIMIT];
int f[808][808];
LL dp[808][808];

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

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0LL;
    // k = 0 で, 256423756 (※挙動がおかしい) が 出力されたため, ロジック修正.
    if(n == k || k == 0LL) return 1LL;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        f[a][b] = 1;
        f[b][a] = 1;
    }
    
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = mPow(FAC[i], MOD - 2);
    
    // 3. dp更新.
    rep(i, N * 2 + 1) dp[i][0] = 1;
    repx(j, 1, N * 2 + 1){
        rep(i, N * 2 + 1){
            repx(k, 1, j + 1){
                LL a1 = dp[i + 1][k - 1];
                LL a2 = dp[i + k * 2][j - k];
                LL a3 = combination((LL)j, (LL)k);
                LL a4 = f[i + 1][i + k * 2];
                dp[i][j] += a1 * a2 % MOD * a3 % MOD * a4;
                dp[i][j] %= MOD;
            }
        }
    }
    
    // 4. 出力.
    printf("%lld\n", dp[0][N]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc217/editorial/2584

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

const int LIMIT = 1010;

LL FAC[LIMIT], INV[LIMIT];

int f[808][808];

LL dp[808][808];

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

}

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

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

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

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

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

LL combination(LL n, LL k){

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

// k = 0 で, 256423756 (※挙動がおかしい) が出力されたため, ロジック修正.

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

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

return ret;

}

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, M){

int a, b;

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

f[a][b] = 1;

f[b][a] = 1;

}

// 2. 事前計算.

FAC[0] = 1;

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

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

// 3. dp更新.

rep(i, N * 2 + 1) dp[i][0] = 1;

repx(j, 1, N * 2 + 1){

rep(i, N * 2 + 1){

repx(k, 1, j + 1){

LL a1 = dp[i + 1][k - 1];

LL a2 = dp[i + k * 2][j - k];

LL a3 = combination((LL)j, (LL)k);

LL a4 = f[i + 1][i + k * 2];

dp[i][j] += a1 * a2 % MOD * a3 % MOD * a4;

dp[i][j] %= MOD;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
2 2
1 2
3 4

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

[入力例]
2 2
1 3
2 4

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

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

[出力例]
30

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

[出力例]
604800

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

[出力例]
883463798

100

[入力例]

2 3

1 2

1 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2

1 2

3 4

[出力例]

※AtCoderテストケースより

[入力例]

2 2

1 3

2 4

[出力例]

※AtCoderテストケースより

[入力例]

5 5

1 2

3 6

4 5

7 10

8 9

[出力例]

[入力例]

10 15

1 6

2 3

4 5

7 10

8 9

11 12

13 14

15 16

17 20

18 19

11 14

12 13

15 20

16 19

17 18

[出力例]

604800

[入力例]

20 35

1 2

3 4

5 6

7 8

9 10

11 12

13 14

15 16

17 18

19 20

21 22

23 24

25 26

27 28

29 30

31 32

33 34

35 36

37 38

39 40

1 10

8 9

2 7

3 6

4 5

11 30

12 29

13 28

14 27

15 26

16 25

17 24

18 23

19 22

20 21

[出力例]

883463798

■参照サイト
AtCoder Beginner Contest 217

2021年9月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題E (Sorting Queries) を解いてみた.

■感想.
1. 問題E は, 方針を絞り込めたので, AC版に到達出来たと思う.
2. 優先順位付きキューの復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. クエリ回答.
    priority_queue<int, vector<int>, greater<int>> pq;
    deque<int> dq;
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int c;
        scanf("%d", &c);
        
        // 2-2. c = 1 の 場合(末尾に追加).
        if(c == 1){
            int x;
            scanf("%d", &x);
            dq.pub(x);
        }
        
        // 2-3. c = 2 の 場合(先頭要素を出力).
        if(c == 2){
            int ans = 0;
            if(!pq.empty()){
                ans = pq.top();
                pq.pop();
            }else{
                ans = dq.front();
                dq.pof();
            }
            printf("%d\n", ans);
        }
        
        // 2-4. c = 3 の 場合(昇順sort).
        if(c == 3){
            while(!dq.empty()){
                pq.push(dq.front());
                dq.pop_front();
            }
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pof pop_front

#define pub push_back

int main(){

// 1. 入力情報.

int Q;

scanf("%d", &Q);

// 2. クエリ回答.

priority_queue<int, vector<int>, greater<int>> pq;

deque<int> dq;

rep(i, Q){

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

int c;

scanf("%d", &c);

// 2-2. c = 1 の場合(末尾に追加).

if(c == 1){

int x;

scanf("%d", &x);

dq.pub(x);

}

// 2-3. c = 2 の場合(先頭要素を出力).

if(c == 2){

int ans = 0;

if(!pq.empty()){

ans = pq.top();

pq.pop();

}else{

ans = dq.front();

dq.pof();

}

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

}

// 2-4. c = 3 の場合(昇順sort).

if(c == 3){

while(!dq.empty()){

pq.push(dq.front());

dq.pop_front();

}

return 0;

}

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

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

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

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

[入力例]
30
1 11
2
1 9
3
1 5
1 2
1 1
3
2
1 3
3
1 0
3
1 7
2
3
1 11
1 5
2
3
2
1 6
1 3
1 10
1 0
2
3
1 5
3
2

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

[入力例]

1 4

1 3

1 2

1 1

1 0

[出力例]

※AtCoderテストケースより

[入力例]

1 5

1 3

1 6

[出力例]

※AtCoderテストケースより

[入力例]

1 11

1 9

1 5

1 2

1 1

1 3

1 0

1 7

1 11

1 5

1 6

1 3

1 10

1 0

1 5

[出力例]

■参照サイト
AtCoder Beginner Contest 217

2021年9月6日2021年9月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題C (Inverse of Permutation) ～問題D (Cutting Woods) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        int p;
        scanf("%d", &p);
        q[p - 1] = i + 1;
    }
    
    // 2. 出力.
    rep(i, N){
        printf("%d", q[i]);
        printf("%s", (i < N - 1) ? " " : "\n");
    }
    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 q[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

int p;

scanf("%d", &p);

q[p - 1] = i + 1;

}

// 2. 出力.

rep(i, N){

printf("%d", q[i]);

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

}

return 0;

}

[入力例]
3
2 3 1

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

[入力例]
3
1 2 3

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

[入力例]
5
5 3 2 4 1

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

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

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

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

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

[入力例]

2 3 1

[出力例]

3 1 2

※AtCoderテストケースより

[入力例]

1 2 3

[出力例]

1 2 3

※AtCoderテストケースより

[入力例]

5 3 2 4 1

[出力例]

5 3 2 4 1

※AtCoderテストケースより

[入力例]

2 1 4 3 6 5 7

[出力例]

2 1 4 3 6 5 7

[入力例]

3 12 8 9 5 7 10 11 1 4 6 2

[出力例]

9 12 1 10 5 11 6 3 4 7 8 2

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

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

int main(){
    
    // 1. 入力情報.
    int L, Q;
    scanf("%d %d", &L, &Q);
    set<int> st;
    st.insert(0);
    st.insert(L);
    
    // 2. クエリ回答.
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int c, x;
        scanf("%d %d", &c, &x);
        
        // 2-2. c = 1 の 場合.
        if(c == 1) st.insert(x);
        
        // 2-3. c = 2 の 場合.
        if(c == 2){
            decltype(st)::iterator itr = st.lower_bound(x);
            int r = *itr;
            int l = *(--itr);
            printf("%d\n", r - 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 main(){

// 1. 入力情報.

int L, Q;

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

set<int> st;

st.insert(0);

st.insert(L);

// 2. クエリ回答.

rep(i, Q){

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

int c, x;

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

// 2-2. c = 1 の場合.

if(c == 1) st.insert(x);

// 2-3. c = 2 の場合.

if(c == 2){

decltype(st)::iterator itr = st.lower_bound(x);

int r = *itr;

int l = *(--itr);

printf("%d\n", r - l);

}

return 0;

}

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

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

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

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

[入力例]
100 10
1 31
2 41
1 59
2 26
1 53
2 58
1 97
2 93
1 23
2 84

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

[入力例]
200 20
1 172
2 99
1 54
2 121
2 169
1 3
2 178
1 65
2 128
1 165
2 187
1 44
2 199
1 117
1 88
1 196
1 77
2 1
2 123
2 85

[出力例]
172
118
118
28
107
28
28
3
48
11

[入力例]

5 3

2 2

1 3

2 2

[出力例]

※AtCoderテストケースより

[入力例]

5 3

1 2

1 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

100 10

1 31

2 41

1 59

2 26

1 53

2 58

1 97

2 93

1 23

2 84

[出力例]

※AtCoderテストケースより

[入力例]

200 20

1 172

2 99

1 54

2 121

2 169

1 3

2 178

1 65

2 128

1 165

2 187

1 44

2 199

1 117

1 88

1 196

1 77

2 1

2 123

2 85

[出力例]

172

118

107

■参照サイト
AtCoder Beginner Contest 217

C++の練習を兼ねて, AtCoder Beginner Contest 210 の 問題C (Colorful Candies) ～ 問題D (National Railway) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題C (Shapes) ～ 問題D (Rectangles) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題G (01Sequence) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題E (Amusement Park) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題C (Many Balls) ～ 問題D (Pair of Balls) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 217 の 問題E (Sorting Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の 問題C (Inverse of Permutation) ～ 問題D (Cutting Woods) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 210 の問題C (Colorful Candies) ～問題D (National Railway) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題C (Shapes) ～問題D (Rectangles) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題G (01Sequence) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題E (Amusement Park) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題C (Many Balls) ～問題D (Pair of Balls) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題E (Sorting Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題C (Inverse of Permutation) ～問題D (Cutting Woods) を解いてみた.