C++の練習を兼ねて, AtCoder Beginner Contest 060 の 問題C(Sentou), 問題D(Simple Knapsack) を解いてみた.
■感想.
1. 問題C は, 解答方針が, 見つかったので, 解答出来た.
2. 問題D は, 解答方針が見えなかったので, 解説を読んでから, その日本語を, プログラムに翻訳したが, なかなか大変だった(コンパクトに纏めることが出来なかった).
本家のサイトAtCoder Regular Contest 073 Editorialをご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) typedef long long LL; int main() { // 1. 入力情報取得. LL N, T; cin >> N >> T; LL totalTime = T; // 2. お湯の出続ける時間をカウント. // 前回スイッチを押した時刻. LL bti = 0; FOR(i, 0, N) { // 今回スイッチを押した時刻. LL cti; cin >> cti; if(cti > bti) totalTime += min(cti - bti, T); bti = cti; } // 3. 出力 ~ 後処理. cout << totalTime << endl; return 0; } |
■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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
// 解き直し. // AtCoder Regular Contest 073 Editorial // https://atcoder.jp/img/arc073/editorial.pdf #include <bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. LL N, W; cin >> N >> W; // 解説通り, 4種類の重さのものを, それぞれ, いくつ選ぶかを把握するために使う. vector<LL> v1, v2, v3, v4; // w1 記録用. LL w1 = 0; FOR(i, 0, N) { LL wi, vi; cin >> wi >> vi; if(i == 0) w1 = wi; if(wi == w1 + 0) v1.push_back(vi); if(wi == w1 + 1) v2.push_back(vi); if(wi == w1 + 2) v3.push_back(vi); if(wi == w1 + 3) v4.push_back(vi); } // 2. バッグの価値を降順sort. sort(v1.begin(), v1.end(), greater<LL>()); sort(v2.begin(), v2.end(), greater<LL>()); sort(v3.begin(), v3.end(), greater<LL>()); sort(v4.begin(), v4.end(), greater<LL>()); // 3. バッグの価値の累積和を作成. int l1, l2, l3, l4; l1 = v1.size(); l2 = v2.size(); l3 = v3.size(); l4 = v4.size(); // cout << l1 << " " << l2 << " " << l3 << " " << l4 << endl; LL a1[l1 + 1] = {}; LL a2[l2 + 1] = {}; LL a3[l3 + 1] = {}; LL a4[l4 + 1] = {}; a1[1] = (l1 > 0) ? v1[0] : 0; a2[1] = (l2 > 0) ? v2[0] : 0; a3[1] = (l3 > 0) ? v3[0] : 0; a4[1] = (l4 > 0) ? v4[0] : 0; FOR(i, 2, l1 + 1) a1[i] += (v1[i - 1] + a1[i - 1]); FOR(i, 2, l2 + 1) a2[i] += (v2[i - 1] + a2[i - 1]); FOR(i, 2, l3 + 1) a3[i] += (v3[i - 1] + a3[i - 1]); FOR(i, 2, l4 + 1) a4[i] += (v4[i - 1] + a4[i - 1]); // FOR(i, 0, l1 + 1) cout << a1[i] << " "; // FOR(i, 0, l2 + 1) cout << a2[i] << " "; // FOR(i, 0, l3 + 1) cout << a3[i] << " "; // FOR(i, 0, l4 + 1) cout << a4[i] << " "; // 4. バッグに入れた物の価値の総和を最大化するための試行錯誤. LL maxValue = 0; FOR(i1, 0, l1 + 1) { FOR(i2, 0, l2 + 1) { FOR(i3, 0, l3 + 1) { FOR(i4, 0, l4 + 1) { // v1 から i1個, v2 から i2個, v3 から i3個, v4 から i4個 選んで, // 重さの和が, W を 超えていたら, スキップ. LL w = w1 * i1 + (w1 + 1) * i2 + (w1 + 2) * i3 + (w1 + 3) * i4; // cout << i1 << " " << i2 << " " << i3 << " " << i4 << " " << w << endl; if(w > W) continue; // 最大値更新. LL v = a1[i1] + a2[i2] + a3[i3] + a4[i4]; if(maxValue < v) maxValue = v; } } } } // 5. 出力 ~ 後処理. cout << maxValue << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 060