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

C++の練習を兼ねて, AtCoder Beginner Contest 123 の問題D (D – Cake 123) を解いてみた.

■感想.
1. 解答の方針が, 全く見えなかったので, 解説を読んだうえで, 実装した.
2. キューに追加されたことが無いかどうかの判定をするための実装が, 結構苦労した(set で対応しようとしたが, 上手く行かなかった, 他に良い方法が思いつかず, 結局, map で, 対応した).
3. map の key に, prefix(接頭語) を追加したが, おそらく, 不要だと思う.

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

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

// 解き直し.
// AtCoder Beginner Contest 123 解説.
// https://img.atcoder.jp/abc123/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
using LL = long long;
const int MAX = 1e3 + 1;
LL A[MAX], B[MAX], C[MAX];

struct cake{
    LL  d; // 美味しさの合計.
    int a; // A の index.
    int b; // B の index.
    int c; // C の index.
    bool operator < (const cake &C) const { return d < C.d; }
};

// 与えられた情報を結合して, 文字列を返却.
// @param prefix: 接頭語.
// @param d: 美味しさの合計.
// @param a: A の index.
// @param b: B の index.
// @param c: C の index.
// @return ret: map に 登録する 文字列 key.
string makeKey(string prefix, LL d, int a, int b, int c){
    string ret = prefix;
    ret += {"_"};
    ret += to_string(A[a] + B[b] + C[c]);
    ret += {"_"};
    ret += to_string(a);
    ret += {"_"};
    ret += to_string(b);
    ret += {"_"};
    ret += to_string(c);
    return ret;
}

int main(){
    
    // 1. 入力情報取得.
    int X, Y, Z, K;
    scanf("%d %d %d %d", &X, &Y, &Z, &K);
    FOR(i, 0, X) scanf("%lld", A + i);
    FOR(i, 0, Y) scanf("%lld", B + i);
    FOR(i, 0, Z) scanf("%lld", C + i);
    
    // 2. 降順sort.
    sort(A, A + MAX, greater<LL>());
    sort(B, B + MAX, greater<LL>());
    sort(C, C + MAX, greater<LL>());
    
    // 3. 解説通り(※Priority Queue (優先度付きキュー) を 使うパターン).
    int a = 0, b = 0, c = 0;
    priority_queue<cake> pq;
    map<string, int> m;
    pq.push({A[a] + B[b] + C[c], a, b, c});
    string s = makeKey("p", A[a] + B[b] + C[c], a, b, c);
    m[s]++;
    int index = 1;
    while(!pq.empty()){
        // 3-1. pq の中で, 一番美味しさの大きい要素を取得.
        cake i = pq.top();
        a = i.a, b = i.b, c = i.c;
        pq.pop();
        
        // 3-2. 追加されてないパターンを追加.
        cake p1 = {A[a + 1] + B[b] + C[c], a + 1, b, c};
        string s1 = makeKey("p", A[a + 1] + B[b] + C[c], a + 1, b, c);
        cake p2 = {A[a] + B[b + 1] + C[c], a, b + 1, c};
        string s2 = makeKey("p", A[a] + B[b + 1] + C[c], a, b + 1, c);
        cake p3 = {A[a] + B[b] + C[c + 1], a, b, c + 1};
        string s3 = makeKey("p", A[a] + B[b] + C[c + 1], a, b, c + 1);
        if(a < X - 1 && m[s1] == 0) pq.push(p1), m[s1]++;
        if(b < Y - 1 && m[s2] == 0) pq.push(p2), m[s2]++;
        if(c < Z - 1 && m[s3] == 0) pq.push(p3), m[s3]++;

        // 3-3. index番目 のケーキの美味しさの合計を出力.
        printf("%lld\n", i.d);
        
        // 3-4. increment.
        index++;
        
        // 3-5. index番目 が Kより大きくなったら終了.
        if(index > K) break;
    }
    // printf with std::string?
    // https://stackoverflow.com/questions/10865957/printf-with-stdstring
    // for(auto &e : m) printf("key=%s, value=%d\n", e.first.c_str(), e.second);
    return 0;
    
}

// 解き直し.

// AtCoder Beginner Contest 123 解説.

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

#include <bits/stdc++.h>

using namespace std;

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

using LL = long long;

const int MAX = 1e3 + 1;

LL A[MAX], B[MAX], C[MAX];

struct cake{

LL d; // 美味しさの合計.

int a; // A の index.

int b; // B の index.

int c; // C の index.

bool operator < (const cake &C) const { return d < C.d; }

};

// 与えられた情報を結合して, 文字列を返却.

// @param prefix: 接頭語.

// @param d: 美味しさの合計.

// @param a: A の index.

// @param b: B の index.

// @param c: C の index.

// @return ret: map に登録する文字列 key.

string makeKey(string prefix, LL d, int a, int b, int c){

string ret = prefix;

ret += {"_"};

ret += to_string(A[a] + B[b] + C[c]);

ret += {"_"};

ret += to_string(a);

ret += {"_"};

ret += to_string(b);

ret += {"_"};

ret += to_string(c);

return ret;

}

