個人用メモ帳

2021年10月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題H (Red and Blue Lamps) を解いてみた.

■感想.
1. 問題H は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 個人的には, 実装に苦労したものの, 解説のロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, R;
    scanf("%d %d", &N, &R);
    set<int> st; // インデックス(操作時に使う予定).
    st.insert(N - 1);
    rep(i, N - 1){
        int a;
        scanf("%lld", &a);
        b[i + 0] += a;
        b[i + 1] += a;
        st.insert(i);
    }
    
    // 2. sort.
    PQ pq;
    rep(i, N) pq.push({b[i], i});
    
    // 3. R回繰り返す.
    R = min(R, N - R);
    LL ans = 0;
    while(!pq.empty() && R > 0){
        // 要素を取り出す.
        P u = pq.top();
        pq.pop();
        LL r = u.a;
        int i = u.b;
        
        // 左端, 右端 の インデックス.
        int idxL = *st.begin();
        int idxR = *(--st.end());
        
        // 左端 の 場合.
        bool ok = false;
        if(i == idxL){
            // 報酬加算.
            ans += r;
            
            // B[0], B[1]削除
            st.erase(st.begin());
            st.erase(st.begin());
            
            // フラグ更新.
            ok = true;
        }
        
        // 右端 の 場合.
        if(i == idxR){
            // 報酬加算.
            ans += r;
            
            // B[N], B[N - 1]削除.
            st.erase(--st.end());
            st.erase(--st.end());
            
            // フラグ更新.
            ok = true;
        }
        
        // それ以外 の 場合.
        if(i != idxL && i != idxR){
            // 存在しない場合.
            if(!st.count(i)) continue;
            
            // 報酬加算.
            ans += r;
            
            // B[i - 1], B[i], B[i + 1]取得.
            auto it = st.lower_bound(i);
            ++it;
            int tIdxR = *it;
            --it;
            --it;
            int tIdxL = *it;
            
            // B[i]更新.
            b[i] = b[tIdxL] - b[i] + b[tIdxR];
            
            // 追加.
            pq.push({b[i], i});
            
            // B[i - 1], B[i + 1]削除.
            st.erase(tIdxL);
            st.erase(tIdxR);
            
            // フラグ更新.
            ok = true;
        }
        
        // デクリメント.
        if(ok) R--;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, int>;

using PQ = priority_queue<P>;

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

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

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

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

#define a first

#define b second

LL b[202020];

int main(){

// 1. 入力情報.

int N, R;

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

set<int> st; // インデックス(操作時に使う予定).

st.insert(N - 1);

rep(i, N - 1){

int a;

scanf("%lld", &a);

b[i + 0] += a;

b[i + 1] += a;

st.insert(i);

}

// 2. sort.

PQ pq;

rep(i, N) pq.push({b[i], i});

// 3. R回繰り返す.

R = min(R, N - R);

LL ans = 0;

while(!pq.empty() && R > 0){

// 要素を取り出す.

P u = pq.top();

pq.pop();

LL r = u.a;

int i = u.b;

// 左端, 右端のインデックス.

int idxL = *st.begin();

int idxR = *(--st.end());

// 左端の場合.

bool ok = false;

if(i == idxL){

// 報酬加算.

ans += r;

// B[0], B[1]削除

st.erase(st.begin());

// フラグ更新.

ok = true;

}

// 右端の場合.

if(i == idxR){

// 報酬加算.

ans += r;

// B[N], B[N - 1]削除.

st.erase(--st.end());

// フラグ更新.

ok = true;

}

// それ以外の場合.

if(i != idxL && i != idxR){

// 存在しない場合.

if(!st.count(i)) continue;

// 報酬加算.

ans += r;

// B[i - 1], B[i], B[i + 1]取得.

auto it = st.lower_bound(i);

++it;

int tIdxR = *it;

--it;

int tIdxL = *it;

// B[i]更新.

b[i] = b[tIdxL] - b[i] + b[tIdxR];

// 追加.

pq.push({b[i], i});

// B[i - 1], B[i + 1]削除.

st.erase(tIdxL);

st.erase(tIdxR);

// フラグ更新.

ok = true;

}

// デクリメント.

if(ok) R--;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
7 6
2 7 1 8 2 8

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

[入力例]
11 7
12345 678 90123 45678901 234567 89012 3456 78901 23456 7890

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

[入力例]
6 2
36 48 38 17 53

[出力例]
156

[入力例]
19 5
314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]
6885

[入力例]
20 12
32 31 42 15 30 42 48 32 49 50 52 20 8 53 18 5 39 34 52

[出力例]
600

[入力例]
50 7
110253291 6598438 106440061 28086927 26995611 26360301 28139813 91640793 43706518 73883983 76021961 1862112 110168433 1690248 12891670 122635038 14674036 32936523 57191454 113582837 108343620 76232476 37982706 69888172 48331131 59780499 46229096 49313209 75487258 24643503 115387228 84672747 16152296 88398861 107703767 101929368 60941425 107935538 122741402 98294501 72886527 97016986 43783312 88844825 110587306 21450700 38539034 55714661 5368450

[出力例]
1390868077

[入力例]

6 2

3 1 4 1 5

[出力例]

※AtCoderテストケースより

[入力例]

7 6

2 7 1 8 2 8

[出力例]

※AtCoderテストケースより

[入力例]

11 7

12345 678 90123 45678901 234567 89012 3456 78901 23456 7890

[出力例]

46207983

※AtCoderテストケースより

[入力例]

6 2

36 48 38 17 53

[出力例]

156

[入力例]

19 5

314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]

6885

[入力例]

20 12

32 31 42 15 30 42 48 32 49 50 52 20 8 53 18 5 39 34 52

[出力例]

600

[入力例]

50 7

110253291 6598438 106440061 28086927 26995611 26360301 28139813 91640793 43706518 73883983 76021961 1862112 110168433 1690248 12891670 122635038 14674036 32936523 57191454 113582837 108343620 76232476 37982706 69888172 48331131 59780499 46229096 49313209 75487258 24643503 115387228 84672747 16152296 88398861 107703767 101929368 60941425 107935538 122741402 98294501 72886527 97016986 43783312 88844825 110587306 21450700 38539034 55714661 5368450

[出力例]

1390868077

■参照サイト
AtCoder Beginner Contest 218

2021年10月3日2021年10月3日

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

C++の練習を兼ねて, AtCoder Regular Contest 127 の問題C (Binary Strings) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 個人的には, 解説のロジックが, 不思議な感じがするとともに, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc127/editorial/2688
// 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

int main(){
    
    // 1. 入力情報.
    int N;
    char c[1010101];
    scanf("%d %s", &N, c);
    string s(c);
    
    // 2. (X - 1)作成.
    // ex.
    // N = 7, X = 1010 -> X - 1 = 0001001 を 作成.
    int l = s.size();
    int n = N - l;
    int x[N];
    int at = -1;
    repr(i, l - 1, 0){
        if(s[i] == '1'){
            at = i;
            break;
        }
    }
    rep(i, n) x[i] = 0;
    repx(i, n, n + at) x[i] = s[i - n] - '0';
    x[n + at] = 0;
    repx(i, n + at + 1, N) x[i] = 1;
    // rep(i, N) printf("%d", x[i]);
    // puts("");
    
    // 3. 文字列作成.
    // ex.
    // N = 5
    // X = 10110
    // -> X - 1 は, 10101.
    // N = 5.
    // B 10000
    // X 10101
    // -> 1 (X - 10000 を 計算)
    // 
    // N = 4
    // B 01000
    // X 00101
    // -> 10 (X - 00001 を 計算)
    // 
    // N = 3
    // B 00100
    // X 00100
    // -> 101 (X - 00100 を 計算)
    // 
    // N = 2
    // B 00010
    // X 00000
    // -> X が 0 となったので終了.
    // -> 1 + 101 = 1101 が出力されると理解.
    string ans = "";
    rep(i, N){
        // X[i] が 1.
        if(x[i]){
            x[i] = 0;
            ans.pb('1');
            continue;
        }
        
        // X[i] が 0.
        // 一番後ろの 1 の場所は？
        int cur = -1;
        repr(j, N - 1, 0){
            if(x[j]){
                cur = j;
                break;
            }
        }
        
        // X が 0(終了).
        if(cur == -1) break;
        
        // X[N - 1] が 1.
        if(cur == N - 1) x[N - 1] = 0;
        
        // X[N - 1] が 0.
        if(cur < N - 1){
            x[cur] = 0;
            repr(j, N - 1, cur + 1) x[j] = 1;
        }
        
        // '0' を 追加.
        ans.pb('0');
    }
    
    // 4. 先頭に, '1' を 追加.
    ans = "1" + ans;
    
    // 5. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

100

101

102

103

104

105

106

107

// 解き直し.

// https://atcoder.jp/contests/arc127/editorial/2688

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

int main(){

// 1. 入力情報.

int N;

char c[1010101];

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

string s(c);

// 2. (X - 1)作成.

// ex.

// N = 7, X = 1010 -> X - 1 = 0001001 を作成.

int l = s.size();

int n = N - l;

int x[N];

int at = -1;

repr(i, l - 1, 0){

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

at = i;

break;

}

rep(i, n) x[i] = 0;

repx(i, n, n + at) x[i] = s[i - n] - '0';

x[n + at] = 0;

repx(i, n + at + 1, N) x[i] = 1;

// rep(i, N) printf("%d", x[i]);

// puts("");

// 3. 文字列作成.

// ex.

// N = 5

// X = 10110

// -> X - 1 は, 10101.

// N = 5.

// B 10000

// X 10101

// -> 1 (X - 10000 を計算)

// N = 4

// B 01000

// X 00101

// -> 10 (X - 00001 を計算)

// N = 3

// B 00100

// X 00100

// -> 101 (X - 00100 を計算)

// N = 2

// B 00010

// X 00000

// -> X が 0 となったので終了.

// -> 1 + 101 = 1101 が出力されると理解.

string ans = "";

rep(i, N){

// X[i] が 1.

if(x[i]){

x[i] = 0;

ans.pb('1');

continue;

}

// X[i] が 0.

// 一番後ろの 1 の場所は？

int cur = -1;

repr(j, N - 1, 0){

if(x[j]){

cur = j;

break;

}

// X が 0(終了).

if(cur == -1) break;

// X[N - 1] が 1.

if(cur == N - 1) x[N - 1] = 0;

// X[N - 1] が 0.

if(cur < N - 1){

x[cur] = 0;

repr(j, N - 1, cur + 1) x[j] = 1;

}

// '0' を追加.

ans.pb('0');

}

// 4. 先頭に, '1' を追加.

ans = "1" + ans;

// 5. 出力.

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

return 0;

}

[入力例]
3
101

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

[入力例]
10
10100011

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

[入力例]
1000000
11111

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

[入力例]
4
1010

[出力例]
110

[入力例]
4
101

[出力例]
1001

[入力例]
5
10110

[出力例]
1101

[入力例]
31
11000111010010101001100101111

[出力例]
100110001110100101010011001

[入力例]
200
1100010111011011011111101001111010010111100001010001010110110110011110110000011010101101010000010001010000100100010101101010000111111101011111101000001100110000100001000011101100101110100000011011010

[出力例]
1011000101110110110111111010011110100101111000010100010101101101100111101100000110101011010100000100010100001001000101011010100001111111010111111010000011001100001000010000111011001011101000000011101

[入力例]
2021
1010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001001011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001

[出力例]
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001001011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100001110010001

[入力例]

101

[出力例]

※AtCoderのテストケースより

[入力例]

10100011

[出力例]

1001001111

※AtCoderのテストケースより

[入力例]

1000000

11111

[出力例]

1000000000000000000000000000000

※AtCoderのテストケースより

[入力例]

1010

[出力例]

110

[入力例]

101

[出力例]

1001

[入力例]

10110

[出力例]

1101

[入力例]

11000111010010101001100101111

[出力例]

100110001110100101010011001

[入力例]

200

1100010111011011011111101001111010010111100001010001010110110110011110110000011010101101010000010001010000100100010101101010000111111101011111101000001100110000100001000011101100101110100000011011010

[出力例]

1011000101110110110111111010011110100101111000010100010101101101100111101100000110101011010100000100010100001001000101011010100001111111010111111010000011001100001000010000111011001011101000000011101

[入力例]

2021

1010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001001011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001

[出力例]

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001001011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100001110010001

■参照サイト
AtCoder Regular Contest 127

2021年10月1日

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

C++の練習を兼ねて, AtCoder Regular Contest 127 の問題A (Leading 1s) ～問題B (Ternary Strings) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc127/editorial/2686
// 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 pob pop_back
#define pub push_back

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 集計(解説通り).
    LL ans = 0;
    repx(i, 1, 16){
        // 範囲を作成.
        // ex.
        // 先頭が, 11111 の 場合.
        // [11111,         11112)
        // [111110,       111120)
        // [1111100,     1111200)
        // [11111000,   11112000)
        // .....
        string s(i, '1');
        string g = s;
        g.pob();
        g.pub('2');
        
        rep(j, 17 - i){
            // '0' を 追加.
            string cz(j, '0');
            string cs = s + cz;
            string cg = g + cz;
            
            // 数値化.
            LL ns = stoll(cs);
            LL ng = stoll(cg);
            
            // N以下の部分を集計.
            ans += max(0LL, min(N - ns + 1, ng - ns));
        }
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc127/editorial/2686

// 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 pob pop_back

#define pub push_back

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 集計(解説通り).

LL ans = 0;

repx(i, 1, 16){

// 範囲を作成.

// ex.

// 先頭が, 11111 の場合.

// [11111, 11112)

// [111110, 111120)

// [1111100, 1111200)

// [11111000, 11112000)

// .....

string s(i, '1');

string g = s;

g.pob();

g.pub('2');

rep(j, 17 - i){

// '0' を追加.

string cz(j, '0');

string cs = s + cz;

string cg = g + cz;

// 数値化.

LL ns = stoll(cs);

LL ng = stoll(cg);

// N以下の部分を集計.

ans += max(0LL, min(N - ns + 1, ng - ns));

}

// 3. 出力.

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

return 0;

}

[入力例]
11

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

[入力例]
120

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

[入力例]
987654321

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

[入力例]
1010

[出力例]
134

[入力例]
202109252000

[出力例]
123456790122

[入力例]
101010101010101

[出力例]
13355780022446

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

120

[出力例]

※AtCoderのテストケースより

[入力例]

987654321

[出力例]

123456789

※AtCoderのテストケースより

[入力例]

1010

[出力例]

134

[入力例]

202109252000

[出力例]

123456790122

[入力例]

101010101010101

[出力例]

13355780022446

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

// 解き直し.
// https://atcoder.jp/contests/arc127/editorial/2687
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, L;
    scanf("%d %d", &N, &L);
    
    // 2. 基準とする三進数(解説通り).
    vs v1;
    int b = 2, idx = 0;
    while(++idx < L) b *= 3;
    rep(i, N){
        // 対象とする整数.
        int cur = b + i;
        
        // 三進数作成.
        string s = "";
        while(cur){
            int r = cur % 3;
            s.pb(r + '0');
            cur /= 3;
        }
        
        // 反転.
        reverse(all(s));
        
        // 保存.
        v1.pb(s);
    }
    
    // 3. 三進数(別パターン).
    // '0' -> '1'
    // '1' -> '2'
    // '2' -> '0'
    vs v2;
    for(auto &p : v1){
        // 変換.
        string q = "";
        rep(i, L){
            if(p[i] == '0') q.pb('1');
            if(p[i] == '1') q.pb('2');
            if(p[i] == '2') q.pb('0');
        }
        
        // 保存.
        v2.pb(q);
    }
    
    // 4. 三進数(別パターン).
    // '0' -> '2'
    // '1' -> '0'
    // '2' -> '1'
    vs v3;
    for(auto &p : v1){
        // 変換.
        string q = "";
        rep(i, L){
            if(p[i] == '0') q.pb('2');
            if(p[i] == '1') q.pb('0');
            if(p[i] == '2') q.pb('1');
        }
        
        // 保存.
        v3.pb(q);
    }
    
    // 5. sort(不要に見えるが念のため).
    vs ans;
    for(auto &p : v1) ans.pb(p);
    for(auto &p : v2) ans.pb(p);
    for(auto &p : v3) ans.pb(p);
    sort(all(ans));
    
    // 6. 出力.
    for(auto &p : ans) printf("%s\n", p.c_str());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc127/editorial/2687

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

int N, L;

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

// 2. 基準とする三進数(解説通り).

vs v1;

int b = 2, idx = 0;

while(++idx < L) b *= 3;

rep(i, N){

// 対象とする整数.

int cur = b + i;

// 三進数作成.

string s = "";

while(cur){

int r = cur % 3;

s.pb(r + '0');

cur /= 3;

}

// 反転.

reverse(all(s));

// 保存.

v1.pb(s);

}

// 3. 三進数(別パターン).

// '0' -> '1'

// '1' -> '2'

// '2' -> '0'

vs v2;

for(auto &p : v1){

// 変換.

string q = "";

rep(i, L){

if(p[i] == '0') q.pb('1');

if(p[i] == '1') q.pb('2');

if(p[i] == '2') q.pb('0');

}

// 保存.

v2.pb(q);

}

// 4. 三進数(別パターン).

// '0' -> '2'

// '1' -> '0'

// '2' -> '1'

vs v3;

for(auto &p : v1){

// 変換.

string q = "";

rep(i, L){

if(p[i] == '0') q.pb('2');

if(p[i] == '1') q.pb('0');

if(p[i] == '2') q.pb('1');

}

// 保存.

v3.pb(q);

}

// 5. sort(不要に見えるが念のため).

vs ans;

for(auto &p : v1) ans.pb(p);

for(auto &p : v2) ans.pb(p);

for(auto &p : v3) ans.pb(p);

sort(all(ans));

// 6. 出力.

for(auto &p : ans) printf("%s\n", p.c_str());

return 0;

}

[入力例]
2 2

[出力例]
00
02
11
12
20
21
※AtCoderのテストケースより

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

[入力例]
3 2

[出力例]
00
01
02
10
11
12
20
21
22

[入力例]
4 3

[出力例]
010
011
012
021
102
120
121
122
200
201
202
210

[入力例]
5 3

[出力例]
010
011
012
021
022
100
102
120
121
122
200
201
202
210
211

[入力例]
6 5

[出力例]
01110
01111
01112
01120
01121
01122
12200
12201
12202
12220
12221
12222
20000
20001
20002
20010
20011
20012

[入力例]

2 2

[出力例]

※AtCoderのテストケースより

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

[入力例]

3 2

[出力例]

[入力例]

4 3

[出力例]

010

011

012

021

102

120

121

122

200

201

202

210

[入力例]

5 3

[出力例]

010

011

012

021

022

100

102

120

121

122

200

201

202

210

211

[入力例]

6 5

[出力例]

01110

01111

01112

01120

01121

01122

12200

12201

12202

12220

12221

12222

20000

20001

20002

20010

20011

20012

■参照サイト
AtCoder Regular Contest 127

2021年9月30日

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

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題G (Isosceles Trapezium) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 個人的には, 垂直二等分線を考えて分類していくという方針が, 面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

struct info{
    LL x, y, c; // 二点 x, y 座標 の 合計(中点比較用), 重みの和.
    bool operator < (const info& rhs) const{
        return (c > rhs.c);
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld %lld %lld", &x[i], &y[i], &c[i]);
    
    // 2. 二点について, 垂直二等分線などを集計.
    map<T3, int> m;
    int idx = -1;
    vector<vector<info>> v(N * N);
    rep(i, N){
        repx(j, i + 1, N){
            // i -> j の ベクトル.
            LL dx = x[j] - x[i];
            LL dy = y[j] - y[i];
            
            // 最大公約数で割る.
            LL g  = __gcd(abs(dx), abs(dy));
            dx /= g;
            dy /= g;
            
            // 垂直二等分線(傾き).
            // -> ベクトル(a, b) の 形で, a >= 0 となるように保存.
            LL a = -dy;
            LL b = dx;
            if(a < 0){
                a = -a;
                b = -b;
            }
            
            // a が 0 の ケース を 考慮.
            // -> 013.txt などのテストケースで, WA版となった原因と推測.
            // -> b の 符号は, 負にならないように修正.
            if(a == 0) b = abs(b);
            
            // 垂直二等分線(切片).
            // -> 直線 b * x - a * y + a * k = 0 を 保存するイメージ.
            //    但し, 切片は, 整数で保存したいので, 二点 x, y 座標 の 合計
            //    をベースに計算した値を保存.
            LL tx = x[i] + x[j];
            LL ty = y[i] + y[j];
            LL tc = c[i] + c[j];
            LL k = a * ty - b * tx;
            
            // 垂直二等分線が一致するグループごとに分類.
            T3 t = {a, b, k};
            if(!m.count(t)) m[t] = ++idx;
            info cur;
            cur.c = tc;
            cur.x = tx;
            cur.y = ty;
            v[m[t]].pb(cur);
        }
    }
    
    // 3. 選んだ４点の重みの和の最大値.
    LL ans = -1;
    rep(i, idx){
        // sort.
        sort(all(v[i]));
        
        // 先頭要素.
        info s = v[i][0];
        
        // 最大値更新.
        repx(j, 1, v[i].size()){
            // その他の要素.
            info g = v[i][j];
            
            // 中点が一致するか？
            bool ok = (s.x == g.x) && (s.y == g.y);
            
            // 中点が一致しなければ, 最大値更新.
            if(!ok) ans = max(ans, s.c + g.c);
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

// 解き直し.

// https://atcoder.jp/contests/abc220/editorial/2684

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

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

#define pb push_back

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

LL x[1010], y[1010], c[1010];

struct info{

LL x, y, c; // 二点 x, y 座標の合計(中点比較用), 重みの和.

bool operator < (const info& rhs) const{

return (c > rhs.c);

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld %lld %lld", &x[i], &y[i], &c[i]);

// 2. 二点について, 垂直二等分線などを集計.

map<T3, int> m;

int idx = -1;

vector<vector<info>> v(N * N);

rep(i, N){

repx(j, i + 1, N){

// i -> j のベクトル.

LL dx = x[j] - x[i];

LL dy = y[j] - y[i];

// 最大公約数で割る.

LL g = __gcd(abs(dx), abs(dy));

dx /= g;

dy /= g;

// 垂直二等分線(傾き).

// -> ベクトル(a, b) の形で, a >= 0 となるように保存.

LL a = -dy;

LL b = dx;

if(a < 0){

a = -a;

b = -b;

}

// a が 0 のケースを考慮.

// -> 013.txt などのテストケースで, WA版となった原因と推測.

// -> b の符号は, 負にならないように修正.

if(a == 0) b = abs(b);

// 垂直二等分線(切片).

// -> 直線 b * x - a * y + a * k = 0 を保存するイメージ.

// 但し, 切片は, 整数で保存したいので, 二点 x, y 座標の合計

// をベースに計算した値を保存.

LL tx = x[i] + x[j];

LL ty = y[i] + y[j];

LL tc = c[i] + c[j];

LL k = a * ty - b * tx;

// 垂直二等分線が一致するグループごとに分類.

T3 t = {a, b, k};

if(!m.count(t)) m[t] = ++idx;

info cur;

cur.c = tc;

cur.x = tx;

cur.y = ty;

v[m[t]].pb(cur);

}

// 3. 選んだ４点の重みの和の最大値.

LL ans = -1;

rep(i, idx){

// sort.

sort(all(v[i]));

// 先頭要素.

info s = v[i][0];

// 最大値更新.

repx(j, 1, v[i].size()){

// その他の要素.

info g = v[i][j];

// 中点が一致するか？

bool ok = (s.x == g.x) && (s.y == g.y);

// 中点が一致しなければ, 最大値更新.

if(!ok) ans = max(ans, s.c + g.c);

}

// 4. 出力.

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

return 0;

}

[入力例]
5
0 3 10
3 3 10
-1 0 10
2 0 10000
4 0 10

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

[入力例]
6
0 1 1
1 4 20
2 7 300
5 6 4000
4 3 50000
3 0 600000

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

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

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

[入力例]
12
0 0 5
5 0 7
2 0 6
3 0 5
-1 1 7
6 1 4
-2 3 20
7 3 1
-2 0 13
7 0 3
-6 5 11
11 5 3

[出力例]
37

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

[出力例]
25

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

[出力例]
17

[入力例]

0 3 10

3 3 10

-1 0 10

2 0 10000

4 0 10

[出力例]

※AtCoderのテストケースより

[入力例]

0 1 1

1 4 20

2 7 300

5 6 4000

4 3 50000

3 0 600000

[出力例]

650021

※AtCoderのテストケースより

[入力例]

-3 0 1

-2 0 1

-1 0 1

0 0 1

1 0 1

2 0 1

3 0 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

0 0 5

5 0 7

2 0 6

3 0 5

-1 1 7

6 1 4

-2 3 20

7 3 1

-2 0 13

7 0 3

-6 5 11

11 5 3

[出力例]

[入力例]

1 0 5

0 3 7

3 -1 2

1 5 6

6 0 3

4 6 4

-10 8 11

-4 10 7

[出力例]

[入力例]

0 1 5

0 3 7

-1 -1 3

-1 5 2

[出力例]

■参照サイト
AtCoder Beginner Contest 220

2021年9月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題F (Distance Sums 2) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc220/editorial/2693
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vvi = vector<vector<int>>;
using P = pair<LL, 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
LL subTree[202020]; // 部分木の大きさ.
LL dp[202020];      // 木dp.
int p[202020];      // 親頂点.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-4. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 2-5. 未訪問の頂点を処理.
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, 0, d);
    
    // 3. 頂点 1 から 遠い順, 近い順 に 並び替え.
    // 3-1. {距離, 頂点番号} を 保存.
    priority_queue<P> fPq;
    priority_queue<P, vector<P>, greater<P>> nPq;
    rep(i, N){
        fPq.push({d[i], i});
        nPq.push({d[i], i});
    }
    
    // 3-2. 頂点 1 を 除外.
    nPq.pop();
    
    // 4. 部分木サイズなど.
    while(!fPq.empty()){
        // 4-1. 頂点 v を 取り出す.
        P i = fPq.top();
        fPq.pop();
        int v = i.b;
        
        // 4-2. 部分木更新.
        // -> 自頂点(サイズ 1)をカウント.
        subTree[v]++;
        
        // 4-3. 頂点 v を 根とする部分木.
        for(auto &u : G[v]){
            // 頂点 v の 子頂点 u を 選択.
            if(d[u] > d[v]){
                // 子頂点 u の 部分木サイズ を 加算.
                subTree[v] += subTree[u];
                
                // 親頂点 v を 保存.
                p[u] = v;
            }
        }
    }
    
    // 5. 木dp更新.
    rep(i, N) dp[0] += d[i];
    while(!nPq.empty()){
        // 5-1. 頂点 u を 取り出す.
        P i = nPq.top();
        nPq.pop();
        int u = i.b;
        
        // 5-2. 頂点 u について, dp更新.
        dp[u] = dp[p[u]] + (LL)N - 2 * subTree[u];
    }
    
    // 6. 出力.
    rep(i, N) printf("%lld\n", dp[i]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

// https://atcoder.jp/contests/abc220/editorial/2693

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vvi = vector<vector<int>>;

using P = pair<LL, 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

LL subTree[202020]; // 部分木の大きさ.

LL dp[202020]; // 木dp.

int p[202020]; // 親頂点.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int u, v;

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

u--, v--;

G[u].pb(v);

G[v].pb(u);

}

// 2. 頂点 1 から各頂点までの距離を計算.

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

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

// 2-1. 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

// 2-3. キューから取り出す.

int u = q.front();

q.pop();

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

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

// 2-5. 未訪問の頂点を処理.

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

}

return;

};

int d[N];

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

bfs(G, 0, d);

// 3. 頂点 1 から遠い順, 近い順に並び替え.

// 3-1. {距離, 頂点番号} を保存.

priority_queue<P> fPq;

priority_queue<P, vector<P>, greater<P>> nPq;

rep(i, N){

fPq.push({d[i], i});

nPq.push({d[i], i});

}

// 3-2. 頂点 1 を除外.

nPq.pop();

// 4. 部分木サイズなど.

while(!fPq.empty()){

// 4-1. 頂点 v を取り出す.

P i = fPq.top();

fPq.pop();

int v = i.b;

// 4-2. 部分木更新.

// -> 自頂点(サイズ 1)をカウント.

subTree[v]++;

// 4-3. 頂点 v を根とする部分木.

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

// 頂点 v の子頂点 u を選択.

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

// 子頂点 u の部分木サイズを加算.

subTree[v] += subTree[u];

// 親頂点 v を保存.

p[u] = v;

}

// 5. 木dp更新.

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

while(!nPq.empty()){

// 5-1. 頂点 u を取り出す.

P i = nPq.top();

nPq.pop();

int u = i.b;

// 5-2. 頂点 u について, dp更新.

dp[u] = dp[p[u]] + (LL)N - 2 * subTree[u];

}

// 6. 出力.

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

return 0;

}

[入力例]
3
1 2
2 3

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

[入力例]
2
1 2

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

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

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

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

[出力例]
18
22
30
30
16
24
28
20
28
24

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

[出力例]
100
93
88
117
117
111
87
90
110
140
140
140
136
159
159
113
97
120
108
125
131
131
148
148
148

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

[入力例]

1 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 6

1 5

1 3

1 4

1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 5

2 3

2 4

5 6

5 8

5 10

7 8

8 9

[出力例]

[入力例]

1 2

2 3

1 4

1 5

4 10

4 11

4 12

5 13

13 14

13 15

3 6

3 7

7 8

7 9

8 16

8 17

17 18

17 19

19 20

19 21

19 22

20 23

20 24

20 25

[出力例]

100

117

111

110

140

136

159

113

120

108

125

131

148

■参照サイト
AtCoder Beginner Contest 220

2021年9月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題E (Distance on Large Perfect Binary Tree) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 数え上げを正確に実装する部分で, 苦労したように思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, D;
    scanf("%d %d", &N, &D);
    
    // 2. 2 の 冪乗.
    vl mPow;
    mPow.pb(1);
    rep(i, N * 2){
        LL p = mPow.back();
        p <<= 1;
        p %= MOD;
        mPow.pb(p);
    }
    
    // 3. 深さ d ごとに集計.
    LL ans = 0;
    int n = N - 1;
    rep(d, N){
        // 3-1. 頂点 v が, i or j.
        LL f = 0;
        if(d + D <= n) f += mPow[D];
        
        // 3-2. それ以外.
        // -> 区間[d + 1, d + (D - 1)] から, x を 選択したときに,
        // d + k, d + (D - k) が, いずれも, (N - 1)以下になる場合, 集計.
        // -> 但し, k は, 0 < k < D を 満たす必要があるので, 範囲を求める際に, 要注意.
        if(D >= 2 && ((n - d) * 2 >= D)){
            int l = max(1,     min(n - d, d + D - n));
            int r = min(D - 1, max(n - d, d + D - n));
            f += mPow[D - 2] * (LL)(r - l + 1);
        }
        
        // 3-3. 集計.
        // -> 深さが d であるような頂点数は, mPow[d]個と見る.
        // -> なお, (i, j), (j, i) を 区別するため, 2通り.
        ans += f % MOD * 2LL % MOD * mPow[d] % MOD; 
        ans %= MOD;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc220/editorial/2679

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

int N, D;

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

// 2. 2 の冪乗.

vl mPow;

mPow.pb(1);

rep(i, N * 2){

LL p = mPow.back();

p <<= 1;

p %= MOD;

mPow.pb(p);

}

// 3. 深さ d ごとに集計.

LL ans = 0;

int n = N - 1;

rep(d, N){

// 3-1. 頂点 v が, i or j.

LL f = 0;

if(d + D <= n) f += mPow[D];

// 3-2. それ以外.

// -> 区間[d + 1, d + (D - 1)] から, x を選択したときに,

// d + k, d + (D - k) が, いずれも, (N - 1)以下になる場合, 集計.

// -> 但し, k は, 0 < k < D を満たす必要があるので, 範囲を求める際に, 要注意.

if(D >= 2 && ((n - d) * 2 >= D)){

int l = max(1, min(n - d, d + D - n));

int r = min(D - 1, max(n - d, d + D - n));

f += mPow[D - 2] * (LL)(r - l + 1);

}

// 3-3. 集計.

// -> 深さが d であるような頂点数は, mPow[d]個と見る.

// -> なお, (i, j), (j, i) を区別するため, 2通り.

ans += f % MOD * 2LL % MOD * mPow[d] % MOD;

ans %= MOD;

}

// 4. 出力.

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

return 0;

}

[入力例]
3 2

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

[入力例]
14142 17320

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

[入力例]
2 1

[出力例]
4

[入力例]
3 1

[出力例]
12

[入力例]
3 3

[出力例]
8

[入力例]
10 16

[出力例]
163840

[入力例]
2021 928

[出力例]
525614051

[入力例]
314159 265358

[出力例]
663838476

[入力例]

3 2

[出力例]

※AtCoderテストケースより

[入力例]

14142 17320

[出力例]

11284501

※AtCoderテストケースより

[入力例]

2 1

[出力例]

[入力例]

3 1

[出力例]

[入力例]

3 3

[出力例]

[入力例]

10 16

[出力例]

163840

[入力例]

2021 928

[出力例]

525614051

[入力例]

314159 265358

[出力例]

663838476

■参照サイト
AtCoder Beginner Contest 220

2021年9月27日

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

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題C (Long Sequence) ～問題D (FG operation) を解いてみた.

■感想.
1. 問題D は, 動的計画法の更新式を抽出できたので, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    scanf("%lld", &X);
    
    // 2. 累積和.
    rep(i, N) aCum[i + 1] = aCum[i] + a[i];
    
    // 3. 商, 余りは？
    LL q = X / aCum[N];
    LL r = X % aCum[N];
    
    // 4. 余りを超える位置は？
    int at = -1;
    rep(i, N + 1){
        if(aCum[i] > r){
            at = i;
            break;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", q * N + (LL)at);
    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--)

LL a[101010], aCum[101010];

int main(){

// 1. 入力情報.

int N;

LL X;

scanf("%d", &N);

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

scanf("%lld", &X);

// 2. 累積和.

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

// 3. 商, 余りは？

LL q = X / aCum[N];

LL r = X % aCum[N];

// 4. 余りを超える位置は？

int at = -1;

rep(i, N + 1){

if(aCum[i] > r){

at = i;

break;

}

// 5. 出力.

printf("%lld\n", q * N + (LL)at);

return 0;

}

[入力例]
3
3 5 2
26

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

[入力例]
4
12 34 56 78
1000

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

[入力例]
10
5 1 9 11 6 5 1 2 12 7
2021

[出力例]
344

[入力例]
20
34 121 72 71 95 78 78 32 86 109 73 39 81 23 68 78 54 98 76 33
20210927

[出力例]
288934

[入力例]
50
554 261 807 477 51 847 575 1186 901 415 520 381 622 1115 438 1010 625 1234 732 415 814 1193 1033 112 1125 1028 984 1113 928 535 656 12 287 874 1196 94 1089 986 177 988 812 246 414 1097 134 152 19 942 1096 1165
1000000000000000000

[出力例]
1450662952969509

[入力例]

3 5 2

[出力例]

※AtCoderテストケースより

[入力例]

12 34 56 78

1000

[出力例]

※AtCoderテストケースより

[入力例]

5 1 9 11 6 5 1 2 12 7

2021

[出力例]

344

[入力例]

34 121 72 71 95 78 78 32 86 109 73 39 81 23 68 78 54 98 76 33

20210927

[出力例]

288934

[入力例]

554 261 807 477 51 847 575 1186 901 415 520 381 622 1115 438 1010 625 1234 732 415 814 1193 1033 112 1125 1028 984 1113 928 535 656 12 287 874 1196 94 1089 986 177 988 812 246 414 1097 134 152 19 942 1096 1165

1000000000000000000

[出力例]

1450662952969509

■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 = 998244353;
LL dp[101010][10];
int a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. dp更新.
    dp[0][a[0]] = 1;
    rep(i, N - 1){
        rep(j, 10){
            // 操作 F.
            int f = (j + a[i + 1]) % 10;
            dp[i + 1][f] += dp[i][j];
            dp[i + 1][f] %= MOD;
            
            // 操作 G.
            int g = (j * a[i + 1]) % 10;
            dp[i + 1][g] += dp[i][j];
            dp[i + 1][g] %= MOD;
        }
    }
    
    // 3. 出力.
    rep(i, 10) printf("%lld\n", dp[N - 1][i]);
    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 = 998244353;

LL dp[101010][10];

int a[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. dp更新.

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

rep(i, N - 1){

rep(j, 10){

// 操作 F.

int f = (j + a[i + 1]) % 10;

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

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

// 操作 G.

int g = (j * a[i + 1]) % 10;

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

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

}

// 3. 出力.

rep(i, 10) printf("%lld\n", dp[N - 1][i]);

return 0;

}

[入力例]
3
2 7 6

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

[入力例]
5
0 1 2 3 4

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

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

[出力例]
108
2
174
38
38
4
46
10
82
10

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

[出力例]
795218227
107345812
107305502
107505240
107361985
644232897
107505240
107305502
107345812
107352373

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

[出力例]
905413840
17605008
307786178
847871598
26241917
17716361
76727260
463602346
95789053
727441864

[入力例]

2 7 6

[出力例]

※AtCoderテストケースより

[入力例]

0 1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

1 4 1 4 2 1 3 5 6 2

[出力例]

108

174

[入力例]

3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0

[出力例]

795218227

107345812

107305502

107505240

107361985

644232897

107505240

107305502

107345812

107352373

[入力例]

200

1 0 9 1 6 0 2 0 8 3 0 6 3 5 1 8 0 5 1 9 8 7 7 9 0 3 0 6 1 9 7 5 0 3 4 1 1 0 0 4 4 7 1 1 1 2 7 3 4 4 8 2 3 3 8 2 9 8 0 0 1 4 2 5 4 7 3 4 1 9 4 9 1 8 5 3 6 0 0 4 6 2 4 7 5 1 0 1 3 9 4 9 6 5 8 6 9 8 1 8 0 2 9 8 5 6 1 1 0 3 2 7 0 4 4 2 5 0 0 1 4 2 9 8 5 2 8 7 3 6 1 8 1 3 0 6 4 4 2 1 4 5 1 3 8 5 9 8 8 9 9 2 1 4 3 3 3 4 4 1 7 3 7 1 4 0 7 3 5 3 6 2 9 2 8 8 2 2 1 9 7 6 8 0 3 7 7 3 6 5 4 8 7 6 7 7 8 8 8 6

[出力例]

905413840

17605008

307786178

847871598

26241917

17716361

76727260

463602346

95789053

727441864

■参照サイト
AtCoder Beginner Contest 220

2021年9月26日2021年9月26日

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

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

■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. (競プロ典型 90 問の問題083 (Colorful Graph))に, 類似している印象を受けたものの, AC版となるための実装までに, 苦労したように思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc219/editorial/2653
// https://atcoder.jp/contests/typical90/tasks/typical90_ce
// -> 003.txt などのテストケースで, WA版となったため, ロジック修正.
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
P n[202020]; // {頂点番号, {クエリ番号, 整数}}.
P q[202020]; // {頂点番号, {クエリ番号, 整数}}(※看板).

int main(){
    
    // 1. 入力情報.
    int N, M, Q;
    scanf("%d %d %d", &N, &M, &Q);
    vvi G(N), F(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 部分グラフ作成(次数が大きい頂点に向かう頂点のみ辺を追加).
    int B = (int)sqrt(M);
    rep(i, N) if(G[i].size() >= B) for(auto &p : G[i]) F[p].pb(i);
    
    // 3. クエリ実行.
    rep(i, N) n[i].a = -1, n[i].b = i + 1;
    rep(i, N) q[i].a = -1, q[i].b = 0;
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int x;
        scanf("%d", &x);
        x--;
        
        // 3-2. (手順 1) 頂点 x の整数を正しい値に書き換え.
        // -> 一番直近のクエリ番号(値が最も大きいもの)で更新された内容を反映.
        for(auto &u : F[x]){
            if(q[u].a > n[x].a){
                n[x].a = q[u].a;
                n[x].b = q[u].b;
            }
        }
        
        // 3-3. (手順 2) 頂点 xの正しい整数を X とおく.
        int X = n[x].b;
        
        // 3-4. (手順 3) 頂点 xの次数が B 以上か否か応じて, 処理を分岐.
        int gSize = G[x].size();
        
        // (a) 隣接する頂点数が小さい場合.
        if(gSize < B){
            for(auto &u : G[x]){
                n[u].a = i;
                n[u].b = X;
            }
        }
        
        // (b) 隣接する頂点数が大きい場合.
        if(gSize >= B){
            q[x].a = i;
            q[x].b = X;
        }
    }
    
    // 4. 復元.
    rep(i, N){
        // 隣接する頂点数が大きい頂点を基準に, 各頂点 の 整数を正しい値に書き換え.
        // -> グラフ F は, 構成上, 利用できないことに注意.
        int gSize = G[i].size();
        if(gSize >= B){
            for(auto &u : G[i]){
                if(q[i].a > n[u].a){
                    n[u].a = q[i].a;
                    n[u].b = q[i].b;
                }
            }
        }
    }
    
    // 5. 出力.
    rep(i, N){
        printf("%d", n[i].b);
        printf("%s", (i < N - 1) ? " " :"\n");
    }
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/abc219/editorial/2653

// https://atcoder.jp/contests/typical90/tasks/typical90_ce

// -> 003.txt などのテストケースで, WA版となったため, ロジック修正.

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

P n[202020]; // {頂点番号, {クエリ番号, 整数}}.

P q[202020]; // {頂点番号, {クエリ番号, 整数}}(※看板).

int main(){

// 1. 入力情報.

int N, M, Q;

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

vvi G(N), F(N);

rep(i, M){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. 部分グラフ作成(次数が大きい頂点に向かう頂点のみ辺を追加).

int B = (int)sqrt(M);

rep(i, N) if(G[i].size() >= B) for(auto &p : G[i]) F[p].pb(i);

// 3. クエリ実行.

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

rep(i, N) q[i].a = -1, q[i].b = 0;

rep(i, Q){

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

int x;

scanf("%d", &x);

x--;

// 3-2. (手順 1) 頂点 x の整数を正しい値に書き換え.

// -> 一番直近のクエリ番号(値が最も大きいもの)で更新された内容を反映.

for(auto &u : F[x]){

if(q[u].a > n[x].a){

n[x].a = q[u].a;

n[x].b = q[u].b;

}

// 3-3. (手順 2) 頂点 xの正しい整数を X とおく.

int X = n[x].b;

// 3-4. (手順 3) 頂点 xの次数が B 以上か否か応じて, 処理を分岐.

int gSize = G[x].size();

// (a) 隣接する頂点数が小さい場合.

if(gSize < B){

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

n[u].a = i;

n[u].b = X;

}

// (b) 隣接する頂点数が大きい場合.

if(gSize >= B){

q[x].a = i;

q[x].b = X;

}

// 4. 復元.

rep(i, N){

// 隣接する頂点数が大きい頂点を基準に, 各頂点の整数を正しい値に書き換え.

// -> グラフ F は, 構成上, 利用できないことに注意.

int gSize = G[i].size();

if(gSize >= B){

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

if(q[i].a > n[u].a){

n[u].a = q[i].a;

n[u].b = q[i].b;

}

// 5. 出力.

rep(i, N){

printf("%d", n[i].b);

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

}

return 0;

}

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

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

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

[出力例]
1 6 1 1 6 6 1 9 9 10 11 12 10 14
※AtCoderテストケースより

[入力例]
1 0 1
1

[出力例]
1

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

[出力例]
1 1 1

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

[出力例]
1 1 7 1 7 7 7 11 1 1 11

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

[出力例]
12 3 3 3 5 5 7 7 9 10 7 12 15 15 15 15 18 18 18 3 21 22

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

[出力例]
1 1 1 1 1 1 1 8 8 8 8 8 8

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

[出力例]
1 5 5 5 5 7 7 7 7 11 11 11 11 1 1

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

[入力例]

5 6 3

4 2

4 3

1 2

2 3

4 5

1 5

1 3 4

[出力例]

1 3 3 3 3

※AtCoderテストケースより

[入力例]

14 14 8

7 4

13 9

9 8

4 3

7 2

13 8

12 8

11 3

6 3

7 14

6 5

1 4

10 13

5 2

2 6 12 9 1 10 5 4

[出力例]

1 6 1 1 6 6 1 9 9 10 11 12 10 14

※AtCoderテストケースより

[入力例]

1 0 1

[出力例]

[入力例]

3 2 3

2 1

3 2

3 1 2

[出力例]

1 1 1

[入力例]

11 13 5

2 1

2 10

2 9

10 9

2 4

4 5

4 3

3 5

3 7

3 6

7 8

8 7

8 11

7 3 1 2 11

[出力例]

1 1 7 1 7 7 7 11 1 1 11

[入力例]

22 27 8

1 17

1 5

1 6

6 5

17 18

18 19

19 17

12 1

12 13

13 14

14 12

15 13

15 14

15 16

16 13

2 3

3 4

4 2

4 20

21 20

20 22

21 22

7 8

9 8

10 9

10 11

11 7

5 18 17 12 15 3 4 7

[出力例]

12 3 3 3 5 5 7 7 9 10 7 12 15 15 15 15 18 18 18 3 21 22

[入力例]

13 12 5

1 2

1 3

1 4

1 5

1 6

1 7

8 7

8 9

8 10

8 11

8 12

8 13

1 8 1 8 1

[出力例]

1 1 1 1 1 1 1 8 8 8 8 8 8

[入力例]

15 14 10

1 10

1 3

1 6

1 14

14 15

10 11

10 12

10 13

3 2

3 4

3 5

6 7

6 8

6 9

1 14 15 7 6 5 3 11 10 14

[出力例]

1 5 5 5 5 7 7 7 7 11 11 11 11 1 1

■参照サイト
サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）
083 – Colorful Graph

2021年9月24日

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

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

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. dp更新.
    dp[0][0] = 1;
    repx(j, 1, N + 1){
        repx(i, 1, N + 1){
            dp[i][j] += dp[i - 1][j - 1] + (LL)(j - (i - 1) / M) * dp[i - 1][j];
            dp[i][j] %= MOD;
        }
    }
    
    // 3. 出力.
    repx(i, 1, N + 1) printf("%lld\n", dp[N][i]);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 998244353;

LL dp[5050][5050];

int main(){

// 1. 入力情報.

int N, M;

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

// 2. dp更新.

dp[0][0] = 1;

repx(j, 1, N + 1){

repx(i, 1, N + 1){

dp[i][j] += dp[i - 1][j - 1] + (LL)(j - (i - 1) / M) * dp[i - 1][j];

dp[i][j] %= MOD;

}

// 3. 出力.

repx(i, 1, N + 1) printf("%lld\n", dp[N][i]);

return 0;

}

[入力例]
4 2

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

[入力例]
6 6

[出力例]
1
31
90
65
15
1
※AtCoderテストケースより

[入力例]
20 5

[出力例]
0
0
0
331776
207028224
204931064
814022582
544352515
755619435
401403040
323173195
538468102
309259764
722947327
162115584
10228144
423360
10960
160
1
※AtCoderテストケースより

[入力例]
3 2

[出力例]
0
2
1

[入力例]
5 3

[出力例]
0
4
14
8
1

[入力例]
10 5

[出力例]
0
16
1280
9080
16944
12052
3840
580
40
1

[入力例]
27 18

[出力例]
0
131072
117687007
561668248
333765796
944219615
413145914
25234252
844291551
147820601
415647094
502074964
742578391
643588001
224531504
645569485
719396402
321847628
67809364
337380247
323011383
410215
298122147
4848666
52686
342
1

100

101

102

103

104

105

106

107

108

109

110

111

112

[入力例]

4 2

[出力例]

※AtCoderテストケースより

[入力例]

6 6

[出力例]

※AtCoderテストケースより

[入力例]

20 5

[出力例]

331776

207028224

204931064

814022582

544352515

755619435

401403040

323173195

538468102

309259764

722947327

162115584

10228144

423360

10960

160

※AtCoderテストケースより

[入力例]

3 2

[出力例]

[入力例]

5 3

[出力例]

[入力例]

10 5

[出力例]

1280

9080

16944

12052

3840

580

[入力例]

27 18

[出力例]

131072

117687007

561668248

333765796

944219615

413145914

25234252

844291551

147820601

415647094

502074964

742578391

643588001

224531504

645569485

719396402

321847628

67809364

337380247

323011383

410215

298122147

4848666

52686

342

■参照サイト
AtCoder Beginner Contest 217

2021年9月23日2021年9月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 126 の問題A (Make 10) ～問題B (Cross-free Matching) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. クエリ回答.
    rep(i, T){
        LL N2, N3, N4;
        scanf("%lld %lld %lld", &N2, &N3, &N4);
        
        // 長さ 10 の 棒 を 作成.
        // 長さ 3 の 棒が, 1本余る可能性あるが, 無視.
        LL ans= 0;
        LL n3 = N3 / 2;
        if(n3 <= N4){
            // (3, 3, 4)
            ans += n3;
            N4 -= n3;
            
            // (2, 4, 4)
            LL n4 = N4 / 2;
            LL n24 = min(N2, n4);
            ans += n24;
            N2 -= n24;
            
            // (2, 2, 2, 4)
            if(N4 != n4 * 2){
                if(N2 >= 3){
                    ans++;
                    N2 -= 3;
                }
            }
            
            // (2, 2, 2, 2, 2)
            LL n2 = N2 / 5;
            ans += n2;
        }else{
            // (3, 3, 4)
            ans += N4;
            N3 -= N4 * 2;
            
            // (3, 3, 2, 2)
            LL n23 = min(N2, N3) / 2;
            ans += n23;
            N2 -= n23 * 2;
            N3 -= n23 * 2;
            
            // (2, 2, 2, 2, 2)
            LL n2 = N2 / 5;
            ans += n2;
        }
        
        // 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. クエリ回答.

rep(i, T){

LL N2, N3, N4;

scanf("%lld %lld %lld", &N2, &N3, &N4);

// 長さ 10 の棒を作成.

// 長さ 3 の棒が, 1本余る可能性あるが, 無視.

LL ans= 0;

LL n3 = N3 / 2;

if(n3 <= N4){

// (3, 3, 4)

ans += n3;

N4 -= n3;

// (2, 4, 4)

LL n4 = N4 / 2;

LL n24 = min(N2, n4);

ans += n24;

N2 -= n24;

// (2, 2, 2, 4)

if(N4 != n4 * 2){

if(N2 >= 3){

ans++;

N2 -= 3;

}

// (2, 2, 2, 2, 2)

LL n2 = N2 / 5;

ans += n2;

}else{

// (3, 3, 4)

ans += N4;

N3 -= N4 * 2;

// (3, 3, 2, 2)

LL n23 = min(N2, N3) / 2;

ans += n23;

N2 -= n23 * 2;

N3 -= n23 * 2;

// (2, 2, 2, 2, 2)

LL n2 = N2 / 5;

ans += n2;

}

// 出力.

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

}

return 0;

}

[入力例]
5
3 4 1
7 0 0
0 0 7
0 0 0
1000000000000000 1000000000000000 1000000000000000

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

[入力例]
20
36 112 72
92 61 67
59 59 72
63 4 103
103 63 4
119 96 74
30 112 96
98 61 1
33 3 82
34 77 20
71 109 14
40 52 15
89 0 15
3 84 98
95 41 6
3 24 4
62 113 3
117 23 62
67 27 97
23 102 113

[出力例]
69
63
58
55
40
82
78
38
34
37
49
29
23
45
33
5
34
54
60
74

[入力例]
30
5321 7661 6793
4132 7399 8201
6164 11064 2291
11945 7434 3588
11106 797 12089
1298 7596 9460
11423 11121 4504
8614 7146 11395
6482 7458 7156
5325 5719 285
9070 2202 8960
12194 3869 8798
4770 8479 7498
12099 2499 8485
2690 10112 9743
2595 11087 1936
599 3992 1408
3370 6874 5128
10216 11395 1709
8586 7213 11453
3617 1863 11294
9373 6187 6843
2626 11253 9954
6650 1357 10072
7673 9727 3941
3705 1164 194
70 5032 4508
8848 6466 2153
4381 4286 4640
3875 3967 6781

[出力例]
6079
6326
5373
6054
7295
5096
7422
8424
6396
2894
6058
7118
6496
6563
7468
3233
1707
4787
6145
8462
4548
6467
7882
5765
6028
1167
2586
4570
4018
4677

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

[入力例]

3 4 1

7 0 0

0 0 7

0 0 0

1000000000000000 1000000000000000 1000000000000000

[出力例]

900000000000000

※AtCoderのテストケースより

[入力例]

36 112 72

92 61 67

59 59 72

63 4 103

103 63 4

119 96 74

30 112 96

98 61 1

33 3 82

34 77 20

71 109 14

40 52 15

89 0 15

3 84 98

95 41 6

3 24 4

62 113 3

117 23 62

67 27 97

23 102 113

[出力例]

[入力例]

5321 7661 6793

4132 7399 8201

6164 11064 2291

11945 7434 3588

11106 797 12089

1298 7596 9460

11423 11121 4504

8614 7146 11395

6482 7458 7156

5325 5719 285

9070 2202 8960

12194 3869 8798

4770 8479 7498

12099 2499 8485

2690 10112 9743

2595 11087 1936

599 3992 1408

3370 6874 5128

10216 11395 1709

8586 7213 11453

3617 1863 11294

9373 6187 6843

2626 11253 9954

6650 1357 10072

7673 9727 3941

3705 1164 194

70 5032 4508

8848 6466 2153

4381 4286 4640

3875 3967 6781

[出力例]

6079

6326

5373

6054

7295

5096

7422

8424

6396

2894

6058

7118

6496

6563

7468

3233

1707

4787

6145

8462

4548

6467

7882

5765

6028

1167

2586

4570

4018

4677

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

// 解き直し.
// https://atcoder.jp/contests/arc126/editorial/2626
// 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
#define all(x) x.begin(), x.end()

struct line{
    int a, b; // 座標 a, b.
    bool operator < (const line& rhs) const{
        return (a == rhs.a) ? (b > rhs.b) : (a < rhs.a);
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vector<line> v;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        line l;
        l.a = a;
        l.b = b;
        v.pb(l);
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. 狭義単調増加な数列の長さの最大値は？
    // 以下の問題を参照.
    // https://atcoder.jp/contests/typical90/tasks/typical90_bh
    // -> LIS(Longest increase subsequence) を 利用.
    vi dp;
    rep(i, M){
        // 数列を保存.
        line l = v[i];
        if(dp.size() == 0 || dp.back() < l.b){
            dp.pb(l.b);
        }else{
            int at = lower_bound(all(dp), l.b) - dp.begin();
            dp[at] = l.b;
        }
    }
    // rep(i, dp.size()) printf("%d\n", dp[i]);
    
    // 4. 出力.
    printf("%d\n", dp.size());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc126/editorial/2626

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

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

struct line{

int a, b; // 座標 a, b.

bool operator < (const line& rhs) const{

return (a == rhs.a) ? (b > rhs.b) : (a < rhs.a);

}

};

int main(){

// 1. 入力情報.

int N, M;

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

vector<line> v;

rep(i, M){

int a, b;

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

line l;

l.a = a;

l.b = b;

v.pb(l);

}

// 2. sort.

sort(all(v));

// 3. 狭義単調増加な数列の長さの最大値は？

// 以下の問題を参照.

// https://atcoder.jp/contests/typical90/tasks/typical90_bh

// -> LIS(Longest increase subsequence) を利用.

vi dp;

rep(i, M){

// 数列を保存.

line l = v[i];

if(dp.size() == 0 || dp.back() < l.b){

dp.pb(l.b);

}else{

int at = lower_bound(all(dp), l.b) - dp.begin();

dp[at] = l.b;

}

// rep(i, dp.size()) printf("%d\n", dp[i]);

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

[入力例]
1 1
1 1

[出力例]
1

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

[出力例]
3

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

[出力例]
6

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

[出力例]
6

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

[出力例]
10

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

[入力例]

3 3

1 2

2 3

3 1

[出力例]

※AtCoderのテストケースより

[入力例]

3 5

1 1

2 1

2 2

3 2

3 3

[出力例]

※AtCoderのテストケースより

[入力例]

7 5

1 7

7 1

3 4

2 6

5 2

[出力例]

※AtCoderのテストケースより

[入力例]

1 1

[出力例]

[入力例]

5 6

1 3

4 1

4 5

5 3

3 2

3 4

[出力例]

[入力例]

8 15

2 1

2 3

3 4

3 2

1 1

4 4

4 5

5 7

5 4

5 8

6 5

6 6

7 6

7 8

8 8

[出力例]

[入力例]

15 20

9 8

1 3

5 4

10 1

10 11

7 7

9 7

4 2

8 14

7 14

5 12

8 11

10 13

15 14

2 10

13 8

4 11

12 4

2 12

5 3

[出力例]

[入力例]

25 50

25 16

6 19

22 14

10 21

6 20

7 20

12 3

8 13

19 23

13 21

8 16

1 22

4 1

14 18

11 9

23 2

13 19

4 10

5 7

1 15

24 1

5 11

3 10

5 4

15 20

17 22

24 16

25 11

10 15

7 6

14 16

8 11

11 13

6 7

15 8

6 9

6 18

8 25

15 12

14 7

16 2

22 6

3 13

10 10

20 4

16 23

9 10

16 20

5 12

12 14

[出力例]

■参照サイト
AtCoder Regular Contest 126
060 – Chimera

C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題H (Red and Blue Lamps) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 127 の 問題C (Binary Strings) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 127 の 問題A (Leading 1s) ～ 問題B (Ternary Strings) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の 問題G (Isosceles Trapezium) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の 問題F (Distance Sums 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の 問題E (Distance on Large Perfect Binary Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の 問題C (Long Sequence) ～ 問題D (FG operation) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Regular Contest 126 の 問題A (Make 10) ～ 問題B (Cross-free Matching) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題H (Red and Blue Lamps) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 127 の問題C (Binary Strings) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 127 の問題A (Leading 1s) ～問題B (Ternary Strings) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題G (Isosceles Trapezium) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題F (Distance Sums 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題E (Distance on Large Perfect Binary Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題C (Long Sequence) ～問題D (FG operation) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Regular Contest 126 の問題A (Make 10) ～問題B (Cross-free Matching) を解いてみた.