C++ | 個人用メモ帳

2021年7月9日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題016 (Minimum Coins) を解いてみた.

■感想.
1. 実装方針を決めることができたので, AC版に到達出来たと思う.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題016 をご覧下さい.

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

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

int main(){
    
    // 1. 入力情報.
    LL N, coin[3];
    scanf("%lld %lld %lld %lld", &N, &coin[0], &coin[1], &coin[2]);
    
    // 2. sort.
    sort(coin, coin + 3);
    
    // 3. 硬貨枚数を計算.
    int ans = 10000;
    // ex.
    // 15円 を 1, 5, 8円で支払う場合, 
    // 1, 1, 5, 8 とすると, 4枚.
    // 5, 5, 5    とすると, 3枚.
    // のように, 硬貨枚数が変化することに注意.
    repr(c, 9999, 0){
        // 金額がオーバーする場合.
        LL mc = coin[2] * c;
        if(mc > N) continue;
        
        // ぴったりの場合.
        if(mc == N) ans = min(ans, c);
        
        // 不足する場合.
        if(mc < N){
            LL mab = N - mc;
            if(mab / coin[1] > 9999) continue;
            int bMax = (int)(mab / coin[1]);
            repr(b, bMax, 0){
                LL ma = mab - coin[1] * b;
                int a = (int)(ma / coin[0]);
                if(ma % coin[0] == 0){
                    ans = min(ans, a + b + c);
                    break;
                }
            }
        }
    }
    
    // 4. 出力.
    assert(ans != 10000);
    printf("%d\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. 入力情報.

LL N, coin[3];

scanf("%lld %lld %lld %lld", &N, &coin[0], &coin[1], &coin[2]);

// 2. sort.

sort(coin, coin + 3);

// 3. 硬貨枚数を計算.

int ans = 10000;

// ex.

// 15円を 1, 5, 8円で支払う場合,

// 1, 1, 5, 8 とすると, 4枚.

// 5, 5, 5 とすると, 3枚.

// のように, 硬貨枚数が変化することに注意.

repr(c, 9999, 0){

// 金額がオーバーする場合.

LL mc = coin[2] * c;

if(mc > N) continue;

// ぴったりの場合.

if(mc == N) ans = min(ans, c);

// 不足する場合.

if(mc < N){

LL mab = N - mc;

if(mab / coin[1] > 9999) continue;

int bMax = (int)(mab / coin[1]);

repr(b, bMax, 0){

LL ma = mab - coin[1] * b;

int a = (int)(ma / coin[0]);

if(ma % coin[0] == 0){

ans = min(ans, a + b + c);

break;

}

// 4. 出力.

assert(ans != 10000);

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

return 0;

}

[入力例]
227
21 47 56

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

[入力例]
9999
1 5 10

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

[入力例]
998244353
314159 265358 97932

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

[入力例]
100000000
10001 10002 10003

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

[入力例]
1000000000
314159 265358 97932

[出力例]
3527

[入力例]
987654321
14142 135623 73095

[出力例]
7405

[入力例]

227

21 47 56

[出力例]

※AtCoderテストケースより

[入力例]

9999

1 5 10

[出力例]

1004

※AtCoderテストケースより

[入力例]

998244353

314159 265358 97932

[出力例]

3333

※AtCoderテストケースより

[入力例]

100000000

10001 10002 10003

[出力例]

9998

※AtCoderテストケースより

[入力例]

1000000000

314159 265358 97932

[出力例]

3527

[入力例]

987654321

14142 135623 73095

[出力例]

7405

■参照サイト
016 – Minimum Coins

2021年7月7日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題030 (K Factors) を解いてみた.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題030 をご覧下さい.

■C++版プログラム(問題030／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[30303030];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 倍数を保存.
    repx(i, 2, N + 1){
        if(a[i]) continue;
        repex(j, i, N + 1, i) a[j]++;
    }
    
    // 3. K種類以上をカウント.
    int ans = 0;
    rep(i, N + 1) if(a[i] >= K) ans++;
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int a[30303030];

int main(){

// 1. 入力情報.

int N, K;

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

// 2. 倍数を保存.

repx(i, 2, N + 1){

if(a[i]) continue;

repex(j, i, N + 1, i) a[j]++;

}

// 3. K種類以上をカウント.

int ans = 0;

rep(i, N + 1) if(a[i] >= K) ans++;

// 4. 出力.

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

return 0;

}

[入力例]
15 2

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

[入力例]
30 2

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

[入力例]
200 4

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

[入力例]
869120 1

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

[入力例]
10000000 3

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

[入力例]
2021 4

[出力例]
83

[入力例]
20210707 3

[出力例]
13978430
※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]
20210711 8

[出力例]
11
※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]

15 2

[出力例]

※AtCoderテストケースより

[入力例]

30 2

[出力例]

※AtCoderテストケースより

[入力例]

200 4

[出力例]

※AtCoderテストケースより

[入力例]

869120 1

[出力例]

869119

※AtCoderテストケースより

[入力例]

10000000 3

[出力例]

6798027

※AtCoderテストケースより

[入力例]

2021 4

[出力例]

[入力例]

20210707 3

[出力例]

13978430

※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]

20210711 8

[出力例]

※整数 N が, 問題文の制約条件から範囲外であるケース.

■参照サイト
030 – K Factors

2021年7月4日

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

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

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 実装に苦労したものの, 二分探索の復習が出来たので良かったと思う.
3. Binary Indexed Tree の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Regular Contest 101 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/arc101/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--)
int a[101010];

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1){
        for(i++; i <= n; i += i & -i) d[i] += x;
    }
    T sum(int i){
        T x = 0;
        for(i++; i; i -= i & -i) x += d[i];
        return x;
    }
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }
};

