C++ | 個人用メモ帳

2022年2月26日

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

C++の練習を兼ねて, AtCoder Beginner Contest 147 の問題D (Xor Sum 4) を解いてみた.

■感想.
1. 問題Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題D は, 過去問 AtCoder Regular Contest 135 の問題C (XOR to All) に似ていると感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%lld", &a[i]);
        rep(j, 61){
            rep(k, 2) aCum[i + 1][j][k] = aCum[i][j][k];
            if((a[i] >> j) & 1) aCum[i + 1][j][1]++;
            else                aCum[i + 1][j][0]++;
        }
    }
    
    // 2. 集計.
    LL ans = 0;
    rep(i, N){
        rep(j, 61){
            // a[i] の j桁目.
            int d = (a[i] >> j) & 1;
            
            // 1 の とき.
            if(d){
                ans += (aCum[N][j][0] - aCum[i + 1][j][0]) * ((1LL << j) % MOD);
                ans %= MOD;
            }
            
            // 0 の とき.
            if(!d){
                ans += (aCum[N][j][1] - aCum[i + 1][j][1]) * ((1LL << j) % MOD);
                ans %= MOD;
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

LL a[303030], aCum[303030][61][2];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

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

rep(j, 61){

rep(k, 2) aCum[i + 1][j][k] = aCum[i][j][k];

if((a[i] >> j) & 1) aCum[i + 1][j][1]++;

else aCum[i + 1][j][0]++;

}

// 2. 集計.

LL ans = 0;

rep(i, N){

rep(j, 61){

// a[i] の j桁目.

int d = (a[i] >> j) & 1;

// 1 のとき.

if(d){

ans += (aCum[N][j][0] - aCum[i + 1][j][0]) * ((1LL << j) % MOD);

ans %= MOD;

}

// 0 のとき.

if(!d){

ans += (aCum[N][j][1] - aCum[i + 1][j][1]) * ((1LL << j) % MOD);

ans %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
3
1 2 3

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

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

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

[入力例]
10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

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

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

[出力例]
84

[入力例]
12
95 88 5 63 67 35 67 2 31 39 0 66

[出力例]
4098

[入力例]
120
7728 7084 5138 10586 3785 8265 10064 9492 9517 6355 1229 8848 11106 9216 10861 6522 3376 7719 6997 10628 7311 3005 7274 11121 2433 10408 3147 4419 2536 302 3314 11593 8143 5496 9052 2398 5684 8460 5320 4137 6427 7092 7170 2160 7881 12200 9637 7160 11379 6501 6887 11366 11103 433 11837 8370 1378 10234 9686 4802 9967 8762 1941 11091 1272 4861 3949 9323 2552 10617 6932 9498 4151 9893 3392 5468 1597 5925 3654 11581 4880 3159 11967 6457 12315 73 10193 379 42 6363 10239 7058 7046 11834 6938 2690 624 2103 4895 12039 10008 1781 8703 6929 10201 5117 11203 11472 12278 6264 9883 7990 10090 6055 9195 11592 1794 631 151 2299

[出力例]
56257246

[入力例]
500
2022 201 9128 2421 2021 7838 4217 7697 6106 3519 2530 2020 36850 74953 81006 6586 75551 75587 89606 97002 90356 53482 68575 32184 40607 97434 82571 96320 67400 5288 62749 28206 16596 68956 44467 58071 32198 12177 38396 87606 8878 8328 5442 2604 11263 5746 9314 3185 9707 8443 6781 6069 78336 22629 66983 57454 11210 13429 18214 4748 37107 56141 30904 6090 52272 56768 24634 46301 31230 80753 89021 3010 37346 93387 82126 12093 12608 17978 53423 74226 2023 3430 6408 2901 831 10520 1770 77 4391 4732 8497 816 84121 79525 10364 36137 91959 88459 79189 83697 41671 47523 86573 66963 49365 96912 27040 49627 51013 28984 4422 20422 41663 55405 43797 72935 526 75488 78575 53208 3748 21 47187 15692 99829 73396 53088 59700 44996 26251 62733 7159 10568 47912 76834 11125 36691 92107 77681 12267 41984 18140 19458 69994 48491 71718 4092 52312 3859 77592 154 87621 62891 51680 95331 44261 99627 79691 47902 61496 2042 73729 82578 18211 87616 66537 9270 28247 62047 48493 67427 74212 5911 9323 62395 15860 69836 65638 45323 69937 27612 62302 91630 70699 31562 99945 74847 98208 93698 24938 45429 81630 41668 83458 86860 99346 38529 24653 56694 49841 537 69836 71872 5091 49410 62308 43100 11655 24227 58868 13060 20138 56084 79366 5976 72380 34267 48843 10699 83236 16455 8880 63583 42850 3360 96190 57503 74318 96263 9235 25627 28002 51003 51747 39416 50431 54799 62224 25260 66736 8940 8111 1762 8679 11109 8493 11411 8463 7669 2814 10385 4207 93708 85624 5302 3015 28477 41998 2815 8990 74706 33739 8228 13684 91311 59172 9386 83223 35239 93946 89843 64368 261 81098 12635 81335 26437 22482 66705 93153 4575 9948 9077 2313 2853 6878 3553 11149 576 8258 6030 8205 27029 7237 4787 45750 75836 62048 17419 1239 38698 55820 61621 39252 35735 9526 90954 20445 34462 80247 97356 29152 34026 81642 1129 54421 1268 71422 25902 77406 914 4398 2985 5899 10732 10527 9285 11999 9119 7887 1391 10115 91022 28588 39817 4089 39947 92356 11862 2834 87016 45160 31449 99069 77310 52554 46266 87437 60960 50378 25877 21974 19153 25206 33676 1807 53187 94962 10715 27503 257 80385 33580 39733 64465 38383 73376 93367 85322 82701 12204 48047 91653 82387 947 96429 32658 31214 78454 54972 97562 30560 40927 8651 8551 13003 67128 57126 23699 15748 26560 79089 89411 5856 92127 8143 85591 62414 25865 80307 7590 67728 10839 5003 80955 7764 32687 61960 84805 51602 96761 36656 54364 32088 30884 6163 914 75454 4530 48225 20714 66462 91001 44085 59502 86741 78576 6845 45923 68074 46890 28115 91780 77622 76858 50207 44485 28853 22212 42017 5696 43012 24388 84984 25247 57477 15030 60358 4452 25719 28575 99935 88593 85944 56417 42759 89472 10755 5753 48079 73830 46030 33460 22140 80585 52689 4197 65869 34352 13572 32431 28575 85507 71483 44097 45230 28203 72456 29921 45166 2813 48695 10433 44958 33567 73783 56175 54372 97977 47476 8480 42124 95798 42649 15437 18304 88457 59373 236 77119

[出力例]
980143863

[入力例]

1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2 6 5 3

[出力例]

237

※AtCoderテストケースより

[入力例]

3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

[出力例]

103715602

※AtCoderテストケースより

[入力例]

1 2 3 4 5 6 7

[出力例]

[入力例]

95 88 5 63 67 35 67 2 31 39 0 66

[出力例]

4098

[入力例]

120

7728 7084 5138 10586 3785 8265 10064 9492 9517 6355 1229 8848 11106 9216 10861 6522 3376 7719 6997 10628 7311 3005 7274 11121 2433 10408 3147 4419 2536 302 3314 11593 8143 5496 9052 2398 5684 8460 5320 4137 6427 7092 7170 2160 7881 12200 9637 7160 11379 6501 6887 11366 11103 433 11837 8370 1378 10234 9686 4802 9967 8762 1941 11091 1272 4861 3949 9323 2552 10617 6932 9498 4151 9893 3392 5468 1597 5925 3654 11581 4880 3159 11967 6457 12315 73 10193 379 42 6363 10239 7058 7046 11834 6938 2690 624 2103 4895 12039 10008 1781 8703 6929 10201 5117 11203 11472 12278 6264 9883 7990 10090 6055 9195 11592 1794 631 151 2299

[出力例]

56257246

[入力例]

500

2022 201 9128 2421 2021 7838 4217 7697 6106 3519 2530 2020 36850 74953 81006 6586 75551 75587 89606 97002 90356 53482 68575 32184 40607 97434 82571 96320 67400 5288 62749 28206 16596 68956 44467 58071 32198 12177 38396 87606 8878 8328 5442 2604 11263 5746 9314 3185 9707 8443 6781 6069 78336 22629 66983 57454 11210 13429 18214 4748 37107 56141 30904 6090 52272 56768 24634 46301 31230 80753 89021 3010 37346 93387 82126 12093 12608 17978 53423 74226 2023 3430 6408 2901 831 10520 1770 77 4391 4732 8497 816 84121 79525 10364 36137 91959 88459 79189 83697 41671 47523 86573 66963 49365 96912 27040 49627 51013 28984 4422 20422 41663 55405 43797 72935 526 75488 78575 53208 3748 21 47187 15692 99829 73396 53088 59700 44996 26251 62733 7159 10568 47912 76834 11125 36691 92107 77681 12267 41984 18140 19458 69994 48491 71718 4092 52312 3859 77592 154 87621 62891 51680 95331 44261 99627 79691 47902 61496 2042 73729 82578 18211 87616 66537 9270 28247 62047 48493 67427 74212 5911 9323 62395 15860 69836 65638 45323 69937 27612 62302 91630 70699 31562 99945 74847 98208 93698 24938 45429 81630 41668 83458 86860 99346 38529 24653 56694 49841 537 69836 71872 5091 49410 62308 43100 11655 24227 58868 13060 20138 56084 79366 5976 72380 34267 48843 10699 83236 16455 8880 63583 42850 3360 96190 57503 74318 96263 9235 25627 28002 51003 51747 39416 50431 54799 62224 25260 66736 8940 8111 1762 8679 11109 8493 11411 8463 7669 2814 10385 4207 93708 85624 5302 3015 28477 41998 2815 8990 74706 33739 8228 13684 91311 59172 9386 83223 35239 93946 89843 64368 261 81098 12635 81335 26437 22482 66705 93153 4575 9948 9077 2313 2853 6878 3553 11149 576 8258 6030 8205 27029 7237 4787 45750 75836 62048 17419 1239 38698 55820 61621 39252 35735 9526 90954 20445 34462 80247 97356 29152 34026 81642 1129 54421 1268 71422 25902 77406 914 4398 2985 5899 10732 10527 9285 11999 9119 7887 1391 10115 91022 28588 39817 4089 39947 92356 11862 2834 87016 45160 31449 99069 77310 52554 46266 87437 60960 50378 25877 21974 19153 25206 33676 1807 53187 94962 10715 27503 257 80385 33580 39733 64465 38383 73376 93367 85322 82701 12204 48047 91653 82387 947 96429 32658 31214 78454 54972 97562 30560 40927 8651 8551 13003 67128 57126 23699 15748 26560 79089 89411 5856 92127 8143 85591 62414 25865 80307 7590 67728 10839 5003 80955 7764 32687 61960 84805 51602 96761 36656 54364 32088 30884 6163 914 75454 4530 48225 20714 66462 91001 44085 59502 86741 78576 6845 45923 68074 46890 28115 91780 77622 76858 50207 44485 28853 22212 42017 5696 43012 24388 84984 25247 57477 15030 60358 4452 25719 28575 99935 88593 85944 56417 42759 89472 10755 5753 48079 73830 46030 33460 22140 80585 52689 4197 65869 34352 13572 32431 28575 85507 71483 44097 45230 28203 72456 29921 45166 2813 48695 10433 44958 33567 73783 56175 54372 97977 47476 8480 42124 95798 42649 15437 18304 88457 59373 236 77119

[出力例]

980143863

■参照サイト
AtCoder Beginner Contest 147

2022年2月25日

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

C++の練習を兼ねて, エイシングプログラミングコンテスト 2019 の問題C (Alternating Path) を解いてみた.

■感想.
1. 問題Cは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 桁数オーバーフローに注意する必要があると感じた.
3. 幅優先探索の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイトエイシングプログラミングコンテスト 2019 解説の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
char board[404][404];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        char s[404];
        scanf("%s", s);
        rep(j, W) board[i][j] = (s[j] == '#');
    }
    
    // 2. グラフ構築.
    int N = H * W;
    vvi G(N);
    rep(i, H){
        rep(j, W){
            // 黒マス.
            if(board[i][j]){
                // 現在頂点.
                int u = i * W + j;
                
                // 白マス(上).
                if(i && !board[i - 1][j]){
                    int v = (i - 1) * W + j;
                    G[u].pb(v);
                    G[v].pb(u);
                }
                
                // 白マス(下).
                if(i < H - 1 && !board[i + 1][j]){
                    int v = (i + 1) * W + j;
                    G[u].pb(v);
                    G[v].pb(u);
                }
                
                // 白マス(左).
                if(j && !board[i][j - 1]){
                    int v = i * W + (j - 1);
                    G[u].pb(v);
                    G[v].pb(u);
                }
                
                // 白マス(右).
                if(j < W - 1 && !board[i][j + 1]){
                    int v = i * W + (j + 1);
                    G[u].pb(v);
                    G[v].pb(u);
                }
            }
        }
    }
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    };
    
    // 4. 連結成分に分解.
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 5. 連結成分ごとの黒マス, 白マスの個数を集計.
    int cCount[idx][2];
    rep(i, idx) cCount[i][0] = cCount[i][1] = 0;
    rep(i, H) rep(j, W) cCount[c[i * W + j] - 1][board[i][j]]++;
    
    // 6. 集計(05.txt などで, WA版となったため, long long で 確認してみる).
    LL ans = 0;
    rep(i, idx) ans += (LL)cCount[i][0] * (LL)cCount[i][1];
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

char board[404][404];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H){

char s[404];

scanf("%s", s);

rep(j, W) board[i][j] = (s[j] == '#');

}

// 2. グラフ構築.

int N = H * W;

vvi G(N);

rep(i, H){

rep(j, W){

// 黒マス.

if(board[i][j]){

// 現在頂点.

int u = i * W + j;

// 白マス(上).

if(i && !board[i - 1][j]){

int v = (i - 1) * W + j;

G[u].pb(v);

G[v].pb(u);

}

// 白マス(下).

if(i < H - 1 && !board[i + 1][j]){

int v = (i + 1) * W + j;

G[u].pb(v);

G[v].pb(u);

}

// 白マス(左).

if(j && !board[i][j - 1]){

int v = i * W + (j - 1);

G[u].pb(v);

G[v].pb(u);

}

// 白マス(右).

if(j < W - 1 && !board[i][j + 1]){

int v = i * W + (j + 1);

G[u].pb(v);

G[v].pb(u);

}

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

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

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);

}

};

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

int c[N], idx = 0;

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

rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);

// 5. 連結成分ごとの黒マス, 白マスの個数を集計.

int cCount[idx][2];

rep(i, idx) cCount[i][0] = cCount[i][1] = 0;

rep(i, H) rep(j, W) cCount[c[i * W + j] - 1][board[i][j]]++;

// 6. 集計(05.txt などで, WA版となったため, long long で確認してみる).

LL ans = 0;

rep(i, idx) ans += (LL)cCount[i][0] * (LL)cCount[i][1];

// 7. 出力.

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

return 0;

}

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

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

[入力例]
2 4
....
....

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

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

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

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

[出力例]
169

[入力例]
15 27
...........................
...........................
..####...###...##....###...
......#.#...#.#.#...#...#..
......#.#...#...#...#...#..
......#.#...#...#...#...#..
......#.#...#...#...#...#..
...###..#...#...#....####..
..#.....#...#...#.......#..
..#.....#...#...#.......#..
..#.....#...#...#.......#..
..#.....#...#...#.......#..
...####..###..#####.####...
...........................
...........................

[出力例]
285

[入力例]
21 47
...............................................
...................#.............#.............
....................##..........#.#....#.......
.....#.............#.#...........#....#.#......
....#.#...........##..#................#.......
.....#...........##....#.......................
...............###.#....#......................
..............##.#......##.....................
............##....#......#.....................
...........#.##...#.......#....................
..........#...##.........#.###.................
.........#....#.#.........###.###..............
.........#....##.......#....###..##............
........#.....#..##.........####...##..........
........#......##.....###....#..##...##........
......##.....##......#...##...#..##....##......
....###....##..........##......#...##....###...
...###..##......................##...##....###.
####..#.##.#.....................#.#....#......
.##..............................#..####.......
...#...................................####....

[出力例]
1335

[入力例]

3 3

.#.

..#

#..

[出力例]

※AtCoderテストケースより

[入力例]

2 4

....

[出力例]

※AtCoderテストケースより

[入力例]

4 3

###

...

###

[出力例]

※AtCoderテストケースより

[入力例]

5 9

....#....

...#.#...

..#...#..

.#######.

#.......#

[出力例]

169

[入力例]

15 27

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

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

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

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

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

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

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

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

[出力例]

285

[入力例]

21 47

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[出力例]

1335

■参照サイト
エイシングプログラミングコンテスト 2019

2022年2月22日

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

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

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 問題Dで, stack が利用可能なロジックであることが, 非常に面白く感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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 dp[10101];

int main(){
    
    // 1. 入力情報.
    int N, X;
    scanf("%d %d", &N, &X);
    
    // 2. dp更新.
    dp[0] = 1;
    repx(i, 1, N + 1){
        int a, b;
        scanf("%d %d", &a, &b);
        repr(j, X, 0){
            if(dp[j] == i){
                if(j + a <= X) dp[j + a] = i + 1;
                if(j + b <= X) dp[j + b] = i + 1;
            }
        }
    }
    
    // 3. 出力.
    printf("%s\n", (dp[X] == N + 1) ? "Yes" : "No");
    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 dp[10101];

int main(){

// 1. 入力情報.

int N, X;

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

// 2. dp更新.

dp[0] = 1;

repx(i, 1, N + 1){

int a, b;

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

repr(j, X, 0){

if(dp[j] == i){

if(j + a <= X) dp[j + a] = i + 1;

if(j + b <= X) dp[j + b] = i + 1;

}

// 3. 出力.

printf("%s\n", (dp[X] == N + 1) ? "Yes" : "No");

return 0;

}

[入力例]
2 10
3 6
4 5

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

[入力例]
2 10
10 100
10 100

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

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

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

[入力例]
5 77
1 12
5 9
3 11
7 16
2 19

[出力例]
No

[入力例]
12 777
55 95
60 93
11 47
37 52
18 88
67 99
51 89
39 51
11 99
72 78
65 77
32 91

[出力例]
Yes

[入力例]

2 10

3 6

4 5

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 10

10 100

[出力例]

※AtCoderテストケースより

[入力例]

4 12

1 8

5 7

3 4

2 6

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 77

1 12

5 9

3 11

7 16

2 19

[出力例]

[入力例]

12 777

55 95

60 93

11 47

37 52

18 88

67 99

51 89

39 51

11 99

72 78

65 77

32 91

[出力例]

Yes

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

// 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);
    
    // 2. クエリ回答.
    stack<P> st; // {ボールに書かれた数, 連続数}
    rep(i, N){
        int a;
        scanf("%d", &a);
        
        // 筒が空.
        if(st.empty()){
            // ボールを保存.
            st.push({a, 1});
            
            // 出力.
            printf("%d\n", st.size());
            
            // 次へ.
            continue;
        }
        
        // 筒が空でない.
        if(!st.empty()){
            // 前回と同じボールが出てきた.
            P bef = st.top();
            if(a == bef.a){
                // ボールを消す.
                if(a == bef.b + 1){
                    while(!st.empty()){
                        P t = st.top();
                        if(t.a == a) st.pop();
                        else         break;
                    }
                }
                
                // ボールを保存.
                if(a != bef.b + 1) st.push({a, bef.b + 1});
            }
            
            // 前回と異なるボールが出てきた.
            if(a != bef.a) st.push({a, 1});
            
            // 出力.
            printf("%d\n", st.size());
        }
    }
    return 0;
    
}

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

// 2. クエリ回答.

stack<P> st; // {ボールに書かれた数, 連続数}

rep(i, N){

int a;

scanf("%d", &a);

// 筒が空.

if(st.empty()){

// ボールを保存.

st.push({a, 1});

// 出力.

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

// 次へ.

continue;

}

// 筒が空でない.

if(!st.empty()){

// 前回と同じボールが出てきた.

P bef = st.top();

if(a == bef.a){

// ボールを消す.

if(a == bef.b + 1){

while(!st.empty()){

P t = st.top();

if(t.a == a) st.pop();

else break;

}

// ボールを保存.

if(a != bef.b + 1) st.push({a, bef.b + 1});

}

// 前回と異なるボールが出てきた.

if(a != bef.a) st.push({a, 1});

// 出力.

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

}

return 0;

}

[入力例]
5
3 2 3 2 2

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

[入力例]
10
2 3 2 3 3 3 2 3 3 2

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

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

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

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

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

[入力例]

3 2 3 2 2

[出力例]

※AtCoderテストケースより

[入力例]

2 3 2 3 3 3 2 3 3 2

[出力例]

※AtCoderテストケースより

[入力例]

2 3 3 2 2 3 2

[出力例]

[入力例]

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

[出力例]

■参照サイト
AtCoder Beginner Contest 240

2022年2月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 239 の問題E (Subtree K-th Max) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    rep(i, N) scanf("%d", &x[i]);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        --a;
        --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
        }
    };
    
    // 3. 根から各頂点までの最短距離.
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, 0, d);
    
    // 4. 頂点 1 から 遠い順 に並び替え.
    priority_queue<P> pq;
    rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}.
    
    // 5. 頂点に書かれた整数の保存(大きい方から, 20番目まで).
    // 5-1. 根以外.
    vpq t(N);
    vvi q(N);
    int n = 0;
    while(!pq.empty()){
        // 頂点 v を一つ取り出す.
        P p = pq.top();
        pq.pop();
        
        // 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 整数を保存.
        t[v].push(x[v]);
        
        // 頂点 v を 根とする部分木 で 集計.
        for(auto &u : G[v]){
            // 頂点 v の 子供 に 相当する頂点 u を 選択.
            if(d[u] > d[v]){
                n = 0;
                while(n < 20 && !t[u].empty()){
                    int o = t[u].top();
                    t[u].pop();
                    t[v].push(o);
                    q[u].pb(o);
                    n++;
                }
            }
        }
    }
    
    // 5-2. 根.
    // -> 根については, データの移し替えが未完了なので, ここで対応.
    //    前項と同様に, 20件以下に, 絞り込む.
    n = 0;
    while(n < 20 && !t[0].empty()){
        int o = t[0].top();
        t[0].pop();
        q[0].pb(o);
        n++;
    }
    
    // 6. sort.
    rep(i, N){
        sort(all(q[i]));
        reverse(all(q[i]));
    }
    
    // 7. クエリ回答.
    rep(i, Q){
        int v, k;
        scanf("%d %d", &v, &k);
        --v;
        --k;
        printf("%d\n", q[v][k]);
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using vpq = vector<priority_queue<int>>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

int x[101010];

int main(){

// 1. 入力情報.

int N, Q;

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

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

vvi G(N);

rep(i, N - 1){

int a, b;

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

--a;

--b;

G[a].pb(b);

G[b].pb(a);

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

// 3. 根から各頂点までの最短距離.

int d[N];

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

bfs(G, 0, d);

// 4. 頂点 1 から遠い順に並び替え.

priority_queue<P> pq;

rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}.

// 5. 頂点に書かれた整数の保存(大きい方から, 20番目まで).

// 5-1. 根以外.

vpq t(N);

vvi q(N);

int n = 0;

while(!pq.empty()){

// 頂点 v を一つ取り出す.

P p = pq.top();

pq.pop();

// 頂点 v の頂点番号は？

int v = p.b;

// 整数を保存.

t[v].push(x[v]);

// 頂点 v を根とする部分木で集計.

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

// 頂点 v の子供に相当する頂点 u を選択.

if(d[u] > d[v]){

n = 0;

while(n < 20 && !t[u].empty()){

int o = t[u].top();

t[u].pop();

t[v].push(o);

q[u].pb(o);

n++;

}

// 5-2. 根.

// -> 根については, データの移し替えが未完了なので, ここで対応.

// 前項と同様に, 20件以下に, 絞り込む.

n = 0;

while(n < 20 && !t[0].empty()){

int o = t[0].top();

t[0].pop();

q[0].pb(o);

n++;

}

// 6. sort.

rep(i, N){

sort(all(q[i]));

reverse(all(q[i]));

}

// 7. クエリ回答.

rep(i, Q){

int v, k;

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

--v;

--k;

printf("%d\n", q[v][k]);

}

return 0;

}

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

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

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

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

[入力例]
4 4
1 10 100 1000
1 2
2 3
3 4
1 4
2 3
3 2
4 1

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

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

[出力例]
5
3
8
7
12
2
5

[入力例]
20 20
111 22 33 123 222 1 0 7 77 11 88 55 77 55 7 0 1 33 55 88
1 2
1 4
1 16
6 2
6 12
7 6
5 4
3 4
5 11
5 8
10 3
9 3
17 3
10 13
10 14
10 15
18 15
19 15
20 15
1 1
1 2
1 5
1 7
1 20
2 1
2 2
3 1
3 5
3 7
4 1
4 10
5 2
6 2
9 1
10 1
10 2
15 1
15 2
19 1

[出力例]
222
123
88
77
0
55
22
88
55
33
222
33
88
1
77
88
77
88
55
55

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

[入力例]

5 2

1 2 3 4 5

1 4

2 1

2 5

3 2

1 2

2 1

[出力例]

※AtCoderテストケースより

[入力例]

6 2

10 10 10 9 8 8

1 4

2 1

2 5

3 2

6 4

1 4

2 2

[出力例]

※AtCoderテストケースより

[入力例]

4 4

1 10 100 1000

1 2

2 3

3 4

1 4

2 3

3 2

4 1

[出力例]

100

1000

※AtCoderテストケースより

[入力例]

10 7

5 5 7 7 8 10 2 3 11 12

1 2

3 1

4 1

3 5

6 3

4 9

10 4

6 7

8 6

2 1

6 2

3 2

1 5

4 1

3 5

1 7

[出力例]

[入力例]

20 20

111 22 33 123 222 1 0 7 77 11 88 55 77 55 7 0 1 33 55 88

1 2

1 4

1 16

6 2

6 12

7 6

5 4

3 4

5 11

5 8

10 3

9 3

17 3

10 13

10 14

10 15

18 15

19 15

20 15

1 1

1 2

1 5

1 7

1 20

2 1

2 2

3 1

3 5

3 7

4 1

4 10

5 2

6 2

9 1

10 1

10 2

15 1

15 2

19 1

[出力例]

222

123

222

■参照サイト
デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）

2022年2月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 239 の問題C (Knight Fork) ～問題D (Prime Sum Game) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int x1, y1, x2, y2;
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    
    // 2. 準備.
    vp v;
    repx(i, 1, 3){
        repx(j, 1, 3){
            if(i != j){
                v.pb({+i, +j});
                v.pb({-i, +j});
                v.pb({+i, -j});
                v.pb({-i, -j});
            }
        }
    }
    
    // 3. 距離が, √5 の 点は？
    set<P> st1, st2;
    for(auto &p : v){
        st1.insert({x1 + p.a, y1 + p.b});
        st2.insert({x2 + p.a, y2 + p.b});
    }
    
    // 4. 存在チェック.
    bool ok = false;
    for(auto &p : st1){
        if(st2.count(p)){
            ok = true;
            break;
        }
    }
    
    // 5. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int x1, y1, x2, y2;

scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

// 2. 準備.

vp v;

repx(i, 1, 3){

repx(j, 1, 3){

if(i != j){

v.pb({+i, +j});

v.pb({-i, +j});

v.pb({+i, -j});

v.pb({-i, -j});

}

// 3. 距離が, √5 の点は？

set<P> st1, st2;

for(auto &p : v){

st1.insert({x1 + p.a, y1 + p.b});

st2.insert({x2 + p.a, y2 + p.b});

}

// 4. 存在チェック.

bool ok = false;

for(auto &p : st1){

if(st2.count(p)){

ok = true;

break;

}

// 5. 出力.

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

return 0;

}

[入力例]
0 0 3 3

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

[入力例]
0 1 2 3

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

[入力例]
1000000000 1000000000 999999999 999999999

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

[入力例]
1 2 5 4

[出力例]
Yes

[入力例]
20 22 2 19

[出力例]
No

[入力例]

0 0 3 3

[出力例]

Yes

※AtCoderテストケースより

[入力例]

0 1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

1000000000 1000000000 999999999 999999999

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 2 5 4

[出力例]

Yes

[入力例]

20 22 2 19

[出力例]

■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 a[303];

int main(){
    
    // 1. 入力情報.
    int A, B, C, D;
    scanf("%d %d %d %d", &A, &B, &C, &D);
    
    // 2. 素数を取得.
    repx(i, 2, 303) if(!a[i]) repex(j, i * 2, 303, i) a[j]++;
    set<int> p;
    repx(i, 2, 303) if(!a[i]) p.insert(i);
    
    // 3. ゲーム.
    int ans = 0;
    repx(i, A, B + 1){
        // 整数 i に 対して, 整数 j で, (i + j) が 素数となるものがあるか？
        bool ok = false;
        repx(j, C, D + 1){
            if(!ok && p.count(i + j)){
                ans++;
                ok = true;
            }
        }
    }
    
    // 4. 出力.
    printf("%s\n", ans != (B - A + 1) ? "Takahashi" : "Aoki");
    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 a[303];

int main(){

// 1. 入力情報.

int A, B, C, D;

scanf("%d %d %d %d", &A, &B, &C, &D);

// 2. 素数を取得.

repx(i, 2, 303) if(!a[i]) repex(j, i * 2, 303, i) a[j]++;

set<int> p;

repx(i, 2, 303) if(!a[i]) p.insert(i);

// 3. ゲーム.

int ans = 0;

repx(i, A, B + 1){

// 整数 i に対して, 整数 j で, (i + j) が素数となるものがあるか？

bool ok = false;

repx(j, C, D + 1){

if(!ok && p.count(i + j)){

ans++;

ok = true;

}

// 4. 出力.

printf("%s\n", ans != (B - A + 1) ? "Takahashi" : "Aoki");

return 0;

}

[入力例]
2 3 3 4

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

[入力例]
1 100 50 60

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

[入力例]
3 14 1 5

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

[入力例]
20 22 2 19

[出力例]
Aoki

[入力例]
30 33 2 5

[出力例]
Takahashi

[入力例]

2 3 3 4

[出力例]

Aoki

※AtCoderテストケースより

[入力例]

1 100 50 60

[出力例]

Takahashi

※AtCoderテストケースより

[入力例]

3 14 1 5

[出力例]

Aoki

※AtCoderテストケースより

[入力例]

20 22 2 19

[出力例]

Aoki

[入力例]

30 33 2 5

[出力例]

Takahashi

■参照サイト
デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）

2022年2月19日2022年2月19日

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

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

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 個人的には, 大きい数が書かれた箱から処理していくというロジックが, 興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc134/editorial.pdf
// 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], b[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i + 1]);
    
    // 2. 大きい数が書かれた箱から, ボールを入れていく.
    vi ans;
    repr(i, N, 1){
        // i の 倍数が書かれた箱について, ボールが合計いくつ入っているか数える.
        int c = 0;
        repex(j, i, N + 1, i) c += b[j];
        
        // 偶奇が異なる場合に, ボールを追加.
        if((c + a[i]) & 1){
            b[i] += 1;
            ans.pb(i);
        }
    }
    
    // 3. 出力.
    int n = ans.size();
    printf("%d\n", n);
    rep(i, n) printf("%d%s", ans[i], (i < n - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 大きい数が書かれた箱から, ボールを入れていく.

vi ans;

repr(i, N, 1){

// i の倍数が書かれた箱について, ボールが合計いくつ入っているか数える.

int c = 0;

repex(j, i, N + 1, i) c += b[j];

// 偶奇が異なる場合に, ボールを追加.

if((c + a[i]) & 1){

b[i] += 1;

ans.pb(i);

}

// 3. 出力.

int n = ans.size();

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

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

return 0;

}

[入力例]
3
1 0 0

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

[入力例]
5
0 0 0 0 0

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

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

[出力例]
3
7 5 3

[入力例]
30
0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 1 0

[出力例]
12
29 27 26 25 23 22 20 16 15 11 10 3

[入力例]
100
0 0 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1

[出力例]
48
100 98 97 94 93 90 87 86 85 84 83 80 79 76 75 74 72 71 68 64 62 60 57 56 55 51 50 47 46 44 40 39 38 37 35 31 30 28 25 24 23 19 17 14 10 9 6 3

[入力例]

1 0 0

[出力例]

※AtCoderテストケースより

[入力例]

0 0 0 0 0

[出力例]

※AtCoderテストケースより

[入力例]

1 0 1 0 1 0 1

[出力例]

7 5 3

[入力例]

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

[出力例]

29 27 26 25 23 22 20 16 15 11 10 3

[入力例]

100

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

[出力例]

100 98 97 94 93 90 87 86 85 84 83 80 79 76 75 74 72 71 68 64 62 60 57 56 55 51 50 47 46 44 40 39 38 37 35 31 30 28 25 24 23 19 17 14 10 9 6 3

■参照サイト
AtCoder Beginner Contest 134

2022年2月18日2022年2月18日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 二次元累積和を計算し, 二次元累積和を参照しながら, dp更新を行うロジックが, 非常に面白いと感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc130/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
int s[2020], t[2020];
LL dp[2020][2020], dpCum[2020][2020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%d", &s[i]);
    rep(i, M) scanf("%d", &t[i]);
    
    // 2. dp更新.
    rep(i, N){
        rep(j, M){
            // 二次元累積和.
            dpCum[i + 1][j + 1] = dpCum[i][j + 1] + dpCum[i + 1][j] + MOD - dpCum[i][j] + dp[i][j];
            dpCum[i + 1][j + 1] %= MOD;
            
            // S の i文字目 と T の j文字目 を 比較.
            if(s[i] == t[j]){
                dp[i + 1][j + 1] = dpCum[i + 1][j + 1] + 1;
                dp[i + 1][j + 1] %= MOD;
            }
            
        }
    }
    
    // 3. 集計.
    // -> 部分列が, 空のケースを考慮するため, ans = 1 で 初期化.
    LL ans = 1;
    rep(i, N + 1) rep(j, M + 1) ans += dp[i][j], ans %= MOD;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

int s[2020], t[2020];

LL dp[2020][2020], dpCum[2020][2020];

int main(){

// 1. 入力情報.

int N, M;

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

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

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

// 2. dp更新.

rep(i, N){

rep(j, M){

// 二次元累積和.

dpCum[i + 1][j + 1] = dpCum[i][j + 1] + dpCum[i + 1][j] + MOD - dpCum[i][j] + dp[i][j];

dpCum[i + 1][j + 1] %= MOD;

// S の i文字目と T の j文字目を比較.

if(s[i] == t[j]){

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

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

}

// 3. 集計.

// -> 部分列が, 空のケースを考慮するため, ans = 1 で初期化.

LL ans = 1;

rep(i, N + 1) rep(j, M + 1) ans += dp[i][j], ans %= MOD;

// 4. 出力.

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

return 0;

}

[入力例]
2 2
1 3
3 1

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

[入力例]
2 2
1 1
1 1

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

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

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

[入力例]
10 9
9 6 5 7 5 9 8 5 6 7
8 6 8 5 5 7 9 9 7

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

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

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

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

[出力例]
31

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

[出力例]
395

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

[出力例]
705841659

[入力例]

2 2

1 3

3 1

[出力例]

※AtCoderのテストケースより

[入力例]

2 2

1 1

[出力例]

※AtCoderのテストケースより

[入力例]

4 4

3 4 5 6

[出力例]

※AtCoderのテストケースより

[入力例]

10 9

9 6 5 7 5 9 8 5 6 7

8 6 8 5 5 7 9 9 7

[出力例]

191

※AtCoderのテストケースより

[入力例]

20 20

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

[出力例]

846527861

※AtCoderのテストケースより

[入力例]

7 5

1 5 3 5 7 3 2

2 1 5 5 3

[出力例]

[入力例]

18 20

2 16 13 11 1 3 13 16 6 5 1 19 8 6 18 3 12 10

15 1 8 9 9 20 13 17 13 1 14 8 15 18 19 10 2 17 10 8

[出力例]

395

[入力例]

50 75

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

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

[出力例]

705841659

■参照サイト
AtCoder Beginner Contest 130

2022年2月17日

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

C++の練習を兼ねて, SoundHound Inc. Programming Contest 2018 -Masters Tournament- の問題D (Saving Snuuk) を解いてみた.

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

本家のサイト SoundHound Inc. Programming Contest 2018 -Masters Tournament- 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/soundhound2018-summer-qual/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL INF = 202020202020202020;

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

int main(){
    
    // 1. 入力情報.
    int N, M, s, t;
    scanf("%d %d %d %d", &N, &M, &s, &t);
    --s, --t;
    vector<vector<edge>> GY(N), GS(N);
    rep(i, M){
        int u, v, a, b;
        scanf("%d %d %d %d", &u, &v, &a, &b);
        u--;
        v--;
        
        // グラフ(円ベース).
        GY[u].pb(edge{v, (LL)a});
        GY[v].pb(edge{u, (LL)a});
        
        // グラフ(スヌークベース).
        GS[u].pb(edge{v, (LL)b});
        GS[v].pb(edge{u, (LL)b});
    }
    
    // 2. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](vector<vector<edge>> &G, int s, LL* d, int* memo){
        // 2-1. 初期化.
        priority_queue<edge> pq;
        
        // 2-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // 2-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 2-4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 2-5. 訪問済みフラグ設定.
            if(memo[cn]) continue;
            memo[cn]++;
            
            // 2-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});
            }
        }
    };
    
    // 3. 最小コスト計算.
    // 3-1. 都市 s から, 各都市までの, 最小コスト(円).
    LL dy[N];
    int memo[N];
    rep(i, N) dy[i] = INF, memo[i] = 0;
    dijkstra(GY, s, dy, memo);
    
    // 3-2. 都市 t から, 各都市までの, 最小コスト(スヌーク).
    LL ds[N];
    rep(i, N) ds[i] = INF, memo[i] = 0;
    dijkstra(GS, t, ds, memo);
    
    // 4. 最小コストを保存.
    LL ans[N + 1];
    rep(i, N) ans[i + 1] = INF;
    repr(i, N - 1, 0) ans[i] = min(ans[i + 1], dy[i] + ds[i]);
    
    // 5. 出力.
    rep(i, N) printf("%lld\n", 1000000000000000 - ans[i]);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/soundhound2018-summer-qual/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

const LL INF = 202020202020202020;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

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

};

int main(){

// 1. 入力情報.

int N, M, s, t;

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

--s, --t;

vector<vector<edge>> GY(N), GS(N);

rep(i, M){

int u, v, a, b;

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

u--;

v--;

// グラフ(円ベース).

GY[u].pb(edge{v, (LL)a});

GY[v].pb(edge{u, (LL)a});

// グラフ(スヌークベース).

GS[u].pb(edge{v, (LL)b});

GS[v].pb(edge{u, (LL)b});

}

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

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

auto dijkstra = [&](vector<vector<edge>> &G, int s, LL* d, int* memo){

// 2-1. 初期化.

priority_queue<edge> pq;

// 2-2. 始点設定.

d[s] = 0;

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

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

while(!pq.empty()){

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

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

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

if(memo[cn]) continue;

memo[cn]++;

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

}

};

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

// 3-1. 都市 s から, 各都市までの, 最小コスト(円).

LL dy[N];

int memo[N];

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

dijkstra(GY, s, dy, memo);

// 3-2. 都市 t から, 各都市までの, 最小コスト(スヌーク).

LL ds[N];

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

dijkstra(GS, t, ds, memo);

// 4. 最小コストを保存.

LL ans[N + 1];

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

repr(i, N - 1, 0) ans[i] = min(ans[i + 1], dy[i] + ds[i]);

// 5. 出力.

rep(i, N) printf("%lld\n", 1000000000000000 - ans[i]);

return 0;

}

[入力例]
4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1

[出力例]
999999999999998
999999999999989
999999999999979
999999999999897
※AtCoderテストケースより

[入力例]
8 12 3 8
2 8 685087149 857180777
6 7 298270585 209942236
2 4 346080035 234079976
2 5 131857300 22507157
4 8 30723332 173476334
2 6 480845267 448565596
1 4 181424400 548830121
4 5 57429995 195056405
7 8 160277628 479932440
1 6 475692952 203530153
3 5 336869679 160714712
2 7 389775999 199123879

[出力例]
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994

[入力例]
6 9 3 6
1 2 7 26
1 3 28 61
1 5 28 78
2 4 33 36
2 6 35 111
3 4 58 20
3 6 110 62
4 5 119 113
5 6 99 93

[出力例]
999999999999938
999999999999938
999999999999938
999999999999930
999999999999930
999999999999930

[入力例]
13 16 1 10   
1 3 83326247 85207902
2 6 88459189 47559762
3 4 64979941 49458276
3 6 63050768 74818459
6 7 72892460 34724650
4 5 77540583 1933897
7 8 67206752 87368224
5 8 65826188 61074237
5 9 33789592 14993064
5 13 117663151 108601936
8 10 119290100 121202962
8 12 28834706 29690680
9 11 4714256 35620023
10 11 69922693 6093865
11 12 69593125 40027289
11 13 85863036 57212982

[出力例]
999999808574628
999999808574628
999999808574628
999999793052963
999999729555516
999999729555516
999999729555516
999999729555516
999999729555516
999999729555516
999999729555516
999999638567913
999999593183231

[入力例]

4 3 2 3

1 4 1 100

1 2 1 10

1 3 20 1

[出力例]

999999999999998

999999999999989

999999999999979

999999999999897

※AtCoderテストケースより

[入力例]

8 12 3 8

2 8 685087149 857180777

6 7 298270585 209942236

2 4 346080035 234079976

2 5 131857300 22507157

4 8 30723332 173476334

2 6 480845267 448565596

1 4 181424400 548830121

4 5 57429995 195056405

7 8 160277628 479932440

1 6 475692952 203530153

3 5 336869679 160714712

2 7 389775999 199123879

[出力例]

999999574976994

[入力例]

6 9 3 6

1 2 7 26

1 3 28 61

1 5 28 78

2 4 33 36

2 6 35 111

3 4 58 20

3 6 110 62

4 5 119 113

5 6 99 93

[出力例]

999999999999938

999999999999930

[入力例]

13 16 1 10

1 3 83326247 85207902

2 6 88459189 47559762

3 4 64979941 49458276

3 6 63050768 74818459

6 7 72892460 34724650

4 5 77540583 1933897

7 8 67206752 87368224

5 8 65826188 61074237

5 9 33789592 14993064

5 13 117663151 108601936

8 10 119290100 121202962

8 12 28834706 29690680

9 11 4714256 35620023

10 11 69922693 6093865

11 12 69593125 40027289

11 13 85863036 57212982

[出力例]

999999808574628

999999793052963

999999729555516

999999638567913

999999593183231

■参照サイト
SoundHound Inc. Programming Contest 2018 -Masters Tournament-

2022年2月16日

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

C++の練習を兼ねて, JOI 2021/2022 本選過去問の問題A (インターカステラー (Intercastellar)) を解いてみた.

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

本家のサイト JOI 2021/2022 本選過去問解説の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repx(i, a, b) for(int i = a; i < b; i++)
#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;
    scanf("%d", &N);
    vl p, q;
    p.pb(0);
    rep(i, N){
        LL a, c = 0;
        scanf("%lld", &a);
        
        // ピースの細分化.
        while(a % 2 == 0){
            ++c;
            a >>= 1;
        }
        
        // 細分化したカステラ情報(位置, 長さ)を保存.
        p.pb(p.back() + (1LL << c));
        q.pb(a);
    }
    
    // 2. クエリ回答.
    int Q;
    scanf("%d", &Q);
    rep(i, Q){
        // 2-1. 質問.
        LL x;
        scanf("%lld", &x);
        
        // 2-2. カステラの場所.
        int at = lower_bound(all(p), x) - p.begin();
        --at;
        
        // 2-3. 出力.
        printf("%lld\n", q[at]);
    }
    return 0;
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

scanf("%d", &N);

vl p, q;

p.pb(0);

rep(i, N){

LL a, c = 0;

scanf("%lld", &a);

// ピースの細分化.

while(a % 2 == 0){

++c;

a >>= 1;

}

// 細分化したカステラ情報(位置, 長さ)を保存.

p.pb(p.back() + (1LL << c));

q.pb(a);

}

// 2. クエリ回答.

int Q;

scanf("%d", &Q);

rep(i, Q){

// 2-1. 質問.

LL x;

scanf("%lld", &x);

// 2-2. カステラの場所.

int at = lower_bound(all(p), x) - p.begin();

--at;

// 2-3. 出力.

printf("%lld\n", q[at]);

}

return 0;

}

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

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

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

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

[入力例]
16
536870912
402653184
536870912
536870912
134217728
536870912
671088640
536870912
536870912
536870912
939524096
805306368
536870912
956301312
536870912
536870912
5
2500000000
3355443201
4294967296
5111111111
6190792704

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

[入力例]
15
2592
7680
576
92160
57600
450
33177600
2
675
225
48000
3072000
20736
147456
45
11
233
377
610
987
1597
2584
4181
6765
10946
17711
28657

[出力例]
15
15
45
45
45
45
2025
2025
2025
2025
9

[入力例]
25
37158912
2646
840
216
73728
196
3641573376
3430
98784
1555848
1032192
260112384
47185920
1209655
1032192
12042248
236027904
110100480
393216
28800000
5529600
63221765
132765696
72576
131072
15
274
504
927
1705
3136
5768
10609
19513
35890
66012
121415
223317
410744
755476
1389537

[出力例]
567
567
567
567
567
567
567
567
567
9
27783
3969
45
45
105

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

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

536870912

402653184

536870912

134217728

536870912

671088640

536870912

939524096

805306368

536870912

956301312

536870912

2500000000

3355443201

4294967296

5111111111

6190792704

[出力例]

※AtCoderテストケースより

[入力例]

2592

7680

576

92160

57600

450

33177600

675

225

48000

3072000

20736

147456

233

377

610

987

1597

2584

4181

6765

10946

17711

28657

[出力例]

2025

[入力例]

37158912

2646

840

216

73728

196

3641573376

3430

98784

1555848

1032192

260112384

47185920

1209655

1032192

12042248

236027904

110100480

393216

28800000

5529600

63221765

132765696

72576

131072

274

504

927

1705

3136

5768

10609

19513

35890

66012

121415

223317

410744

755476

1389537

[出力例]

567

27783

3969

105

■参照サイト
JOI 2021/2022 本選過去問

2022年2月15日

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

C++の練習を兼ねて, AtCoder Beginner Contest 225 の問題C (Calendar Validator) ～問題D (Play Train) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題D で, 標準ライブラリ std::deque を利用するロジックが, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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 b[10101][7], m[7];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) rep(j, M) scanf("%d", &b[i][j]);
    
    // 2. 余り.
    // -> 006.txt などで, WA版となったので, ロジック修正.
    repx(i, 1, 8) m[i % 7] = i;
    
    // 3. 判定.
    // 3-1. 横方向.
    // -> 1ずつ増加しているか？
    //    余りも考慮.
    bool ok = true;
    rep(i, N){
        rep(j, M - 1){
            if(b[i][j + 1] != b[i][j] + 1)          ok = false;
            if(m[b[i][j + 1] % 7] < m[b[i][j] % 7]) ok = false;
        }
    }
    
    // 3-2. 縦方向.
    // -> 7ずつ増加しているか？
    rep(j, M) rep(i, N - 1) if(b[i + 1][j] != b[i][j] + 7) ok = false;
    
    // 4. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    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 b[10101][7], m[7];

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. 余り.

// -> 006.txt などで, WA版となったので, ロジック修正.

repx(i, 1, 8) m[i % 7] = i;

// 3. 判定.

// 3-1. 横方向.

// -> 1ずつ増加しているか？

// 余りも考慮.

bool ok = true;

rep(i, N){

rep(j, M - 1){

if(b[i][j + 1] != b[i][j] + 1) ok = false;

if(m[b[i][j + 1] % 7] < m[b[i][j] % 7]) ok = false;

}

// 3-2. 縦方向.

// -> 7ずつ増加しているか？

rep(j, M) rep(i, N - 1) if(b[i + 1][j] != b[i][j] + 7) ok = false;

// 4. 出力.

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

return 0;

}

[入力例]
2 3
1 2 3
8 9 10

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

[入力例]
2 1
1
2

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

[入力例]
10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

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

[入力例]
7 5
990 991 992 993 994
997 998 999 1000 1001
1004 1005 1006 1007 1008
1011 1012 1013 1014 1015
1018 1019 1020 1021 1022
1025 1026 1027 1028 1029
1032 1033 1034 1035 1036

[出力例]
Yes

[入力例]
10 5
3296 3297 3298 3299 3300
3303 3304 3305 3306 3307
3310 3311 3312 3313 3314
3317 3318 3319 3320 3321
3324 3325 3326 3327 3328
3331 3332 3333 3334 3335
3338 3339 3340 3341 3342
3345 3346 3347 3348 3349
3352 3353 3354 3355 3356
3359 3360 3361 3362 3363

[出力例]
No

[入力例]
20 3
5168 5169 5170
5175 5176 5177
5182 5183 5184
5189 5190 5191
5196 5197 5198
5203 5204 5205
5210 5211 5212
5217 5218 5219
5224 5225 5226
5231 5232 5233
5238 5239 5240
5245 5246 5247
5252 5253 5254
5259 5260 5261
5266 5267 5268
5273 5274 5275
5280 5281 5282
5287 5288 5289
5294 5295 5296
5301 5302 5303

[出力例]
Yes

[入力例]

2 3

1 2 3

8 9 10

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 1

[出力例]

※AtCoderテストケースより

[入力例]

10 4

1346 1347 1348 1349

1353 1354 1355 1356

1360 1361 1362 1363

1367 1368 1369 1370

1374 1375 1376 1377

1381 1382 1383 1384

1388 1389 1390 1391

1395 1396 1397 1398

1402 1403 1404 1405

1409 1410 1411 1412

[出力例]

Yes

※AtCoderテストケースより

[入力例]

7 5

990 991 992 993 994

997 998 999 1000 1001

1004 1005 1006 1007 1008

1011 1012 1013 1014 1015

1018 1019 1020 1021 1022

1025 1026 1027 1028 1029

1032 1033 1034 1035 1036

[出力例]

Yes

[入力例]

10 5

3296 3297 3298 3299 3300

3303 3304 3305 3306 3307

3310 3311 3312 3313 3314

3317 3318 3319 3320 3321

3324 3325 3326 3327 3328

3331 3332 3333 3334 3335

3338 3339 3340 3341 3342

3345 3346 3347 3348 3349

3352 3353 3354 3355 3356

3359 3360 3361 3362 3363

[出力例]

[入力例]

20 3

5168 5169 5170

5175 5176 5177

5182 5183 5184

5189 5190 5191

5196 5197 5198

5203 5204 5205

5210 5211 5212

5217 5218 5219

5224 5225 5226

5231 5232 5233

5238 5239 5240

5245 5246 5247

5252 5253 5254

5259 5260 5261

5266 5267 5268

5273 5274 5275

5280 5281 5282

5287 5288 5289

5294 5295 5296

5301 5302 5303

[出力例]

Yes

■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--)
#define pof pop_front
#define pob pop_back
#define puf push_front
#define pub push_back
int p[101010], q[101010];

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    
    // 2. 初期化.
    rep(i, N) p[i] = q[i] = -1;
    
    // 3. クエリ回答.
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int c;
        scanf("%d ", &c);
        
        // 3-2. クエリ 1.
        if(c == 1){
            int x, y;
            scanf("%d %d", &x, &y);
            --x;
            --y;
            
            // 電車 y の 親 を 電車 x と 設定.
            p[y] = x;
            q[x] = y;
        }
        
        // 3-3. クエリ 2.
        if(c == 2){
            int x, y;
            scanf("%d %d", &x, &y);
            --x;
            --y;
            
            // 電車 x, y の 親子関係 を 廃止.
            p[y] = -1;
            q[x] = -1;
        }
        
        // 3-4. クエリ 3.
        if(c == 3){
            int x;
            scanf("%d", &x);
            --x;
            
            // 電車 x の 親.
            int cur = x;
            deque<int> dq;
            while(cur != -1){
                dq.puf(cur);
                cur = p[cur];
            }
            
            // 電車 x の 子.
            cur = x;
            dq.pob();
            while(cur != -1){
                dq.pub(cur);
                cur = q[cur];
            }
            
            // 出力.
            int M = dq.size();
            printf("%d ", M);
            rep(i, M) printf("%d%s", dq[i] + 1, (i < M - 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--)

#define pof pop_front

#define pob pop_back

#define puf push_front

#define pub push_back

int p[101010], q[101010];

int main(){

// 1. 入力情報.

int N, Q;

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

// 2. 初期化.

rep(i, N) p[i] = q[i] = -1;

// 3. クエリ回答.

rep(i, Q){

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

int c;

scanf("%d ", &c);

// 3-2. クエリ 1.

if(c == 1){

int x, y;

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

--x;

--y;

// 電車 y の親を電車 x と設定.

p[y] = x;

q[x] = y;

}

// 3-3. クエリ 2.

if(c == 2){

int x, y;

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

--x;

--y;

// 電車 x, y の親子関係を廃止.

p[y] = -1;

q[x] = -1;

}

// 3-4. クエリ 3.

if(c == 3){

int x;

scanf("%d", &x);

--x;

// 電車 x の親.

int cur = x;

deque<int> dq;

while(cur != -1){

dq.puf(cur);

cur = p[cur];

}

// 電車 x の子.

cur = x;

dq.pob();

while(cur != -1){

dq.pub(cur);

cur = q[cur];

}

// 出力.

int M = dq.size();

printf("%d ", M);

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

}

return 0;

}

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

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

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

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

[入力例]

7 14

1 6 3

1 4 1

1 5 2

1 2 7

1 3 5

3 2

3 4

3 6

2 3 5

2 4 1

1 1 5

3 2

3 4

3 6

[出力例]

5 6 3 5 2 7

2 4 1

5 6 3 5 2 7

4 1 5 2 7

1 4

2 6 3

※AtCoderテストケースより

[入力例]

12 25

1 1 2

3 1

1 2 3

1 5 7

1 8 9

1 11 12

2 8 9

1 10 8

1 3 10

3 3

1 6 4

2 2 3

1 2 6

1 4 5

3 5

1 7 3

3 10

2 4 5

3 7

1 12 5

2 3 10

3 5

1 4 9

1 9 11

3 12

[出力例]

2 1 2

5 1 2 3 10 8

6 1 2 6 4 5 7

9 1 2 6 4 5 7 3 10 8

5 5 7 3 10 8

5 11 12 5 7 3

10 1 2 6 4 9 11 12 5 7 3

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

C++の練習を兼ねて, AtCoder Beginner Contest 147 の 問題D (Xor Sum 4) を解いてみた.

C++の練習を兼ねて, エイシング プログラミング コンテスト 2019 の 問題C (Alternating Path) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 239 の 問題E (Subtree K-th Max) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 239 の 問題C (Knight Fork) ～ 問題D (Prime Sum Game) を解いてみた.

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

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

C++の練習を兼ねて, SoundHound Inc. Programming Contest 2018 -Masters Tournament- の 問題D (Saving Snuuk) を解いてみた.

C++の練習を兼ねて, JOI 2021/2022 本選 過去問 の 問題A (インターカステラー (Intercastellar)) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 225 の 問題C (Calendar Validator) ～ 問題D (Play Train) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 147 の問題D (Xor Sum 4) を解いてみた.

C++の練習を兼ねて, エイシングプログラミングコンテスト 2019 の問題C (Alternating Path) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 239 の問題E (Subtree K-th Max) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 239 の問題C (Knight Fork) ～問題D (Prime Sum Game) を解いてみた.

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

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

C++の練習を兼ねて, SoundHound Inc. Programming Contest 2018 -Masters Tournament- の問題D (Saving Snuuk) を解いてみた.

C++の練習を兼ねて, JOI 2021/2022 本選過去問の問題A (インターカステラー (Intercastellar)) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 225 の問題C (Calendar Validator) ～問題D (Play Train) を解いてみた.