C++の練習を兼ねて, AtCoder Beginner Contest 252 の 問題F (Bread) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説されているロジックで最小コストが計算できる点が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 252 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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 |
// 解き直し. // https://atcoder.jp/contests/abc252/editorial/3998 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using PQ = priority_queue<LL, vector<LL>, greater<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 L, a, b = 0; scanf("%d %lld", &N, &L); PQ pq; rep(i, N){ scanf("%lld", &a); pq.push(a); b += a; } // 2. L が a の 合計よりも大きい. if(L > b) pq.push(L - b); // 3. 最小のコストは？ LL ans = 0; while(pq.size() > 1){ LL s1 = pq.top(); pq.pop(); LL s2 = pq.top(); pq.pop(); ans += (s1 + s2); pq.push(s1 + s2); } // 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 |
[入力例] 5 7 1 2 1 2 1 [出力例] 16 ※AtCoderテストケースより [入力例] 3 1000000000000000 1000000000 1000000000 1000000000 [出力例] 1000005000000000 ※AtCoderテストケースより [入力例] 12 52 3 1 4 1 5 9 2 6 5 3 5 8 [出力例] 176 [入力例] 25 1040 2 23 60 67 9 77 4 99 78 96 9 6 40 91 73 6 68 73 12 7 6 2 3 54 40 [出力例] 4322 [入力例] 75 5050 19 10 36 97 97 80 12 68 20 20 84 62 71 26 110 85 15 105 64 90 108 40 119 43 14 50 68 83 43 81 37 80 96 25 90 10 23 38 7 90 46 25 120 11 96 92 18 110 22 82 79 58 26 44 117 110 105 70 34 76 78 89 111 20 23 41 86 25 113 100 29 110 59 70 39 [出力例] 30000 |
■参照サイト
AtCoder Beginner Contest 252