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

C++の練習を兼ねて, AtCoder Beginner Contest 160 の問題E (E – Red and Green Apples) を解いてみた.

■感想.
1. 優先度付きキュー（priority_queue）を使う方針で, 何とかAC版となったので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 160 解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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 a first
#define b second

int main(){
    
    // 1. 入力情報.
    int X, Y, A, B, C;
    scanf("%d %d %d %d %d", &X, &Y, &A, &B, &C);
    LL x;
    priority_queue<LL> pPQ, qPQ, r, apple;
    rep(i, A){
        scanf("%lld", &x);
        pPQ.push(x);
    }
    rep(i, B){
        scanf("%lld", &x);
        qPQ.push(x);
    }
    rep(i, C){
        scanf("%lld", &x);
        r.push(x);
    }
    
    // 2. X個 の 赤色リンゴ, Y個 の 緑色リンゴ を 保存.
    priority_queue<P, vector<P>, greater<P>> pq;
    int c1 = 0, c2 = 0;
    while(++c1 <= X){
        LL p = pPQ.top();
        pPQ.pop();
        pq.push({p, 1});
    }
    while(++c2 <= Y){
        LL q = qPQ.top();
        qPQ.pop();
        pq.push({q, 2});
    }
    
    // 3. 組み換え.
    // pq の 最小の美味しさのリンゴ と r の 最大の美味しさのリンゴ を 
    // 比較して, 組み換え.
    while(!pq.empty()){
        // pq から 取得.
        P a1 = pq.top();
        
        if(!r.empty()){
            // r から 取得.
            LL a2 = r.top();
            
            // リンゴ a1 が 赤色 の 場合, リンゴ a2 の 美味しさ が 大きい場合, 入れ替え.
            if(a1.b == 1 && X > 0 && a1.a < a2){
                pq.pop();
                pq.push({a2, 3});
                r.pop();
                X--;
                continue;
            }
            
            // リンゴ a1 が 緑色 の 場合, リンゴ a2 の 美味しさ が 大きい場合, 入れ替え.
            if(a1.b == 2 && Y > 0 && a1.a < a2){
                pq.pop();
                pq.push({a2, 3});
                r.pop();
                Y--;
                continue;
            }
        }
        
        // 組み替え出来なかった場合.
        pq.pop();
        apple.push(a1.a);
    }
    
    // 4. 美味しさの集計.
    LL ans = 0;
    while(!apple.empty()){
        LL a = apple.top();
        apple.pop();
        ans += a;
        // printf("%lld\n", a);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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 a first

#define b second

int main(){

// 1. 入力情報.

int X, Y, A, B, C;

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

LL x;

priority_queue<LL> pPQ, qPQ, r, apple;

rep(i, A){

scanf("%lld", &x);

pPQ.push(x);

}

rep(i, B){

scanf("%lld", &x);

qPQ.push(x);

}

rep(i, C){

scanf("%lld", &x);

r.push(x);

}

// 2. X個の赤色リンゴ, Y個の緑色リンゴを保存.

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

int c1 = 0, c2 = 0;

while(++c1 <= X){

LL p = pPQ.top();

pPQ.pop();

pq.push({p, 1});

}

while(++c2 <= Y){

LL q = qPQ.top();

qPQ.pop();

pq.push({q, 2});

}

// 3. 組み換え.

// pq の最小の美味しさのリンゴと r の最大の美味しさのリンゴを

// 比較して, 組み換え.

while(!pq.empty()){

// pq から取得.

P a1 = pq.top();

if(!r.empty()){

// r から取得.

LL a2 = r.top();

// リンゴ a1 が赤色の場合, リンゴ a2 の美味しさが大きい場合, 入れ替え.

if(a1.b == 1 && X > 0 && a1.a < a2){

pq.pop();

pq.push({a2, 3});

r.pop();

X--;

continue;

}

// リンゴ a1 が緑色の場合, リンゴ a2 の美味しさが大きい場合, 入れ替え.

if(a1.b == 2 && Y > 0 && a1.a < a2){

pq.pop();

pq.push({a2, 3});

r.pop();

Y--;

continue;

}

// 組み替え出来なかった場合.

pq.pop();

apple.push(a1.a);

}

// 4. 美味しさの集計.

LL ans = 0;

while(!apple.empty()){

LL a = apple.top();

apple.pop();

ans += a;

// printf("%lld\n", a);

}

// 5. 出力.

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

return 0;

}

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

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

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

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

[入力例]
2 2 4 4 4
11 12 13 14
21 22 23 24
1 2 3 4

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

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

[出力例]
2

[入力例]
12 25 18 30 27
190 657 115 37 909 270 639 985 960 10 353 560 380 347 408 573 665 700
266 917 630 119 229 764 70 197 617 685 48 142 502 220 41 805 350 686 648 537 686 343 773 121 293 162 775 80 285 450
927 209 230 853 619 401 774 743 124 216 296 620 575 690 890 8 129 274 419 636 225 396 532 167 175 626 71

[出力例]
25435

[入力例]
5 7 10 13 11
691238539 839775129 423518584 201289886 582985771 538396815 443879402 161017534 58062635 755432143
825073727 921590855 430912918 297069423 791855375 938244497 692856590 357476221 986992383 228340270 893857249 56370970 868214757
238113853 321266905 137943723 899165731 612611308 830868780 74999267 423085548 878409626 769495093 357911685

[出力例]
10443543202

[入力例]

1 2 2 2 1

2 4

5 1

[出力例]

※AtCoderテストケースより

[入力例]

2 2 2 2 2

8 6

9 1

2 1

[出力例]

※AtCoderテストケースより

[入力例]

2 2 4 4 4

11 12 13 14

21 22 23 24

1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1 1 1

[出力例]

[入力例]

12 25 18 30 27

190 657 115 37 909 270 639 985 960 10 353 560 380 347 408 573 665 700

266 917 630 119 229 764 70 197 617 685 48 142 502 220 41 805 350 686 648 537 686 343 773 121 293 162 775 80 285 450

927 209 230 853 619 401 774 743 124 216 296 620 575 690 890 8 129 274 419 636 225 396 532 167 175 626 71

[出力例]

25435

[入力例]

5 7 10 13 11

691238539 839775129 423518584 201289886 582985771 538396815 443879402 161017534 58062635 755432143

825073727 921590855 430912918 297069423 791855375 938244497 692856590 357476221 986992383 228340270 893857249 56370970 868214757

238113853 321266905 137943723 899165731 612611308 830868780 74999267 423085548 878409626 769495093 357911685

[出力例]

10443543202

■参照サイト
AtCoder Beginner Contest 160

C++の練習を兼ねて, AtCoder Beginner Contest 160 の 問題E (E – Red and Green Apples) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 160 の問題E (E – Red and Green Apples) を解いてみた.

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