int main(){

// 1. 入力情報取得.

int X, Y, Z, K;

scanf("%d %d %d %d", &X, &Y, &Z, &K);

FOR(i, 0, X) scanf("%lld", A + i);

FOR(i, 0, Y) scanf("%lld", B + i);

FOR(i, 0, Z) scanf("%lld", C + i);

// 2. 降順sort.

sort(A, A + MAX, greater<LL>());

sort(B, B + MAX, greater<LL>());

sort(C, C + MAX, greater<LL>());

// 3. 解説通り(※Priority Queue (優先度付きキュー) を使うパターン).

int a = 0, b = 0, c = 0;

priority_queue<cake> pq;

map<string, int> m;

pq.push({A[a] + B[b] + C[c], a, b, c});

string s = makeKey("p", A[a] + B[b] + C[c], a, b, c);

m[s]++;

int index = 1;

while(!pq.empty()){

// 3-1. pq の中で, 一番美味しさの大きい要素を取得.

cake i = pq.top();

a = i.a, b = i.b, c = i.c;

pq.pop();

// 3-2. 追加されてないパターンを追加.

cake p1 = {A[a + 1] + B[b] + C[c], a + 1, b, c};

string s1 = makeKey("p", A[a + 1] + B[b] + C[c], a + 1, b, c);

cake p2 = {A[a] + B[b + 1] + C[c], a, b + 1, c};

string s2 = makeKey("p", A[a] + B[b + 1] + C[c], a, b + 1, c);

cake p3 = {A[a] + B[b] + C[c + 1], a, b, c + 1};

string s3 = makeKey("p", A[a] + B[b] + C[c + 1], a, b, c + 1);

if(a < X - 1 && m[s1] == 0) pq.push(p1), m[s1]++;

if(b < Y - 1 && m[s2] == 0) pq.push(p2), m[s2]++;

if(c < Z - 1 && m[s3] == 0) pq.push(p3), m[s3]++;

// 3-3. index番目のケーキの美味しさの合計を出力.

printf("%lld\n", i.d);

// 3-4. increment.

index++;

// 3-5. index番目が Kより大きくなったら終了.

if(index > K) break;

}

// printf with std::string?

// https://stackoverflow.com/questions/10865957/printf-with-stdstring

// for(auto &e : m) printf("key=%s, value=%d\n", e.first.c_str(), e.second);

return 0;

}

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

[出力例(debug版)]
19
17
15
14
13
12
10
8
key=p_10_0_1_1, value=1
key=p_12_1_0_1, value=1
key=p_13_1_1_0, value=1
key=p_14_0_0_1, value=1
key=p_15_0_1_0, value=1
key=p_17_1_0_0, value=1
key=p_19_0_0_0, value=1
key=p_8_1_1_1, value=1
※AtCoderテストケースより

[入力例]
3 3 3 5
1 10 100
2 20 200
1 10 100

[出力例(debug版)]
400
310
310
301
301
key=p_121_0_1_2, value=1
key=p_121_2_1_0, value=1
key=p_130_0_1_1, value=1
key=p_130_1_1_0, value=1
key=p_211_1_0_2, value=1
key=p_211_2_0_1, value=1
key=p_220_0_1_0, value=1
key=p_220_1_0_1, value=1
key=p_301_0_0_2, value=1
key=p_301_2_0_0, value=1
key=p_310_0_0_1, value=1
key=p_310_1_0_0, value=1
key=p_400_0_0_0, value=1
※AtCoderテストケースより

[入力例]
10 10 10 20
7467038376 5724769290 292794712 2843504496 3381970101 8402252870 249131806 6310293640 6690322794 6082257488
1873977926 2576529623 1144842195 1379118507 6003234687 4925540914 3902539811 3326692703 484657758 2877436338
4975681328 8974383988 2882263257 7690203955 514305523 6679823484 4263279310 585966808 3752282379 620585736

[出力例(debug版)]
23379871545
22444657051
22302177772
22095691512
21667941469
21366963278
21287912315
21279176669
21160477018
21085311041
21059876163
21017997739
20703329561
20702387965
20590247696
20383761436
20343962175
20254073196
20210218542
20150096547
key=p_18359588776_6_0_0, value=1
key=p_18445954391_1_0_3, value=1
key=p_18926038509_3_1_1, value=1
key=p_18969893163_0_4_1, value=1
key=p_19059782142_1_2_1, value=1
key=p_19072402774_1_1_2, value=1
key=p_19187217439_3_2_0, value=1
key=p_19306067663_2_1_1, value=1
key=p_19318858702_1_4_0, value=1
key=p_19373380965_2_0_2, value=1
key=p_19381168885_0_0_3, value=1
key=p_19418207932_5_0_1, value=1
key=p_19419149528_0_3_1, value=1
key=p_19567246593_2_2_0, value=1
key=p_19624694192_5_1_0, value=1
key=p_19768115067_1_3_0, value=1
key=p_19775696130_4_0_1, value=1
key=p_19953166481_0_5_0, value=1
key=p_19982182390_4_1_0, value=1
key=p_19994996636_0_2_1, value=1
key=p_20003732282_3_0_1, value=1
key=p_20007617268_0_1_2, value=1
key=p_20082783245_1_1_1, value=1
key=p_20150096547_1_0_2, value=1
key=p_20210218542_3_1_0, value=1
key=p_20254073196_0_4_0, value=1
key=p_20343962175_1_2_0, value=1
key=p_20383761436_2_0_1, value=1
key=p_20590247696_2_1_0, value=1
key=p_20702387965_5_0_0, value=1
key=p_20703329561_0_3_0, value=1
key=p_21017997739_0_1_1, value=1
key=p_21059876163_4_0_0, value=1
key=p_21085311041_0_0_2, value=1
key=p_21160477018_1_0_1, value=1
key=p_21279176669_0_2_0, value=1
key=p_21287912315_3_0_0, value=1
key=p_21366963278_1_1_0, value=1
key=p_21667941469_2_0_0, value=1
key=p_22095691512_0_0_1, value=1
key=p_22302177772_0_1_0, value=1
key=p_22444657051_1_0_0, value=1
key=p_23379871545_0_0_0, value=1
※AtCoderテストケースより

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

