C++の練習を兼ねて, AtCoder Regular Contest 006 の 問題C (C – 積み重ね) を解いてみた.
■感想.
1. どこかで類題を見た記憶があったので, 探したところ, 本問も, yukicoder の No.4 おもりと天秤 に似ていることが分かった.
■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 61 62 63 |
#include <bits/stdc++.h> using namespace std; // 段ボール箱の山のリストを更新する. // @param ms: 段ボール箱のリスト. // @param w: 追加予定の段ボール. // @return ret: 段ボール箱の山のリスト. vector<vector<int>> updateMountains(vector<vector<int>> ms, int w){ // 1. 段ボールを, 既存の山に追加した場合. vector<vector<int>> ret; bool b = false; for(auto &m : ms){ if(!b && m.back() >= w){ m.push_back(w); b = true; } ret.push_back(m); } // 2. 段ボールを, 新規の山に追加した場合. if(!b){ vector<int> v; v.push_back(w); ret.push_back(v); } return ret; } int main() { // 1. 入力情報取得. int N; cin >> N; int w[N]; for(int i = 0; i < N; ++i) cin >> w[i]; // 2. 段ボールを積んでいく. vector<vector<int>> mountains; // 2-1. 1箱目を追加. vector<int> mountain; mountain.push_back(w[0]); mountains.push_back(mountain); // 2-2. 2箱目以降を追加. for(int i = 1; i < N; i++){ vector<vector<int>> lc = updateMountains(mountains, w[i]); swap(mountains, lc); } // 3. 出力. // for(auto &ms : mountains){ // for(auto &m : ms) cout << m << " "; // cout << endl; // } cout << mountains.size() << endl; 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 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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
[入力例] 5 4 3 1 2 1 [出力例(debug版)] 4 3 1 1 2 2 ※AtCoderのテストケースより [入力例] 7 93 249 150 958 442 391 25 [出力例(debug版)] 93 25 249 150 958 442 391 3 ※AtCoderのテストケースより [入力例] 4 100 100 100 100 [出力例(debug版)] 100 100 100 100 1 ※AtCoderのテストケースより [入力例] 15 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 [出力例(debug版)] 3 1 1 4 2 5 5 3 9 6 5 8 7 9 9 6 ※AtCoderのテストケースより [入力例] 25 34 12 7 89 45 90 47 3 58 79 66 19 23 50 8 11 75 39 45 67 20 25 1 81 2 [出力例(debug版)] 34 12 7 3 1 89 45 19 8 2 90 47 23 11 58 50 39 20 79 66 45 25 75 67 81 7 |