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

C++の練習を兼ねて, AtCoder Beginner Contest 308 の問題F (Vouchers) ～問題G (Minimum Xor Pair Query) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, std::multiset の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using PQ = priority_queue<LL>;
using P = pair<LL, LL>;
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()

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vl P(N), L(M), D(M);
    rep(i, N) scanf("%lld", &P[i]);
    rep(i, M) scanf("%lld", &L[i]);
    rep(i, M) scanf("%lld", &D[i]);
    vp v(M);
    rep(i, M){
        v[i].a = L[i];
        v[i].b = D[i];
    }
    
    // 2. sort.
    sort(all(P));
    sort(all(v));
    
    // 3. 最小の金額は？
    LL ans = 0;
    int j = 0;
    PQ pq;
    rep(i, N){
        // 3-1. 利用可能なクーポンを保存.
        while(j < M){
            if(v[j].a > P[i]) break;
            pq.push(v[j].b);
            ++j;
        }
        
        // 3-2. 加算.
        ans += P[i];
        
        // 3-3. クーポン適用.
        if(!pq.empty()){
            ans -= pq.top();
            pq.pop();
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using PQ = priority_queue<LL>;

using P = pair<LL, LL>;

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()

int main(){

// 1. 入力情報.

int N, M;

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

vl P(N), L(M), D(M);

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

rep(i, M) scanf("%lld", &L[i]);

rep(i, M) scanf("%lld", &D[i]);

vp v(M);

rep(i, M){

v[i].a = L[i];

v[i].b = D[i];

}

// 2. sort.

sort(all(P));

sort(all(v));

// 3. 最小の金額は？

LL ans = 0;

int j = 0;

PQ pq;

rep(i, N){

// 3-1. 利用可能なクーポンを保存.

while(j < M){

if(v[j].a > P[i]) break;

pq.push(v[j].b);

++j;

}

// 3-2. 加算.

ans += P[i];

// 3-3. クーポン適用.

if(!pq.empty()){

ans -= pq.top();

pq.pop();

}

// 4. 出力.

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

return 0;

}

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

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

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

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

[入力例]
12 7
103 48 123 114 10 39 69 113 54 72 21 110
54 102 98 75 122 83 99
43 91 89 69 112 80 86

[出力例]
375

[入力例]
100 150
882 1159 678 1049 838 992 1091 749 311 258 411 68 107 785 491 1085 262 351 313 688 12 150 208 517 684 841 511 452 610 799 165 2 421 811 604 896 291 230 298 362 713 1035 53 1064 731 1165 1147 51 846 182 440 324 1113 190 702 651 22 689 23 198 290 848 589 51 597 1028 387 396 951 707 91 507 613 436 4 387 802 560 60 522 695 828 1121 504 35 1174 994 156 211 86 12 73 1072 24 158 1071 989 542 1015 258
956 950 238 584 866 695 858 303 1055 549 528 750 810 373 621 56 1046 837 405 402 900 570 977 928 1090 1114 1124 1026 396 521 571 63 1178 459 468 919 463 372 826 380 553 68 1031 623 961 883 491 697 393 275 1045 620 15 125 970 928 801 433 1084 1150 40 986 204 646 846 830 1067 250 1201 765 77 370 91 1007 393 717 1180 100 290 1043 318 311 235 836 708 683 155 365 521 142 878 1127 20 152 1084 458 1043 38 753 1143 846 132 1049 371 95 67 490 364 1148 77 681 905 519 500 793 288 211 95 802 1156 1069 611 334 312 479 1218 766 39 199 866 887 755 540 106 664 1038 517 932 1038 1185 872 1160 671 158 200 940 40 877 845 777
507 283 238 584 687 301 238 303 205 51 129 750 232 42 556 56 208 837 205 402 164 487 306 355 222 404 654 358 157 521 92 63 776 266 256 573 463 271 70 380 50 68 174 596 662 287 491 358 393 275 186 136 15 125 604 884 605 433 735 722 40 485 93 557 839 172 543 250 881 234 77 301 91 816 327 335 427 100 88 752 318 288 235 66 253 683 155 365 88 99 728 500 20 152 56 458 589 38 96 790 341 132 772 371 95 45 299 364 735 77 569 240 48 94 206 288 211 34 535 882 383 611 334 30 479 675 240 39 199 159 348 200 80 106 356 786 517 895 563 783 761 359 453 42 200 547 40 223 85 593

[出力例]
15000

[入力例]

3 3

4 3 1

4 4 2

2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

10 5

9 7 1 5 2 2 5 5 7 6

7 2 7 8 2

3 2 4 1 2

[出力例]

※AtCoderテストケースより

[入力例]

12 7

103 48 123 114 10 39 69 113 54 72 21 110

54 102 98 75 122 83 99

43 91 89 69 112 80 86

[出力例]

375

[入力例]

100 150

882 1159 678 1049 838 992 1091 749 311 258 411 68 107 785 491 1085 262 351 313 688 12 150 208 517 684 841 511 452 610 799 165 2 421 811 604 896 291 230 298 362 713 1035 53 1064 731 1165 1147 51 846 182 440 324 1113 190 702 651 22 689 23 198 290 848 589 51 597 1028 387 396 951 707 91 507 613 436 4 387 802 560 60 522 695 828 1121 504 35 1174 994 156 211 86 12 73 1072 24 158 1071 989 542 1015 258

956 950 238 584 866 695 858 303 1055 549 528 750 810 373 621 56 1046 837 405 402 900 570 977 928 1090 1114 1124 1026 396 521 571 63 1178 459 468 919 463 372 826 380 553 68 1031 623 961 883 491 697 393 275 1045 620 15 125 970 928 801 433 1084 1150 40 986 204 646 846 830 1067 250 1201 765 77 370 91 1007 393 717 1180 100 290 1043 318 311 235 836 708 683 155 365 521 142 878 1127 20 152 1084 458 1043 38 753 1143 846 132 1049 371 95 67 490 364 1148 77 681 905 519 500 793 288 211 95 802 1156 1069 611 334 312 479 1218 766 39 199 866 887 755 540 106 664 1038 517 932 1038 1185 872 1160 671 158 200 940 40 877 845 777

507 283 238 584 687 301 238 303 205 51 129 750 232 42 556 56 208 837 205 402 164 487 306 355 222 404 654 358 157 521 92 63 776 266 256 573 463 271 70 380 50 68 174 596 662 287 491 358 393 275 186 136 15 125 604 884 605 433 735 722 40 485 93 557 839 172 543 250 881 234 77 301 91 816 327 335 427 100 88 752 318 288 235 66 253 683 155 365 88 99 728 500 20 152 56 458 589 38 96 790 341 132 772 371 95 45 299 364 735 77 569 240 48 94 206 288 211 34 535 882 383 611 334 30 479 675 240 39 199 159 348 200 80 106 356 786 517 895 563 783 761 359 453 42 200 547 40 223 85 593

[出力例]

15000

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

// 解き直し.
// https://atcoder.jp/contests/abc308/editorial/6707
// 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 main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. クエリ回答.
    map<int, int> mXor;
    multiset<int> mst;
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int f;
        scanf("%d", &f);
        
        // 2-2. クエリ 1.
        if(f == 1){
            int x;
            scanf("%d", &x);
            
            // 要素数で分岐.
            // 0個.
            int n = mst.size();
            if(n == 0){
                mst.insert(x);
                continue;
            }
            
            // 1個.
            if(n == 1){
                ++mXor[*mst.begin() ^ x];
                mst.insert(x);
                continue;
            }
            
            // 2個以上.
            // -> 最初, 中間, 最後で分岐.
            mst.insert(x);
            auto itr = mst.lower_bound(x);
            if(itr == mst.begin()){
                ++itr;
                ++mXor[*mst.begin() ^ *itr];
            }else if(itr == --mst.end()){
                --itr;
                ++mXor[*(--mst.end()) ^ *itr];
            }else{
                int l = *(--itr);
                ++itr;
                int r = *(++itr);
                --mXor[l ^ r];
                if(mXor[l ^ r] == 0) mXor.erase(l ^ r);
                ++mXor[l ^ x];
                ++mXor[x ^ r];
            }
        }
        
        // 2-3. クエリ 2.
        if(f == 2){
            int x;
            scanf("%d", &x);
            
            // 要素数で分岐.
            // 1個.
            int n = mst.size();
            if(n == 1){
                mst.erase(x);
                continue;
            }
            
            // 2個以上.
            // -> 最初, 中間, 最後で分岐.
            auto itr = mst.lower_bound(x);
            if(itr == mst.begin()){
                int l = *mst.begin();
                int r = *(++itr);
                --mXor[l ^ r];
                if(mXor[l ^ r] == 0) mXor.erase(l ^ r);
            }else if(itr == --mst.end()){
                int l = *(--itr);
                int r = *(--mst.end());
                --mXor[l ^ r];
                if(mXor[l ^ r] == 0) mXor.erase(l ^ r);
            }else{
                int l = *(--itr);
                ++itr;
                int r = *(++itr);
                ++mXor[l ^ r];
                --mXor[l ^ x];
                if(mXor[l ^ x] == 0) mXor.erase(l ^ x);
                --mXor[x ^ r];
                if(mXor[x ^ r] == 0) mXor.erase(x ^ r);
            }
            mst.erase(mst.find(x));
        }
        
        // 2-4. クエリ 3.
        if(f == 3) printf("%d\n", mXor.begin()->first);
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

// 解き直し.

// https://atcoder.jp/contests/abc308/editorial/6707

// 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 main(){

// 1. 入力情報.

int Q;

scanf("%d", &Q);

// 2. クエリ回答.

map<int, int> mXor;

multiset<int> mst;

rep(i, Q){

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

int f;

scanf("%d", &f);

// 2-2. クエリ 1.

if(f == 1){

int x;

scanf("%d", &x);

// 要素数で分岐.

// 0個.

int n = mst.size();

if(n == 0){

mst.insert(x);

continue;

}

// 1個.

if(n == 1){

++mXor[*mst.begin() ^ x];

mst.insert(x);

continue;

}

// 2個以上.

// -> 最初, 中間, 最後で分岐.

mst.insert(x);

auto itr = mst.lower_bound(x);

if(itr == mst.begin()){

++itr;

++mXor[*mst.begin() ^ *itr];

}else if(itr == --mst.end()){

--itr;

++mXor[*(--mst.end()) ^ *itr];

}else{

int l = *(--itr);

++itr;

int r = *(++itr);

--mXor[l ^ r];

if(mXor[l ^ r] == 0) mXor.erase(l ^ r);

++mXor[l ^ x];

++mXor[x ^ r];

}

// 2-3. クエリ 2.

if(f == 2){

int x;

scanf("%d", &x);

// 要素数で分岐.

// 1個.

int n = mst.size();

if(n == 1){

mst.erase(x);

continue;

}

// 2個以上.

// -> 最初, 中間, 最後で分岐.

auto itr = mst.lower_bound(x);

if(itr == mst.begin()){

int l = *mst.begin();

int r = *(++itr);

--mXor[l ^ r];

if(mXor[l ^ r] == 0) mXor.erase(l ^ r);

}else if(itr == --mst.end()){

int l = *(--itr);

int r = *(--mst.end());

--mXor[l ^ r];

if(mXor[l ^ r] == 0) mXor.erase(l ^ r);

}else{

int l = *(--itr);

++itr;

int r = *(++itr);

++mXor[l ^ r];

--mXor[l ^ x];

if(mXor[l ^ x] == 0) mXor.erase(l ^ x);

--mXor[x ^ r];

if(mXor[x ^ r] == 0) mXor.erase(x ^ r);

}

mst.erase(mst.find(x));

}

// 2-4. クエリ 3.

if(f == 3) printf("%d\n", mXor.begin()->first);

}

return 0;

}

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

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

[入力例]
70
1 64
1 46
1 25
1 5
1 7
1 9
3
1 51
1 5
1 91
1 6
3
1 63
1 5
2 5
2 5
2 5
1 99
1 60
3
1 40
1 7
1 71
3
1 41
2 7
2 7
1 109
3
1 53
1 29
2 91
1 19
3
1 20
2 25
1 9
3
1 32
1 92
1 47
2 9
2 9
3
1 97
1 61
1 76
3
1 70
3
1 32
1 119
3
1 33
1 0
3
1 67
1 59
1 113
3
1 55
1 39
1 111
1 7
3
1 100
1 95
1 93
1 73
3

[出力例]
2
0
1
0
1
1
0
1
1
1
0
0
0
0
0

[入力例]
100
1 4282
1 7381
1 1971
1 7717
3
1 9166
1 14740
1 2856
1 5936
3
1 9121
1 16763
1 4997
1 9073
1 2740
1 3412
3
1 18735
1 3380
1 16133
3
1 7979
1 3992
2 7717
1 15625
3
1 6495
1 10890
1 8630
3
1 5937
1 2855
1 17854
1 9165
1 13490
3
1 19882
1 12257
1 10890
1 9119
3
1 19385
2 10890
1 21787
1 8272
3
1 20361
1 9119
1 14030
2 10890
1 8838
3
1 17845
1 22167
2 9119
1 17863
3
1 13961
2 9119
1 20044
2 2855
1 9074
3
1 5934
1 12072
1 15797
3
1 3120
2 5934
1 17048
1 1624
3
1 2152
1 18494
1 2740
1 17666
3
1 16868
2 2740
1 10406
3
1 13483
1 11639
2 2740
1 16260
3
1 12921
1 11414
2 14740
1 6595
3
1 17845
1 7618
1 9122
1 19740
3
1 1111
2 17845
1 1112
3

[出力例]
752
752
111
96
96
96
1
0
1
0
1
1
1
1
0
1
1
1
0
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

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

[入力例]

1 2

1 10

1 3

2 2

1 10

[出力例]

※AtCoderテストケースより

[入力例]

1 64

1 46

1 25

1 5

1 7

1 9

1 51

1 5

1 91

1 6

1 63

1 5

2 5

1 99

1 60

1 40

1 7

1 71

1 41

2 7

1 109

1 53

1 29

2 91

1 19

1 20

2 25

1 9

1 32

1 92

1 47

2 9

1 97

1 61

1 76

1 70

1 32

1 119

1 33

1 0

1 67

1 59

1 113

1 55

1 39

1 111

1 7

1 100

1 95

1 93

1 73

[出力例]

[入力例]

100

1 4282

1 7381

1 1971

1 7717

1 9166

1 14740

1 2856

1 5936

1 9121

1 16763

1 4997

1 9073

1 2740

1 3412

1 18735

1 3380

1 16133

1 7979

1 3992

2 7717

1 15625

1 6495

1 10890

1 8630

1 5937

1 2855

1 17854

1 9165

1 13490

1 19882

1 12257

1 10890

1 9119

1 19385

2 10890

1 21787

1 8272

1 20361

1 9119

1 14030

2 10890

1 8838

1 17845

1 22167

2 9119

1 17863

1 13961

2 9119

1 20044

2 2855

1 9074

1 5934

1 12072

1 15797

1 3120

2 5934

1 17048

1 1624

1 2152

1 18494

1 2740

1 17666

1 16868

2 2740

1 10406

1 13483

1 11639

2 2740

1 16260

1 12921

1 11414

2 14740

1 6595

1 17845

1 7618

1 9122

1 19740

1 1111

2 17845

1 1112

[出力例]

752

111

■参照サイト
CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)

C++の練習を兼ねて, AtCoder Beginner Contest 308 の 問題F (Vouchers) ～ 問題G (Minimum Xor Pair Query) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 308 の問題F (Vouchers) ～問題G (Minimum Xor Pair Query) を解いてみた.

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