[入力例]

2 2 2 8

4 6

1 5

3 8

[出力例(debug版)]

key=p_10_0_1_1, value=1

key=p_12_1_0_1, value=1

key=p_13_1_1_0, value=1

key=p_14_0_0_1, value=1

key=p_15_0_1_0, value=1

key=p_17_1_0_0, value=1

key=p_19_0_0_0, value=1

key=p_8_1_1_1, value=1

※AtCoderテストケースより

[入力例]

3 3 3 5

1 10 100

2 20 200

1 10 100

[出力例(debug版)]

400

310

301

key=p_121_0_1_2, value=1

key=p_121_2_1_0, value=1

key=p_130_0_1_1, value=1

key=p_130_1_1_0, value=1

key=p_211_1_0_2, value=1

key=p_211_2_0_1, value=1

key=p_220_0_1_0, value=1

key=p_220_1_0_1, value=1

key=p_301_0_0_2, value=1

key=p_301_2_0_0, value=1

key=p_310_0_0_1, value=1

key=p_310_1_0_0, value=1

key=p_400_0_0_0, value=1

※AtCoderテストケースより

[入力例]

10 10 10 20

7467038376 5724769290 292794712 2843504496 3381970101 8402252870 249131806 6310293640 6690322794 6082257488

1873977926 2576529623 1144842195 1379118507 6003234687 4925540914 3902539811 3326692703 484657758 2877436338

4975681328 8974383988 2882263257 7690203955 514305523 6679823484 4263279310 585966808 3752282379 620585736

[出力例(debug版)]

23379871545

22444657051

22302177772

22095691512

21667941469

21366963278

21287912315

21279176669

21160477018

21085311041

21059876163

21017997739

20703329561

20702387965

20590247696

20383761436

20343962175

20254073196

20210218542

20150096547

key=p_18359588776_6_0_0, value=1

key=p_18445954391_1_0_3, value=1

key=p_18926038509_3_1_1, value=1

key=p_18969893163_0_4_1, value=1

key=p_19059782142_1_2_1, value=1

key=p_19072402774_1_1_2, value=1

key=p_19187217439_3_2_0, value=1

key=p_19306067663_2_1_1, value=1

key=p_19318858702_1_4_0, value=1

key=p_19373380965_2_0_2, value=1

key=p_19381168885_0_0_3, value=1

key=p_19418207932_5_0_1, value=1

key=p_19419149528_0_3_1, value=1

key=p_19567246593_2_2_0, value=1

key=p_19624694192_5_1_0, value=1

key=p_19768115067_1_3_0, value=1

key=p_19775696130_4_0_1, value=1

key=p_19953166481_0_5_0, value=1

key=p_19982182390_4_1_0, value=1

key=p_19994996636_0_2_1, value=1

key=p_20003732282_3_0_1, value=1

key=p_20007617268_0_1_2, value=1

key=p_20082783245_1_1_1, value=1

key=p_20150096547_1_0_2, value=1

key=p_20210218542_3_1_0, value=1

key=p_20254073196_0_4_0, value=1

key=p_20343962175_1_2_0, value=1

key=p_20383761436_2_0_1, value=1

key=p_20590247696_2_1_0, value=1

key=p_20702387965_5_0_0, value=1

key=p_20703329561_0_3_0, value=1

key=p_21017997739_0_1_1, value=1

key=p_21059876163_4_0_0, value=1

key=p_21085311041_0_0_2, value=1

key=p_21160477018_1_0_1, value=1

key=p_21279176669_0_2_0, value=1

key=p_21287912315_3_0_0, value=1

key=p_21366963278_1_1_0, value=1

key=p_21667941469_2_0_0, value=1

key=p_22095691512_0_0_1, value=1

key=p_22302177772_0_1_0, value=1

key=p_22444657051_1_0_0, value=1

key=p_23379871545_0_0_0, value=1

※AtCoderテストケースより

■参照サイト
AtCoder Beginner Contest 123

C++の練習を兼ねて, AtCoder Beginner Contest 123 の 問題D (D – Cake 123) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 123 の問題D (D – Cake 123) を解いてみた.

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