int main(){
    
    // 1. 入力情報.
    int N, l = 2020202020, h = 0, m;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a[i]);
        h = max(h, a[i]);
        l = min(l, a[i]);
    }
    h++;
    l--;
    
    // 2. 最終的な中央値となるための判定条件(要素数).
    LL M = (LL)(N + 1) * (LL)N / 2;
    if(M & 1) M++;
    M /= 2;
    
    // 3. 評価関数.
    auto f = [&](int x) -> bool {
        // 3-1. x以上か？
        int b[N];
        rep(i, N) b[i] = (a[i] >= x) ? 1 : -1;
        
        // 3-2. 数列 S の 計算.
        int S[N + 1];
        S[0] = 0;
        int ms = N + 1;
        rep(i, N){
            S[i + 1] = S[i] + b[i];
            ms = min(ms, S[i + 1]);
        }
        
        // 3-3. Binary Indexed Tree に 数列 S を 反映.
        if(ms <= 0) rep(i, N + 1) S[i] += (1 - ms);
        BIT<LL> ft(N + 1);
        rep(i, N + 1) ft.add(S[i], 1LL);
        
        // 3-4. 数列 S に含まれる S[l] <= S[r] を 満たすものの個数.
        LL sCount = 0;
        rep(i, N){
            // 場所 S[i] に, -1 を 加算.
            ft.add(S[i], -1LL);
            
            // 区間[S[i], N] の 合計は？
            LL t = ft.sum(S[i], N + 1);
            
            // 集計.
            sCount += t;
        }
        
        // 3-5. 評価.
        return (sCount < M);
    };
    
    // 4. 二分探索.
    while(l + 1 < h){
        m = (h + l) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    
    // 5. 出力.
    printf("%d\n", l);
    return 0;
    
}

100

// 解き直し.

// https://img.atcoder.jp/arc101/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--)

int a[101010];

// Binary Indexed Tree (Fenwick Tree)

// https://youtu.be/lyHk98daDJo?t=7960

template<typename T>

struct BIT{

int n;

vector<T> d;

BIT(int n = 0) : n(n), d(n + 1) {}

void add(int i, T x = 1){

for(i++; i <= n; i += i & -i) d[i] += x;

}

T sum(int i){

T x = 0;

for(i++; i; i -= i & -i) x += d[i];

return x;

}

T sum(int l, int r){

return sum(r - 1) - sum(l - 1);

}

};

int main(){

// 1. 入力情報.

int N, l = 2020202020, h = 0, m;

scanf("%d", &N);

rep(i, N){

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

h = max(h, a[i]);

l = min(l, a[i]);

}

h++;

l--;

// 2. 最終的な中央値となるための判定条件(要素数).

LL M = (LL)(N + 1) * (LL)N / 2;

if(M & 1) M++;

M /= 2;

// 3. 評価関数.

auto f = [&](int x) -> bool {

// 3-1. x以上か？

int b[N];

rep(i, N) b[i] = (a[i] >= x) ? 1 : -1;

// 3-2. 数列 S の計算.

int S[N + 1];

S[0] = 0;

int ms = N + 1;

rep(i, N){

S[i + 1] = S[i] + b[i];

ms = min(ms, S[i + 1]);

}

// 3-3. Binary Indexed Tree に数列 S を反映.

if(ms <= 0) rep(i, N + 1) S[i] += (1 - ms);

BIT<LL> ft(N + 1);

rep(i, N + 1) ft.add(S[i], 1LL);

// 3-4. 数列 S に含まれる S[l] <= S[r] を満たすものの個数.

LL sCount = 0;

rep(i, N){

// 場所 S[i] に, -1 を加算.

ft.add(S[i], -1LL);

// 区間[S[i], N] の合計は？

LL t = ft.sum(S[i], N + 1);

// 集計.

sCount += t;

}

// 3-5. 評価.

return (sCount < M);

};

// 4. 二分探索.

while(l + 1 < h){

m = (h + l) >> 1;

if(f(m)) h = m;

else l = m;

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

}

// 5. 出力.

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

return 0;

}

[入力例]
3
10 30 20

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

[入力例]
1
10

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

[入力例]
10
5 9 5 9 8 9 3 5 4 3

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

[入力例]
5
23 8 17 5 13

[出力例]
13

[入力例]
31
41 5 92 65 3 58 97 93 2 38 4 62 64 33 8 32 79 50 28 84 19 71 6 93 99 3 75 10 5 8 20

[出力例]
50

[入力例]
100
63238 103570 37988 54487 72815 11268 99987 23767 75684 9483 16587 64526 91308 41419 27171 53793 40890 3019 37663 103430 107127 40161 111213 64334 105258 35467 116942 47020 46193 99908 66262 43053 42826 10527 108301 109763 109706 110549 57321 10236 53967 69000 22892 94994 21748 13803 36276 96104 102159 38938 107343 18714 122886 72001 113446 51043 82827 63066 52429 20403 104493 42038 42109 123184 18246 74697 24944 18185 89514 10062 95471 3832 102967 12473 55945 92535 45840 95311 20546 104868 84779 91707 104311 27314 90949 10139 46205 109686 75876 49978 107111 90053 21028 43572 79102 119240 36299 23423 105790 106975

[出力例]
57321

[入力例]

10 30 20

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

5 9 5 9 8 9 3 5 4 3

[出力例]

※AtCoderのテストケースより

[入力例]

23 8 17 5 13

[出力例]

[入力例]

41 5 92 65 3 58 97 93 2 38 4 62 64 33 8 32 79 50 28 84 19 71 6 93 99 3 75 10 5 8 20

[出力例]

[入力例]

100

63238 103570 37988 54487 72815 11268 99987 23767 75684 9483 16587 64526 91308 41419 27171 53793 40890 3019 37663 103430 107127 40161 111213 64334 105258 35467 116942 47020 46193 99908 66262 43053 42826 10527 108301 109763 109706 110549 57321 10236 53967 69000 22892 94994 21748 13803 36276 96104 102159 38938 107343 18714 122886 72001 113446 51043 82827 63066 52429 20403 104493 42038 42109 123184 18246 74697 24944 18185 89514 10062 95471 3832 102967 12473 55945 92535 45840 95311 20546 104868 84779 91707 104311 27314 90949 10139 46205 109686 75876 49978 107111 90053 21028 43572 79102 119240 36299 23423 105790 106975

[出力例]

57321

■参照サイト
AtCoder Regular Contest 101
Binary Indexed Tree (Fenwick Tree)

2021年7月3日2021年7月3日

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

