個人用メモ帳

2022年2月28日2022年2月28日

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

C++の練習を兼ねて, AtCoder Regular Contest 136 の問題A (A ↔ BB) ～問題B (Triple Shift) を解いてみた.

■感想.
1. 問題Bは, 実装してみたもののWA版となったため, 解説を参考に, 解き直ししてAC版に到達できた.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    char s[202020];
    scanf("%d %s", &N, s);
    
    // 2. 文字列操作.
    stack<char> st;
    rep(i, N){
        // 空でない.
        if(!st.empty()){
            // 'B' の 場合.
            char cur = st.top();
            if(cur == 'B'){
                // BA -> BBB -> AB
                if(s[i] == 'A'){
                    st.pop();
                    st.push('A');
                    st.push('B');
                    continue;
                }
                
                // BB -> A
                if(s[i] == 'B'){
                    st.pop();
                    st.push('A');
                    continue;
                }
            }
        }
        
        // それ以外.
        st.push(s[i]);
    }
    
    // 3. 文字列作成.
    string ans;
    while(!st.empty()){
        char t = st.top();
        st.pop();
        ans.pb(t);
    }
    
    // 4. 反転.
    reverse(all(ans));
    
    // 5. 出力.
    printf("%s\n", ans.c_str());
    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 pb push_back

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

