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

C++の練習を兼ねて, AtCoder Beginner Contest 195 の問題C (Comma) ～問題D (Shipping Center) を解いてみた.

■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. コンマの個数をカウント.
    LL ans = 0;
    if(N >= 1e3)  ans += N - (1e3 - 1);
    if(N >= 1e6)  ans += N - (1e6 - 1);
    if(N >= 1e9)  ans += N - (1e9 - 1);
    if(N >= 1e12) ans += N - (1e12 - 1);
    if(N >= 1e15) ans += N - (1e15 - 1);
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. コンマの個数をカウント.

LL ans = 0;

if(N >= 1e3) ans += N - (1e3 - 1);

if(N >= 1e6) ans += N - (1e6 - 1);

if(N >= 1e9) ans += N - (1e9 - 1);

if(N >= 1e12) ans += N - (1e12 - 1);

if(N >= 1e15) ans += N - (1e15 - 1);

// 3. 出力.

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

return 0;

}

[入力例]
1010

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

[入力例]
27182818284590

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

[入力例]
1000

[出力例]
1

[入力例]
1234567

[出力例]
1468136

[入力例]
314159265358979

[出力例]
1255636060434920

[入力例]
1000000000000000

[出力例]
3998998998999005

[入力例]

1010

[出力例]

※AtCoderテストケースより

[入力例]

27182818284590

[出力例]

107730272137364

※AtCoderテストケースより

[入力例]

1000

[出力例]

[入力例]

1234567

[出力例]

1468136

[入力例]

314159265358979

[出力例]

1255636060434920

[入力例]

1000000000000000

[出力例]

3998998998999005

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

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

struct good{
    int w; // 荷物の大きさ.
    int v; // 荷物の価値.
    bool operator < (const good &G) const {
        return (w < G.w) || ((w == G.w) && (v > G.v));
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M, Q;
    scanf("%d %d %d", &N, &M, &Q);
    vector<good> goods;
    rep(i, N){
        int w, v;
        scanf("%d %d", &w, &v);
        good b;
        b.w = w;
        b.v = v;
        goods.pb(b);
    }
    rep(i, M) scanf("%d", &x[i]);
    
    // 2. sort.
    // 大きさの小さな箱から順に, 並び替える.
    // もし, 大きさが等しい場合は, その箱に入れることができる価値が大きい荷物から順に, 並び替える.
    sort(all(goods));
    // for(auto &p : goods) printf("w=%d v=%d\n", p.w, p.v);
    
    // 3. クエリ回答.
    rep(i, Q){
        // 使用不可の箱情報.
        int l, r;
        scanf("%d %d", &l, &r);
        l--, r--;
        
        // 箱に保管したかのフラグ.
        int memo[55];
        rep(j, 55) memo[j] = 0;
        
        // 使用可能な, 箱の用意.
        PQ pq;
        rep(j, l)         pq.push(x[j]);
        repx(j, r + 1, M) pq.push(x[j]);
        
        // 各荷物について, 箱に保管できるか？
        int ans = 0;
        // 使用可能な箱を取り出していく.
        while(!pq.empty()){
            // 箱を取り出す.
            int p = pq.top();
            pq.pop();
            
            // どの荷物を箱に保管できるかのチェック.
            int maxV = 0, maxAt = -1;
            rep(j, goods.size()){
                // 箱にしまえない場合は, 終了.
                if(goods[j].w > p) break;
                
                // 箱に保管できる場合は, 価値の最大値を探す.
                if(!memo[j]){
                    if(maxV < goods[j].v){
                        maxV = goods[j].v;
                        maxAt = j;
                    }
                };
            }
            
            // 価値が最大のものを箱に保管できた場合は, 保管済みに設定.
            if(maxAt != -1){
                memo[maxAt] = 1;
                ans += maxV;
            }
        }
        
        // 出力.
        printf("%d\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc195/editorial/846

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using PQ = priority_queue<int, vector<int>, greater<int>>;

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

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

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

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

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

#define pb push_back

int x[55];

struct good{

int w; // 荷物の大きさ.

int v; // 荷物の価値.

bool operator < (const good &G) const {

return (w < G.w) || ((w == G.w) && (v > G.v));

}

};

int main(){

// 1. 入力情報.

int N, M, Q;

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

vector<good> goods;

rep(i, N){

int w, v;

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

good b;

b.w = w;

b.v = v;

goods.pb(b);

}

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

// 2. sort.

// 大きさの小さな箱から順に, 並び替える.

// もし, 大きさが等しい場合は, その箱に入れることができる価値が大きい荷物から順に, 並び替える.

sort(all(goods));

// for(auto &p : goods) printf("w=%d v=%d\n", p.w, p.v);

// 3. クエリ回答.

rep(i, Q){

// 使用不可の箱情報.

int l, r;

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

l--, r--;

// 箱に保管したかのフラグ.

int memo[55];

rep(j, 55) memo[j] = 0;

// 使用可能な, 箱の用意.

PQ pq;

rep(j, l) pq.push(x[j]);

repx(j, r + 1, M) pq.push(x[j]);

// 各荷物について, 箱に保管できるか？

int ans = 0;

// 使用可能な箱を取り出していく.

while(!pq.empty()){

// 箱を取り出す.

int p = pq.top();

pq.pop();

// どの荷物を箱に保管できるかのチェック.

int maxV = 0, maxAt = -1;

rep(j, goods.size()){

// 箱にしまえない場合は, 終了.

if(goods[j].w > p) break;

// 箱に保管できる場合は, 価値の最大値を探す.

if(!memo[j]){

if(maxV < goods[j].v){

maxV = goods[j].v;

maxAt = j;

}

};

}

// 価値が最大のものを箱に保管できた場合は, 保管済みに設定.

if(maxAt != -1){

memo[maxAt] = 1;

ans += maxV;

}

// 出力.

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

}

return 0;

}

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

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

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

[出力例]
28
21
21
9
9
0
16

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

[出力例]
110
110
110
101
80
63
93
75

[入力例]

3 4 3

1 9

5 3

7 8

1 8 6 9

4 4

1 4

1 3

[出力例]

※AtCoderテストケースより

[入力例]

5 6 7

3 9

5 5

5 7

10 8

10 12

1 2 5 10 4 3

1 2

1 3

2 3

2 4

3 5

3 6

4 5

[出力例]

[入力例]

10 12 8

13 15

11 18

7 9

13 15

20 12

23 9

13 18

17 18

17 12

20 17

5 7 10 10 11 11 12 13 13 15 20 20

1 1

1 2

2 3

2 6

5 8

6 10

11 11

11 12

[出力例]

110

101

■参照サイト
パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）

C++の練習を兼ねて, AtCoder Beginner Contest 195 の 問題C (Comma) ～ 問題D (Shipping Center) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 195 の問題C (Comma) ～問題D (Shipping Center) を解いてみた.

コメントを残すコメントをキャンセル