C++の練習を兼ねて, AtCoder Regular Contest 100 の問題E (Or Plus Max) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 問題Eで, 高速ゼータ変換に関する考え方に触れることが出来たので, 非常に良かったと思う.
3. 実装に苦労したものの, 個人的には, 上位二個の要素を更新していくロジックが, 非常に面白いと感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Regular Contest 100 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/arc100/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using PQ = priority_queue<P>;
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
#define all(x) x.begin(), x.end()
P a[303030];
PQ pq[303030];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, 1 << N){
        int t;
        scanf("%d", &t);
        a[i].a = t;
        a[i].b = i;
        pq[i].push(a[i]);
    }
    
    // 2. 上位二桁更新.
    rep(i, 1 << N){
        rep(j, N){
            // 2-1. j ビット目が, 1 の 場合は, 更新対象外.
            int bit = 1 << j;
            if(i & bit) continue;
            
            // 2-2. 更新対称 の 位置 を 取得.
            int ni = i + bit;
            
            // 2-3. ni 番目 の 要素 に, i番目 の 要素を全て追加.
            // -> i 番目 の 要素 を コピーしてから実施.
            PQ cPQ = pq[i];
            while(!cPQ.empty()){
                P u = cPQ.top();
                cPQ.pop();
                pq[ni].push(u);
            }
            
            // 2-4. 重複要素削除.
            // -> i 番目 の 要素 を 追加すると, ダブルカウントしている場合があるので, 重複削除.
            set<P> st;
            while(!pq[ni].empty()){
                P u = pq[ni].top();
                pq[ni].pop();
                st.insert(u);
            }
            
            // 2-5. ni 番目の要素数が, 二個になるように調整.
            while(!pq[ni].empty()) pq[ni].pop();
            vp v;
            for(auto &p : st) v.pb(p);
            reverse(all(v));
            assert(v.size() >= 2);
            pq[ni].push(v[0]);
            pq[ni].push(v[1]);
        }
    }
    
    // 3. 累積max ～ 出力.
    int ans = 0;
    repx(i, 1, 1 << N){
        // 3-1. i番目の要素を取得.
        int t = pq[i].top().a;
        pq[i].pop();
        t += pq[i].top().a;
        
        // 3-2. 累積max更新.
        ans = max(ans, t);
        
        // 3-3. 出力.
        printf("%d\n", ans);
    }
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using PQ = priority_queue<P>;

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

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

P a[303030];

PQ pq[303030];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, 1 << N){

int t;

scanf("%d", &t);

a[i].a = t;

a[i].b = i;

pq[i].push(a[i]);

}

// 2. 上位二桁更新.

rep(i, 1 << N){

rep(j, N){

// 2-1. j ビット目が, 1 の場合は, 更新対象外.

int bit = 1 << j;

if(i & bit) continue;

// 2-2. 更新対称の位置を取得.

int ni = i + bit;

// 2-3. ni 番目の要素に, i番目の要素を全て追加.

// -> i 番目の要素をコピーしてから実施.

PQ cPQ = pq[i];

while(!cPQ.empty()){

P u = cPQ.top();

cPQ.pop();

pq[ni].push(u);

}

// 2-4. 重複要素削除.

// -> i 番目の要素を追加すると, ダブルカウントしている場合があるので, 重複削除.

set<P> st;

while(!pq[ni].empty()){

P u = pq[ni].top();

pq[ni].pop();

st.insert(u);

}

// 2-5. ni 番目の要素数が, 二個になるように調整.

while(!pq[ni].empty()) pq[ni].pop();

vp v;

for(auto &p : st) v.pb(p);

reverse(all(v));

assert(v.size() >= 2);

pq[ni].push(v[0]);

pq[ni].push(v[1]);

}

// 3. 累積max ～出力.

int ans = 0;

repx(i, 1, 1 << N){

// 3-1. i番目の要素を取得.

int t = pq[i].top().a;

pq[i].pop();

t += pq[i].top().a;

// 3-2. 累積max更新.

ans = max(ans, t);

// 3-3. 出力.

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

}

return 0;

}

[入力例]
2
1 2 3 1

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

[入力例]
3
10 71 84 33 6 47 23 25

[出力例]
81
94
155
155
155
155
155
※AtCoderテストケースより

[入力例]
4
75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32

[出力例]
101
120
147
156
156
178
194
194
194
194
194
194
194
194
194
※AtCoderテストケースより

[入力例]
5
96 64 33 40 80 30 121 72 93 15 1 65 75 16 8 80 118 52 51 2 84 7 100 75 116 122 64 16 29 31 80 50

[出力例]
160
160
160
176
176
217
217
217
217
217
217
217
217
217
217
217
217
217
217
217
217
239
239
239
240
240
240
240
240
240
243

[入力例]
6
801 583 932 1190 85 653 62 420 598 31 896 1153 1127 1203 780 664 283 325 1079 74 702 1123 188 263 136 216 591 3 1232 699 510 1032 1154 694 59 362 804 527 73 997 150 1196 1076 1036 999 633 438 1055 349 549 277 197 1078 608 155 606 864 516 158 653 1073 393 1002 306

[出力例]
1384
1733
2122
2122
2122
2122
2122
2122
2122
2122
2343
2343
2343
2343
2393
2393
2393
2393
2393
2393
2393
2393
2393
2393
2393
2393
2393
2393
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435
2435

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

[入力例]

1 2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

10 71 84 33 6 47 23 25

[出力例]

155

※AtCoderテストケースより

[入力例]

75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32

[出力例]

101

120

147

156

178

194

※AtCoderテストケースより

[入力例]

96 64 33 40 80 30 121 72 93 15 1 65 75 16 8 80 118 52 51 2 84 7 100 75 116 122 64 16 29 31 80 50

[出力例]

160

176

217

239

240

243

[入力例]

801 583 932 1190 85 653 62 420 598 31 896 1153 1127 1203 780 664 283 325 1079 74 702 1123 188 263 136 216 591 3 1232 699 510 1032 1154 694 59 362 804 527 73 997 150 1196 1076 1036 999 633 438 1055 349 549 277 197 1078 608 155 606 864 516 158 653 1073 393 1002 306

[出力例]

1384

1733

2122

2343

2393

2435

■参照サイト
AtCoder Regular Contest 100

2021年7月1日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題021 (Come Back in One Piece) を解いてみた.

■感想.
1. 実装方針を決めることができたこと, および, 過去問の実装を参照できたので, AC版に到達出来たと思う.
2. 強連結成分分解(Strongly Connected Component)について, 理解を深めることが出来たので, 非常に良かったと思う.
3. 問題021は, 過去問 AtCoder Beginner Contest 202 (E – Count Descendants) を一部拝借する形で, 実装に反映した.
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題021 をご覧下さい.