int main(){

// 1. 入力情報.

int N;

char s[202020];

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

// 2. 文字列操作.

stack<char> st;

rep(i, N){

// 空でない.

if(!st.empty()){

// 'B' の場合.

char cur = st.top();

if(cur == 'B'){

// BA -> BBB -> AB

if(s[i] == 'A'){

st.pop();

st.push('A');

st.push('B');

continue;

}

// BB -> A

if(s[i] == 'B'){

st.pop();

st.push('A');

continue;

}

// それ以外.

st.push(s[i]);

}

// 3. 文字列作成.

string ans;

while(!st.empty()){

char t = st.top();

st.pop();

ans.pb(t);

}

// 4. 反転.

reverse(all(ans));

// 5. 出力.

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

return 0;

}

[入力例]
4
CBAA

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

[入力例]
1
A

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

[入力例]
6
BBBCBB

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

[入力例]
50
BAACACBABBACABCBBCBCBBCABAABCABACCCBABBBCCABCCABBB

[出力例]
AABCACAAABCABCACBCACAAAACAABCCCAAACCABCCAAB

[入力例]
100
BBAABAABBCABAAABCBBCAABAAABAACBBCABCCBCCCCAACCCBBABBCBBACBCACABAABBBABAAABBBCBABABBBBCCBAACBCBBACCBA

[出力例]
AAAAAABCAAAAACACAAAAAAAACACABCCBCCCCAACCCAAACAACBCACAAAAAAAAAAACAAAAACCAABCBCAACCAB

[入力例]

CBAA

[出力例]

CAAB

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

BBBCBB

[出力例]

ABCA

※AtCoderのテストケースより

[入力例]

BAACACBABBACABCBBCBCBBCABAABCABACCCBABBBCCABCCABBB

[出力例]

AABCACAAABCABCACBCACAAAACAABCCCAAACCABCCAAB

[入力例]

100

BBAABAABBCABAAABCBBCAABAAABAACBBCABCCBCCCCAACCCBBABBCBBACBCACABAABBBABAAABBBCBABABBBBCCBAACBCBBACCBA

[出力例]

AAAAAABCAAAAACACAAAAAAAACACABCCBCCCCAACCCAAACAACBCACAAAAAAAAAAACAAAAACCAABCBCAACCAB

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

// 説き直し.
// https://atcoder.jp/contests/arc136/editorial/3467
// 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[5050], b[5050], ca[5050], cb[5050];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    set<int> st;
    rep(i, N){
        scanf("%d", &a[i]);
        ca[a[i]]++;
        st.insert(a[i]);
    }
    rep(i, N){
        scanf("%d", &b[i]);
        cb[b[i]]++;
    }
    
    // 2. 例外.
    rep(i, 5050){
        if(ca[i] != cb[i]){
            puts("No");
            return 0;
        }
    }
    
    // 3. sort.
    // 3-1. 数列 A.
    int aCnt = 0;
    rep(i, N){
        int aMin = 5050, at = -1;
        repx(j, i, N){
            if(aMin > a[j]){
                aMin = a[j];
                at = j;
            }
        }
        repr(j, at, i + 1) swap(a[j], a[j - 1]);
        aCnt += (at - i);
    }
    
    // 3-2. 数列 B.
    int bCnt = 0;
    rep(i, N){
        int bMin = 5050, at = -1;
        repx(j, i, N){
            if(bMin > b[j]){
                bMin = b[j];
                at = j;
            }
        }
        repr(j, at, i + 1) swap(b[j], b[j - 1]);
        bCnt += (at - i);
    }
    
    // 4. 出力.
    if(st.size() != N) puts("Yes");
    else               printf("%s\n", ((aCnt + bCnt) % 2 == 0)  ? "Yes" : "No");
    return 0;
    
}

// 説き直し.

// https://atcoder.jp/contests/arc136/editorial/3467

// 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[5050], b[5050], ca[5050], cb[5050];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

set<int> st;

rep(i, N){

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

ca[a[i]]++;

st.insert(a[i]);

}

rep(i, N){

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

cb[b[i]]++;

}

// 2. 例外.

rep(i, 5050){

if(ca[i] != cb[i]){

puts("No");

return 0;

}

// 3. sort.

// 3-1. 数列 A.

int aCnt = 0;

rep(i, N){

int aMin = 5050, at = -1;

repx(j, i, N){

if(aMin > a[j]){

aMin = a[j];

at = j;

}

repr(j, at, i + 1) swap(a[j], a[j - 1]);

aCnt += (at - i);

}

// 3-2. 数列 B.

int bCnt = 0;

rep(i, N){

int bMin = 5050, at = -1;

repx(j, i, N){

if(bMin > b[j]){

bMin = b[j];

at = j;

}

repr(j, at, i + 1) swap(b[j], b[j - 1]);

bCnt += (at - i);

}

// 4. 出力.

if(st.size() != N) puts("Yes");

else printf("%s\n", ((aCnt + bCnt) % 2 == 0) ? "Yes" : "No");

return 0;

}

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

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

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

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

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

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

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

[出力例]
No

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

[出力例]
Yes

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

[出力例]
Yes

[入力例]

3 1 4 5

4 1 5 3

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 2 2

2 1 2

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 2 3

2 3 4

[出力例]

※AtCoderのテストケースより

[入力例]

2 1 3 5 4 7 6

1 5 6 7 2 4 3

[出力例]

[入力例]

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

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

[出力例]

Yes

[入力例]

15 25 8 34 36 50 49 44 42 11 7 21 17 27 31 30 19 43 46 5 12 16 45 33 23 13 22 35 9 1 10 41 48 20 38 28 26 6 32 18 29 2 24 39 4 3 40 37 14 47

34 7 46 27 4 43 24 40 31 13 38 45 29 23 11 30 9 39 25 10 50 19 44 36 5 3 47 8 17 37 42 15 16 22 49 1 41 32 14 20 33 26 28 18 2 12 48 35 6 21

[出力例]

Yes

■参照サイト
AtCoder Regular Contest 136

2022年2月27日2022年2月27日

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

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

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

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

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

// 説き直し.
// https://img.atcoder.jp/abc147/editorial.pdf
// 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 all(x) x.begin(), x.end()
int a[101][101], b[101][101];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H) rep(j, W) scanf("%d", &a[i + 1][j + 1]);
    rep(i, H) rep(j, W) scanf("%d", &b[i + 1][j + 1]);
    
    // 2. dp更新.
    bitset<50505> dp[H + 2][W + 2];
    dp[1][1][25000 + abs(a[1][1] - b[1][1])] = true;
    rep(k, H + W + 1){
        rep(i, min(k + 1, H + 1)){
            int j = k - i;
            if(!i || !j) continue;
            if(i > H) continue;
            if(j > W) continue;
            
            // 今回分取得.
            bitset<50505> dp00 = dp[i][j];
            bitset<50505> dp01 = dp[i][j];
            bitset<50505> dp10 = dp[i][j];
            bitset<50505> dp11 = dp[i][j];
            
            // マス(i, j) -> マス(i + 1, j).
            dp[i + 1][j] |= (dp00 <<= abs(a[i + 1][j] - b[i + 1][j]));
            dp[i + 1][j] |= (dp01 >>= abs(a[i + 1][j] - b[i + 1][j]));
            
            // マス(i, j) -> マス(i, j + 1).
            dp[i][j + 1] |= (dp10 <<= abs(a[i][j + 1] - b[i][j + 1]));
            dp[i][j + 1] |= (dp11 >>= abs(a[i][j + 1] - b[i][j + 1]));
        }
    }
    
    // 3. 文字列化.
    string dpStr = dp[H][W].to_string();
    reverse(all(dpStr));
    
    // 4. 偏りの最小値は？
    // 4-1. 右側.
    int ans = 202020;
    repx(i, 25000, dpStr.size()){
        if(dpStr[i] == '1'){
            ans = min(ans, i - 25000);
            break;
        }
    }
    
    // 4-2. 左側.
    repr(i, 25000, 0){
        if(dpStr[i] == '1'){
            ans = min(ans, 25000 - i);
            break;
        }
    }
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 説き直し.

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

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

int a[101][101], b[101][101];

int main(){

// 1. 入力情報.

int H, W;

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

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

rep(i, H) rep(j, W) scanf("%d", &b[i + 1][j + 1]);

// 2. dp更新.

bitset<50505> dp[H + 2][W + 2];

dp[1][1][25000 + abs(a[1][1] - b[1][1])] = true;

rep(k, H + W + 1){

rep(i, min(k + 1, H + 1)){

int j = k - i;

if(!i || !j) continue;

if(i > H) continue;

if(j > W) continue;

// 今回分取得.

bitset<50505> dp00 = dp[i][j];

bitset<50505> dp01 = dp[i][j];

bitset<50505> dp10 = dp[i][j];

bitset<50505> dp11 = dp[i][j];

// マス(i, j) -> マス(i + 1, j).

dp[i + 1][j] |= (dp00 <<= abs(a[i + 1][j] - b[i + 1][j]));

dp[i + 1][j] |= (dp01 >>= abs(a[i + 1][j] - b[i + 1][j]));

// マス(i, j) -> マス(i, j + 1).

dp[i][j + 1] |= (dp10 <<= abs(a[i][j + 1] - b[i][j + 1]));

dp[i][j + 1] |= (dp11 >>= abs(a[i][j + 1] - b[i][j + 1]));

}

// 3. 文字列化.

string dpStr = dp[H][W].to_string();

reverse(all(dpStr));

// 4. 偏りの最小値は？

// 4-1. 右側.

int ans = 202020;

repx(i, 25000, dpStr.size()){

if(dpStr[i] == '1'){

ans = min(ans, i - 25000);

break;

}

// 4-2. 左側.

repr(i, 25000, 0){

if(dpStr[i] == '1'){

ans = min(ans, 25000 - i);

break;

}

// 5. 出力.

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

return 0;

}

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

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

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

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

[入力例]
2 2
1 5
7 11
3 8
21 25

[出力例]
2

[入力例]
3 3
76 5 11
7 0 35
39 45 7
3 39 1
0 15 47
7 77 2

[出力例]
3

[入力例]
3 5
8 12 9 7 0
8 10 14 6 10
0 17 18 8 3
5 18 12 2 6
11 9 1 10 18
1 10 17 12 1

[出力例]
0

[入力例]

2 2

1 2

3 4

2 1

[出力例]

※AtCoderテストケースより

[入力例]

2 3

1 10 80

80 10 1

1 2 3

4 5 6

[出力例]

※AtCoderテストケースより

[入力例]

2 2

1 5

7 11

3 8

21 25

[出力例]

[入力例]

3 3

76 5 11

7 0 35

39 45 7

3 39 1

0 15 47

7 77 2

[出力例]

[入力例]

3 5

8 12 9 7 0

8 10 14 6 10

0 17 18 8 3

5 18 12 2 6

11 9 1 10 18

1 10 17 12 1

[出力例]

■参照サイト
AtCoder Beginner Contest 147

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-

C++の練習を兼ねて, AtCoder Regular Contest 136 の 問題A (A ↔ BB) ～ 問題B (Triple Shift) を解いてみた.

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

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++の練習を兼ねて, AtCoder Regular Contest 136 の問題A (A ↔ BB) ～問題B (Triple Shift) を解いてみた.

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

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) を解いてみた.