C++の練習を兼ねて, AtCoder Beginner Contest 246 の 問題C (Coupon) ～ 問題D (2-variable Function) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達出来たと思う.
2. 個人的には, 二分探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 246 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using PQ = priority_queue<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--) int main(){ // 1. 入力情報. int N; LL K, X; scanf("%d %lld %lld", &N, &K, &X); PQ pq; rep(i, N){ LL a; scanf("%lld", &a); pq.push(a); } // 2. 商品価格の更新. while(K && !pq.empty()){ // 商品を取得. LL a = pq.top(); pq.pop(); // 終了条件. if(a < X) break; // クーポン適用. LL q = min(K, a / X); a -= q * X; K -= q; // 戻し. if(a > 0) pq.push(a); } // 3. 集計. LL ans = 0; while(!pq.empty()){ // 商品を取得. LL a = pq.top(); pq.pop(); // 次へ. if(--K > 0) continue; // 金額集計. ans += a; } // 4. 出力. printf("%lld\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
[入力例] 5 4 7 8 3 10 5 13 [出力例] 12 ※AtCoderテストケースより [入力例] 5 100 7 8 3 10 5 13 [出力例] 0 ※AtCoderテストケースより [入力例] 20 815 60 2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202 [出力例] 112 ※AtCoderテストケースより [入力例] 10 15 32 7 13 23 84 77 110 57 89 57 52 [出力例] 110 [入力例] 30 25 777 661 1309 1076 501 710 649 539 792 236 734 880 829 1067 1242 822 1260 798 264 1205 1294 829 513 993 822 583 1151 1186 140 762 669 [出力例] 6000 |
■C++版プログラム(問題D／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
// 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. 3 乗が N 以下のもの. int p = 0; while((LL)p * (LL)p * (LL)p <= N) ++p; // 3. 評価関数. auto f = [&](LL a, LL b) -> bool { // 3-1. 数式計算. LL X = (a + b) * (a * a + b * b); // 3-2. 判定結果. return (X < N); }; // 4. 区間[0, p] で 確認. LL ans = 1e18 + 1; rep(i, p + 1){ // 4-1. 二分探索で確認してみる. LL l = -1, h = (LL)(2 * p + 1), m, a = (LL)i; while(l + 1 < h){ LL m = (h + l) >> 1; if(f(a, m)) l = m; else h = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } // 4-2. 最小値更新. ans = min(ans, (a + h) * (a * a + h * h)); } // 5. 出力. printf("%lld\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
[入力例] 9 [出力例] 15 ※AtCoderテストケースより [入力例] 0 [出力例] 0 ※AtCoderテストケースより [入力例] 999999999989449206 [出力例] 1000000000000000000 ※AtCoderテストケースより [入力例] 123 [出力例] 125 [入力例] 2022 [出力例] 2048 [入力例] 20220622 [出力例] 20221245 [入力例] 202204022100 [出力例] 202204033115 [入力例] 314159265358979323 [出力例] 314159265359236485 |
■参照サイト
AtCoder Beginner Contest 246