■C++版プログラム(問題021／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>;
using P = pair<int, 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
#define pb push_back
int memo[101010], t[101010], scc[101010];
LL gCount[101010];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G1(N), G2(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G1[a].pb(b); // 有向辺.
        G2[b].pb(a); // 有向辺(逆向き).
    }
    
    // 強連結成分分解(Strongly Connected Component).
    // https://manabitimes.jp/math/1250
    // 2. 行き止まりの順番を保存.
    int idx = 0;
    PQ pq;
    auto dfs1 = [&](auto&& self, int c) -> void{
        // 訪問済フラグ設定.
        memo[c] = 1;
        
        // 取り出した要素を処理.
        for(auto &n : G1[c]) if(!memo[n]) self(self, n);
        
        // 行き止まりの順番を保存.
        pq.push({++idx, c});
    };
    rep(i, N) if(!memo[i]) dfs1(dfs1, i);
    
    // 3. 強連結成分に分解.
    idx = 0;
    auto dfs2 = [&](auto&& self, int c) -> void{
        // 連結成分番号設定.
        scc[c] = idx;
        
        // 取り出した要素を処理.
        for(auto &n : G2[c]) if(!scc[n]) self(self, n);
    };
    while(!pq.empty()){
        // 要素を取り出す.
        P p = pq.top();
        pq.pop();
        
        // 連結成分番号が設定済み.
        if(scc[p.b]) continue;
        
        // インクリメント.
        idx++;
        
        // 連結成分番号設定.
        dfs2(dfs2, p.b);
    }
    
    // 4. 各強連結成分の大きさを保存.
    rep(i, N) gCount[scc[i]]++;
    
    // 5. 集計.
    LL ans = 0;
    repx(i, 1, idx + 1) ans += gCount[i] * (gCount[i] - 1) / 2;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

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

#define pb push_back

int memo[101010], t[101010], scc[101010];

LL gCount[101010];

int main(){

// 1. 入力情報.

int N, M;

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

vvi G1(N), G2(N);

rep(i, M){

int a, b;

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

a--, b--;

G1[a].pb(b); // 有向辺.

G2[b].pb(a); // 有向辺(逆向き).

}

// 強連結成分分解(Strongly Connected Component).

// https://manabitimes.jp/math/1250

// 2. 行き止まりの順番を保存.

int idx = 0;

PQ pq;

auto dfs1 = [&](auto&& self, int c) -> void{

// 訪問済フラグ設定.

memo[c] = 1;

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

for(auto &n : G1[c]) if(!memo[n]) self(self, n);

// 行き止まりの順番を保存.

pq.push({++idx, c});

};

rep(i, N) if(!memo[i]) dfs1(dfs1, i);

// 3. 強連結成分に分解.

idx = 0;

auto dfs2 = [&](auto&& self, int c) -> void{

// 連結成分番号設定.

scc[c] = idx;

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

for(auto &n : G2[c]) if(!scc[n]) self(self, n);

};

while(!pq.empty()){

// 要素を取り出す.

P p = pq.top();

pq.pop();

// 連結成分番号が設定済み.

if(scc[p.b]) continue;

// インクリメント.

idx++;

// 連結成分番号設定.

dfs2(dfs2, p.b);

}

// 4. 各強連結成分の大きさを保存.

rep(i, N) gCount[scc[i]]++;

// 5. 集計.

LL ans = 0;

repx(i, 1, idx + 1) ans += gCount[i] * (gCount[i] - 1) / 2;

// 6. 出力.

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

return 0;

}

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

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

[入力例]
100 1
1 2

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

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

[出力例]
4

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

[出力例]
20

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

[出力例]
13

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

[出力例]
51

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

[入力例]

4 7

1 2

2 1

2 3

4 3

4 1

1 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

100 1

1 2

[出力例]

※AtCoderテストケースより

[入力例]

9 11

1 2

2 1

2 9

2 3

3 6

6 7

7 8

8 6

3 4

4 5

3 5

[出力例]

[入力例]

12 18

1 2

2 1

5 1

2 3

4 2

3 8

3 4

4 6

4 7

4 5

8 11

11 12

12 8

8 9

9 10

10 8

[出力例]

[入力例]

17 21

1 2

2 3

4 1

4 3

8 4

3 8

10 8

10 11

11 12

8 12

9 12

7 9

9 13

5 7

6 5

7 6

14 13

16 14

16 15

15 13

17 13

[出力例]

[入力例]

23 38

1 3

3 1

3 2

2 4

3 16

16 17

17 18

18 17

3 18

4 6

6 4

1 5

5 1

5 6

5 19

20 5

19 20

19 21

21 22

22 23

23 22

23 19

6 7

7 9

8 7

8 9

9 10

10 11

11 9

11 15

15 11

10 12

12 10

12 13

13 14

14 13

14 15

[出力例]

■参照サイト
021 – Come Back in One Piece
強連結成分分解の意味とアルゴリズム

2021年6月30日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題042 (Multiple of 9) を解いてみた.

■感想.
1. 動的計画法の方針で, 規則性を抽出できたので, AC版に到達出来たと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題042 をご覧下さい.

■C++版プログラム(問題042／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 dp[101010][10]; // {各桁の和, 1の位}

int main(){
    
    // 1. 入力情報.
    int K;
    scanf("%d", &K);
    
    // 2. 例外ケース.
    if(K % 9 != 0){
        puts("0");
        return 0;
    }
    
    // 3. 通常ケース.
    rep(i, 10) dp[i][i] = 1;
    repx(i, 2, 100000){
        // 3-1. 各桁の和(i) に対して, 1の位(j) を, すべて見る.
        repx(j, 1, 10){
            // 3-2. 各桁の和は, 1の位以上であるはず.
            int b = i - j;
            if(b >= 0){
                // 3-3. 各桁の和(b)のパターンを集計.
                LL dx = 0;
                repx(k, 1, 10){
                    dx += dp[b][k];
                    dx %= MOD;
                }
                
                // 3-4. dp更新.
                dp[i][j] += dx;
                dp[i][j] %= MOD;
            }
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    repx(j, 1, 10) ans += dp[K][j], ans %= MOD;
    
    // 5. 出力.
    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 dp[101010][10]; // {各桁の和, 1の位}

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

// 2. 例外ケース.

if(K % 9 != 0){

puts("0");

return 0;

}

// 3. 通常ケース.

rep(i, 10) dp[i][i] = 1;

repx(i, 2, 100000){

// 3-1. 各桁の和(i) に対して, 1の位(j) を, すべて見る.

repx(j, 1, 10){

// 3-2. 各桁の和は, 1の位以上であるはず.

int b = i - j;

if(b >= 0){

// 3-3. 各桁の和(b)のパターンを集計.

LL dx = 0;

repx(k, 1, 10){

dx += dp[b][k];

dx %= MOD;

}

// 3-4. dp更新.

dp[i][j] += dx;

dp[i][j] %= MOD;

}

// 4. 集計.

LL ans = 0;

repx(j, 1, 10) ans += dp[K][j], ans %= MOD;

// 5. 出力.

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

return 0;

}

[入力例]
1

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

[入力例]
234

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

[入力例]
9

[出力例]
256

[入力例]
18

[出力例]
129792

[入力例]
2025

[出力例]
789912177

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

234

[出力例]

757186539

※AtCoderテストケースより

[入力例]

[出力例]

256

[入力例]

[出力例]

129792

[入力例]

2025

[出力例]

789912177

■参照サイト
042 – Multiple of 9

2021年6月25日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題051 (Typical Shop) を解いてみた.

■感想.
1. 問題051は, 過去問 AtCoder Beginner Contest 184 (Programming Contest)に類似した方針で解けそうと気付けたので, AC版に到達出来たと思う.
2. 半分全列挙の復習が出来たので良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題051 をご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vp = vector<pair<LL, int>>;
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
#define a first
#define b second
#define all(x) x.begin(), x.end()
LL a[44], gCum[1 << 21][22];

int main(){
    
    // 1. 入力情報.
    int N, K;
    LL P;
    scanf("%d %d %lld", &N, &K, &P);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 事前計算.
    int lCnt = N / 2, rCnt = N - lCnt;
    vp v;
    rep(i, 1 << rCnt){
        LL p = 0;
        rep(j, rCnt) if(i & (1 << j)) p += a[lCnt + j];
        v.pb({p, __builtin_popcount(i)}); // {値段の合計, 品物の選択数}.
    }
    
    // 3. sort.
    sort(all(v));
    
    // 4. 累積和.
    rep(i, v.size()){
        rep(j, 21) gCum[i + 1][j] = gCum[i][j];
        gCum[i + 1][v[i].b]++;
    }
    
    // 5. インデックス計算用.
    vl idxs;
    for(auto &p : v) idxs.pb(p.a);
    
    // 6. 集計.
    LL ans = 0;
    rep(i, 1 << lCnt){
        // 6-1. 左から l個, 右から r個 を 選択.
        int l = __builtin_popcount(i);
        int r = K - l;
        if(r > rCnt || r < 0) continue;
        
        // 6-2. 左から l個選択したときの値段の合計は？
        LL p = 0;
        rep(j, lCnt) if(i & (1 << j)) p += a[j];
        
        // 6-3. 値段の合計が, P円以下になるパターンは？
        int at = upper_bound(all(idxs), P - p) - idxs.begin();
        
        // 6-4. 加算.
        ans += gCum[at][r];
    }
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vp = vector<pair<LL, int>>;

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

#define a first

#define b second

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

LL a[44], gCum[1 << 21][22];

int main(){

// 1. 入力情報.

int N, K;

LL P;

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

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

// 2. 事前計算.

int lCnt = N / 2, rCnt = N - lCnt;

vp v;

rep(i, 1 << rCnt){

LL p = 0;

rep(j, rCnt) if(i & (1 << j)) p += a[lCnt + j];

v.pb({p, __builtin_popcount(i)}); // {値段の合計, 品物の選択数}.

}

// 3. sort.

sort(all(v));

// 4. 累積和.

rep(i, v.size()){

rep(j, 21) gCum[i + 1][j] = gCum[i][j];

gCum[i + 1][v[i].b]++;

}

// 5. インデックス計算用.

vl idxs;

for(auto &p : v) idxs.pb(p.a);

// 6. 集計.

LL ans = 0;

rep(i, 1 << lCnt){

// 6-1. 左から l個, 右から r個を選択.

int l = __builtin_popcount(i);

int r = K - l;

if(r > rCnt || r < 0) continue;

// 6-2. 左から l個選択したときの値段の合計は？

LL p = 0;

rep(j, lCnt) if(i & (1 << j)) p += a[j];

// 6-3. 値段の合計が, P円以下になるパターンは？

int at = upper_bound(all(idxs), P - p) - idxs.begin();

// 6-4. 加算.

ans += gCum[at][r];

}

// 7. 出力.

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

return 0;

}

[入力例]
5 2 10
3 8 7 5 11

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

[入力例]
5 1 10
7 7 7 7 7

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

[入力例]
40 20 100
1 3 1 3 4 1 3 5 5 3 3 4 1 5 4 4 3 1 3 4 1 3 2 4 4 1 5 2 5 3 1 3 3 3 5 5 5 2 3 5

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

[入力例]
10 3 2021
995 1053 40 877 790 164 389 480 712 284

[出力例]
83

[入力例]
20 15 20210625
514085 670779 73685 129574 5500 1074316 985537 683553 782370 1027170 337636 679081 543707 137884 676487 178211 503220 945119 1158968 1225005

[出力例]
15504

[入力例]
40 27 202107122100
808410568 331920903 1137252447 336354363 222223395 404816299 669779234 1170174052 505664701 199843683 626347986 548544963 1159677821 1167796776 142512466 561977437 1112050623 845111295 497654528 853809473 599682486 137743944 250218090 316303643 1213853118 712804419 868439455 966116317 1210969425 1028496444 184508051 765107727 731625464 185947863 31165189 426137200 677132796 376072355 603715221 478022957

[出力例]
12033222880

[入力例]

5 2 10

3 8 7 5 11

[出力例]

※AtCoderテストケースより

[入力例]

5 1 10

7 7 7 7 7

[出力例]

※AtCoderテストケースより

[入力例]

40 20 100

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

[出力例]

137846528820

※AtCoderテストケースより

[入力例]

10 3 2021

995 1053 40 877 790 164 389 480 712 284

[出力例]

[入力例]

20 15 20210625

514085 670779 73685 129574 5500 1074316 985537 683553 782370 1027170 337636 679081 543707 137884 676487 178211 503220 945119 1158968 1225005

[出力例]

15504

[入力例]

40 27 202107122100

808410568 331920903 1137252447 336354363 222223395 404816299 669779234 1170174052 505664701 199843683 626347986 548544963 1159677821 1167796776 142512466 561977437 1112050623 845111295 497654528 853809473 599682486 137743944 250218090 316303643 1213853118 712804419 868439455 966116317 1210969425 1028496444 184508051 765107727 731625464 185947863 31165189 426137200 677132796 376072355 603715221 478022957

[出力例]

12033222880

■参照サイト
051 – Typical Shop

2021年6月24日2021年6月24日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題056 (Lucky Bag) を解いてみた.

■感想.
1. 問題056は, 過去問 AtCoder Beginner Contest 204 (D – Cooking)に類似した方針で解けそうと気付けたので, AC版に到達出来たと思う.
2. 個人的には, 福袋の選択パターンを, 動的計画法を用いて, 計算量を削減出来る点が, 非常に面白いと感じた.
3. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題056 をご覧下さい.

■C++版プログラム(問題056／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
int a[111], b[111], d[111], dp[101010], cost[101010];

int main(){
    
    // 1. 入力情報.
    int N, S, tMin = 0, tMax = 0;
    scanf("%d %d", &N, &S);
    string ans = "";
    rep(i, N){
        scanf("%d %d", &a[i], &b[i]);
        if(a[i] <= b[i]) ans.pb('A');
        else             ans.pb('B');
        tMin += min(a[i], b[i]);
        tMax += max(a[i], b[i]);
        d[i] = abs(a[i] - b[i]);
    }
    
    // 2. NGパターン.
    if(S < tMin || S > tMax){
        puts("Impossible");
        return 0;
    }
    
    // 3. OKパターン.
    S -= tMin;
    if(S == 0){
        printf("%s\n", ans.c_str());
        return 0;
    }
    
    // 4. 福袋(金額差分) を 割り当てを探索.
    // -> 最小となる場合の福袋の割り当ては完了しているので, 
    //    福袋のいずれかを, 金額の大きい方に変更して, 
    //    S円とすることが出来るかをチェック.
    dp[0] = 1;
    rep(i, N){
        repr(j, S, 0){
            // i番目の福袋(金額差分)を考慮.
            int cur = d[i] + j;
            if(cur <= S && dp[j]){
                // dp更新.
                dp[cur] = 1;
                
                // 未訪問の場合, 福袋の番号を記録.
                if(!cost[cur]) cost[cur] = i + 1; // 1-index.
            }
        }
    }
    
    // 5. NGパターン.
    if(!cost[S]){
        puts("Impossible");
        return 0;
    }
    
    // 6. 福袋(金額差分) を 割り当てる.
    int cur = S;
    while(cur > 0){
        int idx = cost[cur] - 1; // 0-index.
        char c = ans[idx];
        ans[idx] = (c == 'B') ? 'A' : 'B';
        cur -= d[idx];
    }
    
    // 7. 出力.
    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

int a[111], b[111], d[111], dp[101010], cost[101010];

int main(){

// 1. 入力情報.

int N, S, tMin = 0, tMax = 0;

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

string ans = "";

rep(i, N){

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

if(a[i] <= b[i]) ans.pb('A');

else ans.pb('B');

tMin += min(a[i], b[i]);

tMax += max(a[i], b[i]);

d[i] = abs(a[i] - b[i]);

}

// 2. NGパターン.

if(S < tMin || S > tMax){

puts("Impossible");

return 0;

}

// 3. OKパターン.

S -= tMin;

if(S == 0){

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

return 0;

}

// 4. 福袋(金額差分) を割り当てを探索.

// -> 最小となる場合の福袋の割り当ては完了しているので,

// 福袋のいずれかを, 金額の大きい方に変更して,

// S円とすることが出来るかをチェック.

dp[0] = 1;

rep(i, N){

repr(j, S, 0){

// i番目の福袋(金額差分)を考慮.

int cur = d[i] + j;

if(cur <= S && dp[j]){

// dp更新.

dp[cur] = 1;

// 未訪問の場合, 福袋の番号を記録.

if(!cost[cur]) cost[cur] = i + 1; // 1-index.

}

// 5. NGパターン.

if(!cost[S]){

puts("Impossible");

return 0;

}

// 6. 福袋(金額差分) を割り当てる.

int cur = S;

while(cur > 0){

int idx = cost[cur] - 1; // 0-index.

char c = ans[idx];

ans[idx] = (c == 'B') ? 'A' : 'B';

cur -= d[idx];

}

// 7. 出力.

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

return 0;

}

[入力例]
3 34
3 14
15 9
26 5

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

[入力例]
5 77
1 16
3 91
43 9
4 26
23 11

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

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

[入力例]
5 59
8 13
55 5
58 8
23 14
4 61

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

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

[出力例]
AAA

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

[出力例]
BBBBB

[入力例]
10 543
110 44
94 93
31 22
15 79
49 70
50 28
79 104
23 51
11 112
79 110

[出力例]
ABAAABBAAA

[入力例]
15 2021
132 79
176 6
196 110
11 94
95 150
150 235
309 49
104 103
284 92
214 159
73 207
288 216
294 132
210 138
143 319

[出力例]
ABAAAABBABBBBBA

[入力例]
25 54321
1382 4941
2128 4730
1776 4176
3947 1801
5307 1004
4280 433
3821 3670
2846 561
1308 1481
4009 2258
2159 1647
379 1766
1237 2114
1778 165
5537 4890
4815 4662
2005 1702
3112 3967
1311 2497
52 1929
3137 4904
3088 3898
3697 5289
3842 4282
1843 4741

[出力例]
AABBBBABBBAAABBBBAAAAAAAA

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

[入力例]

3 34

3 14

15 9

26 5

[出力例]

BAB

※AtCoderテストケースより

[入力例]

5 77

1 16

3 91

43 9

4 26

23 11

[出力例]

BABBA

※AtCoderテストケースより

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

BAAAB

[入力例]

5 59

8 13

55 5

58 8

23 14

4 61

[出力例]

Impossible

※AtCoderテストケースより

[入力例]

3 15

2 7

5 6

8 10

[出力例]

AAA

[入力例]

5 39

2 12

5 6

8 9

1 5

3 7

[出力例]

BBBBB

[入力例]

10 543

110 44

94 93

31 22

15 79

49 70

50 28

79 104

23 51

11 112

79 110

[出力例]

ABAAABBAAA

[入力例]

15 2021

132 79

176 6

196 110

11 94

95 150

150 235

309 49

104 103

284 92

214 159

73 207

288 216

294 132

210 138

143 319

[出力例]

ABAAAABBABBBBBA

[入力例]

25 54321

1382 4941

2128 4730

1776 4176

3947 1801

5307 1004

4280 433

3821 3670

2846 561

1308 1481

4009 2258

2159 1647

379 1766

1237 2114

1778 165

5537 4890

4815 4662

2005 1702

3112 3967

1311 2497

52 1929

3137 4904

3088 3898

3697 5289

3842 4282

1843 4741

[出力例]

AABBBBABBBAAABBBBAAAAAAAA

■参照サイト
056 – Lucky Bag
AtCoder Beginner Contest 204 (D – Cooking)

2021年6月23日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題070 (Plant Planning) を解いてみた.

■感想.
1. 問題070は, 規則性を抽出できたので, AC版に到達出来たと思う.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題070 をご覧下さい.

■C++版プログラム(問題070／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 x[101010], y[101010], xCum[101010], yCum[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld %lld", &x[i], &y[i]);
    
    // 2. sort.
    sort(x, x + N);
    sort(y, y + N);
    
    // 3. 累積和.
    rep(i, N) xCum[i + 1] = xCum[i] + x[i];
    rep(i, N) yCum[i + 1] = yCum[i] + y[i];
    
    // 4. 最小値となる座標を選択.
    // 4-1. X軸方向.
    LL xL1 = 202020202020202020;
    rep(i, N){
        // i番目の座標を基準とした場合のマンハッタン距離.
        LL mx = 0;
        mx += x[i] * (i + 1) - xCum[i];               // 前半.
        mx += xCum[N] - xCum[i + 1] - x[i] * (N - i); // 後半.
        
        // 最小値更新.
        xL1 = min(xL1, mx);
    }
    
    // 4-2. Y軸方向.
    LL yL1 = 202020202020202020;
    rep(i, N){
        // i番目の座標を基準とした場合のマンハッタン距離.
        LL my = 0;
        my += y[i] * (i + 1) - yCum[i];               // 前半.
        my += yCum[N] - yCum[i + 1] - y[i] * (N - i); // 後半.
        
        // 最小値更新.
        yL1 = min(yL1, my);
    }
    
    // 5. 出力.
    printf("%lld\n", xL1 + yL1);
    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 x[101010], y[101010], xCum[101010], yCum[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. sort.

sort(x, x + N);

sort(y, y + N);

// 3. 累積和.

rep(i, N) xCum[i + 1] = xCum[i] + x[i];

rep(i, N) yCum[i + 1] = yCum[i] + y[i];

// 4. 最小値となる座標を選択.

// 4-1. X軸方向.

LL xL1 = 202020202020202020;

rep(i, N){

// i番目の座標を基準とした場合のマンハッタン距離.

LL mx = 0;

mx += x[i] * (i + 1) - xCum[i]; // 前半.

mx += xCum[N] - xCum[i + 1] - x[i] * (N - i); // 後半.

// 最小値更新.

xL1 = min(xL1, mx);

}

// 4-2. Y軸方向.

LL yL1 = 202020202020202020;

rep(i, N){

// i番目の座標を基準とした場合のマンハッタン距離.

LL my = 0;

my += y[i] * (i + 1) - yCum[i]; // 前半.

my += yCum[N] - yCum[i + 1] - y[i] * (N - i); // 後半.

// 最小値更新.

yL1 = min(yL1, my);

}

// 5. 出力.

printf("%lld\n", xL1 + yL1);

return 0;

}

[入力例]
2
-1 2
1 1

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

[入力例]
2
1 0
0 1

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

[入力例]
5
2 5
2 5
-3 4
-4 -8
6 -2

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

[入力例]
4
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000

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

[入力例]
10
21 -56
12 3
-85 109
52 83
74 -104
74 60
-27 23
115 26
48 -31
-33 56

[出力例]
974

[入力例]
20
1071 -547
-1209 955
471 619
11 -274
616 945
398 947
74 -719
-791 116
553 895
963 1123
1169 -588
351 263
-1074 1168
-194 472
74 983
335 -87
20 -759
250 109
-703 87
110 125

[出力例]
20766

[入力例]
30
36482 -23698
389 35575
-62928 92676
122078 54909
28165 109096
-73226 57941
105357 48524
20055 -58032
16498 16028
117248 -52570
11791 90614
77697 80036
-85345 99427
79997 112720
41282 21973
5960 38768
-101579 35767
59552 105905
-6496 8393
21473 57496
54252 -16542
10940 21207
11230 -52560
15006 25961
99768 95712
-96551 894
31111 41698
-36617 114873
123235 -61626
120138 -73622

[出力例]
2861955

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

[入力例]

-1 2

1 1

[出力例]

※AtCoderテストケースより

[入力例]

1 0

0 1

[出力例]

※AtCoderテストケースより

[入力例]

2 5

-3 4

-4 -8

6 -2

[出力例]

※AtCoderテストケースより

[入力例]

1000000000 1000000000

-1000000000 1000000000

-1000000000 -1000000000

1000000000 -1000000000

[出力例]

8000000000

※AtCoderテストケースより

[入力例]

21 -56

12 3

-85 109

52 83

74 -104

74 60

-27 23

115 26

48 -31

-33 56

[出力例]

974

[入力例]

1071 -547

-1209 955

471 619

11 -274

616 945

398 947

74 -719

-791 116

553 895

963 1123

1169 -588

351 263

-1074 1168

-194 472

74 983

335 -87

20 -759

250 109

-703 87

110 125

[出力例]

20766

[入力例]

36482 -23698

389 35575

-62928 92676

122078 54909

28165 109096

-73226 57941

105357 48524

20055 -58032

16498 16028

117248 -52570

11791 90614

77697 80036

-85345 99427

79997 112720

41282 21973

5960 38768

-101579 35767

59552 105905

-6496 8393

21473 57496

54252 -16542

10940 21207

11230 -52560

15006 25961

99768 95712

-96551 894

31111 41698

-36617 114873

123235 -61626

120138 -73622

[出力例]

2861955

■参照サイト
070 – Plant Planning

2021年6月22日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題060 (Chimera) を解いてみた.

■感想.
1. 問題060は, 実装方針を決めることが出来たので, AC版に到達出来たと思う.
2. LIS(Longest increase subsequence) の復習ができたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題060 をご覧下さい.

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

// 以下の過去問を参照.
// https://atcoder.jp/contests/abc134/tasks/abc134_e
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()
int a[303030];
P dpL[303030], dpR[303030]; // {数列の長さ, 最大値}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 狭義単調増加な数列の長さの最大値は？
    // -> LIS(Longest increase subsequence) を 利用.
    // 2-1. 左から右方向へチェック.
    vi lLis;
    rep(i, N){
        // 数列を保存.
        if(lLis.size() == 0 || lLis.back() < a[i]){
            lLis.pb(a[i]);
        }else{
            int at = lower_bound(all(lLis), a[i]) - lLis.begin();
            lLis[at] = a[i];
        }
        
        // インデックス i における数列の長さ, 最大値 を 保存.
        dpL[i].a = lLis.size();
        dpL[i].b = lLis.back();
    }
    
    // 2-2. 右から左方向へチェック.
    vi rLis;
    repr(i, N - 1, 0){
        // 数列を保存.
        if(rLis.size() == 0 || rLis.back() < a[i]){
            rLis.pb(a[i]);
        }else{
            int at = lower_bound(all(rLis), a[i]) - rLis.begin();
            rLis[at] = a[i];
        }
        
        // インデックス i における数列の長さ, 最大値 を 保存.
        dpR[i].a = rLis.size();
        dpR[i].b = rLis.back();
    }
    
    // 3. 最大個数を計算.
    int ans = 0;
    rep(i, N){
        int t = dpL[i].a + dpR[i].a;
        if(dpL[i].b == dpR[i].b) t--;
        ans = max(ans, t);
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 以下の過去問を参照.

// https://atcoder.jp/contests/abc134/tasks/abc134_e

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using P = pair<int, int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

int a[303030];

P dpL[303030], dpR[303030]; // {数列の長さ, 最大値}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

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

// 2-1. 左から右方向へチェック.

vi lLis;

rep(i, N){

// 数列を保存.

if(lLis.size() == 0 || lLis.back() < a[i]){

lLis.pb(a[i]);

}else{

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

lLis[at] = a[i];

}

// インデックス i における数列の長さ, 最大値を保存.

dpL[i].a = lLis.size();

dpL[i].b = lLis.back();

}

// 2-2. 右から左方向へチェック.

vi rLis;

repr(i, N - 1, 0){

// 数列を保存.

if(rLis.size() == 0 || rLis.back() < a[i]){

rLis.pb(a[i]);

}else{

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

rLis[at] = a[i];

}

// インデックス i における数列の長さ, 最大値を保存.

dpR[i].a = rLis.size();

dpR[i].b = rLis.back();

}

// 3. 最大個数を計算.

int ans = 0;

rep(i, N){

int t = dpL[i].a + dpR[i].a;

if(dpL[i].b == dpR[i].b) t--;

ans = max(ans, t);

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
4
1 2 3 4

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

[入力例]
5
3 3 3 3 3

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

[入力例]
15
1 6 11 10 1 11 4 10 13 4 9 9 15 4 11

[出力例]
7

[入力例]
30
17 24 25 23 10 10 23 13 20 2 6 4 9 7 7 8 21 9 7 8 18 20 8 3 21 21 22 22 5 19

[出力例]
10

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

[出力例]
28

[入力例]
300
48 150 23 127 62 109 18 58 128 145 116 114 135 10 124 132 140 66 86 61 7 84 129 114 55 136 113 131 36 143 121 15 52 92 141 24 10 27 121 144 49 75 130 68 71 92 134 41 28 39 149 30 1 1 69 93 71 40 50 42 110 68 55 27 41 79 94 39 23 57 38 21 83 111 38 58 102 34 140 132 102 143 54 76 108 57 46 23 139 28 130 1 114 40 67 80 29 27 105 34 16 8 115 77 28 85 105 133 32 70 127 64 58 45 79 89 13 74 5 27 53 101 44 46 59 92 143 64 21 102 49 93 140 114 61 87 98 80 25 118 117 102 79 46 135 73 47 31 92 118 145 15 56 85 45 36 83 123 140 33 95 98 96 139 127 111 144 127 48 54 69 35 113 39 81 12 132 27 47 104 110 97 99 1 118 9 86 14 96 51 67 59 18 108 130 97 12 17 32 27 70 13 63 60 29 63 58 128 10 50 123 90 120 13 77 7 130 34 122 76 104 31 80 79 122 29 2 28 106 143 116 112 1 6 82 2 7 147 84 131 145 141 50 32 42 143 73 83 112 73 22 32 60 47 94 144 121 34 83 110 9 41 98 48 137 59 63 32 125 109 46 71 120 116 58 5 80 129 34 6 116 101 128 56 28 8 71 149 103 70 90 65 136 118 48 73 17 144 6 81

[出力例]
41

[入力例]

1 2 3 3 2 1

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

3 3 3 3 3

[出力例]

※AtCoderテストケースより

[入力例]

1 6 11 10 1 11 4 10 13 4 9 9 15 4 11

[出力例]

[入力例]

17 24 25 23 10 10 23 13 20 2 6 4 9 7 7 8 21 9 7 8 18 20 8 3 21 21 22 22 5 19

[出力例]

[入力例]

120

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

[出力例]

[入力例]

300

48 150 23 127 62 109 18 58 128 145 116 114 135 10 124 132 140 66 86 61 7 84 129 114 55 136 113 131 36 143 121 15 52 92 141 24 10 27 121 144 49 75 130 68 71 92 134 41 28 39 149 30 1 1 69 93 71 40 50 42 110 68 55 27 41 79 94 39 23 57 38 21 83 111 38 58 102 34 140 132 102 143 54 76 108 57 46 23 139 28 130 1 114 40 67 80 29 27 105 34 16 8 115 77 28 85 105 133 32 70 127 64 58 45 79 89 13 74 5 27 53 101 44 46 59 92 143 64 21 102 49 93 140 114 61 87 98 80 25 118 117 102 79 46 135 73 47 31 92 118 145 15 56 85 45 36 83 123 140 33 95 98 96 139 127 111 144 127 48 54 69 35 113 39 81 12 132 27 47 104 110 97 99 1 118 9 86 14 96 51 67 59 18 108 130 97 12 17 32 27 70 13 63 60 29 63 58 128 10 50 123 90 120 13 77 7 130 34 122 76 104 31 80 79 122 29 2 28 106 143 116 112 1 6 82 2 7 147 84 131 145 141 50 32 42 143 73 83 112 73 22 32 60 47 94 144 121 34 83 110 9 41 98 48 137 59 63 32 125 109 46 71 120 116 58 5 80 129 34 6 116 101 128 56 28 8 71 149 103 70 90 65 136 118 48 73 17 144 6 81

[出力例]

■参照サイト
060 – Chimera
AtCoder Beginner Contest 134(E – Sequence Decomposing)

C++の練習を兼ねて, 競プロ典型 90 問 の 問題016 (Minimum Coins) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題030 (K Factors) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 100 の 問題E (Or Plus Max) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題021 (Come Back in One Piece) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題042 (Multiple of 9) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題051 (Typical Shop) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題056 (Lucky Bag) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題070 (Plant Planning) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題060 (Chimera) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題016 (Minimum Coins) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題030 (K Factors) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 100 の問題E (Or Plus Max) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題021 (Come Back in One Piece) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題042 (Multiple of 9) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題051 (Typical Shop) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題056 (Lucky Bag) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題070 (Plant Planning) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題060 (Chimera) を解いてみた.