C++の練習を兼ねて, AtCoder Beginner Contest 056 の 問題C(Go Home), 問題D(No Need) を解いてみた.
■感想.
1. 問題C, 問題D ともに, 時間はかかったもの(※特に, 問題D)の, 解説見ずに解けたので, 良かったと思う.
2. 当方の解答方針は, 入力値N(カードの枚数), K(よい集合の判定条件) を, 再帰的に, どんどん縮小していく方針を採用した.
本家のサイトARC070 / ABC056 解説をご覧下さい.
■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; typedef long long LL; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. LL X; cin >> X; // 2. カンガルーの家に到着する最小の時刻を計算. // 移動距離の総和を計算していき, X 以上のときに, 抜ける. // -> dist と X の 差分に相当する時刻 dist - X において, 移動しないを選択すればよいので最小のはず. // n(n + 1) / 2 >= 10 の 9乗 を満たす n は, 44720.8 … なので, 44721 まで確認すれば十分のはず. LL dist = 0; LL ans = 0; FOR(i, 1, 44722) { dist += i; ans = i; if(dist >= X) break; } // 3. 出力 ~ 後処理. cout << ans << endl; return 0; } |
■C++版プログラム(問題D/WA版, 2_042.txt で, Wrong Answer).
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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) typedef long long LL; // 不要なカードの枚数を調査し, 返却. // @param v: カードに書かれている数字の集合. // @param K: カードの部分集合に関する判定基準. // @return ans: 不要なカードの枚数. LL noNeedCards(vector<LL> &v, LL K) { // 1-1. K が ゼロ未満 の 場合は, v に 保管したカードの枚数だけ不要なので, それを出力. if(K <= 0) return v.size(); // 1-2. v について, Σvi を 確認し, K を 超えるときの vi を 把握. LL total = 0; LL index = 0; // cout << K << endl; FOR(i, 0, v.size()) { total += v[i]; index = i; // cout << index << " " << v[i] << " " << total << " " << endl; if(total >= K) break; } // 1-3. K に 満たない場合は, v に 保管したカードの枚数だけ不要なので, それを出力. if(total < K) return v.size(); // 1-4. K に 等しい場合は, すべてのカードが必要となるので, 不要なカードは, 0枚. if(total == K) return 0; // 1-5. K より 大きい場合は, 本関数を再帰呼び出しする. K -= v[index]; v.resize(index); return noNeedCards(v, K); } int main() { // 1. 入力情報取得. LL N, K; cin >> N >> K; vector<LL> v; FOR(i, 0, N) { // ai >= K は, Skip. LL a; cin >> a; if(a < K) v.push_back(a); } // 2. K より 大きい場合は, 以下の内容を調べることになる. // 2-1. v を 昇順sort. sort(v.begin(), v.end()); // 2-2. 不要なカードの枚数を調べる. LL ans = noNeedCards(v, K); // 3. 出力 ~ 後処理. cout << ans << 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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) typedef long long LL; // 不要なカードの枚数を調査し, 返却. // @param v: カードに書かれている数字の集合. // @param K: カードの部分集合に関する判定基準. // @return ans: 不要なカードの枚数. LL noNeedCards(vector<LL> &v, LL K) { // 1-1. K が ゼロ未満 の 場合は, v に 保管したカードの枚数だけ不要なので, それを出力. // if(K <= 0) return v.size(); // 2_042.txt の Wrong Answer対策. if(K < 0) return v.size(); // 1-2. v の 要素で, K以上を除外. // 0_002.txt の Wrong Answer対策. vector<LL> lv; for(auto &p : v) if(p < K) lv.push_back(p); // p >= K は, Skip. // 1-3. v について, Σvi を 確認し, K を 超えるときの vi を 把握. LL total = 0; LL index = 0; // cout << K << endl; FOR(i, 0, lv.size()) { total += lv[i]; index = i; // cout << index << " " << lv[i] << " " << total << " " << endl; // [input] // 4 5 // 1 2 3 4 // // [output] // 5 // 0 1 1 // 1 2 3 // 2 3 6 // 2 // 0 1 1 // 1 // -> 1 2 3 4 の 4 について, noNeedCards関数で, 評価される前に, // Skipしてしまうことが, Wrong Answer の 原因と推定される. // -> よって, 以下のif文をコメントアウトした. // if(total >= K) break; // 2_042.txt の Wrong Answer対策. } // 1-4. K に 満たない場合は, lv に 保管したカードの枚数だけ不要なので, それを出力. if(total < K) return lv.size(); // 1-5. K に 等しい場合は, すべてのカードが必要となるので, 不要なカードは, 0枚. if(total == K) return 0; // 1-6. K より 大きい場合は, 本関数を再帰呼び出しする. K -= lv[index]; lv.resize(index); return noNeedCards(lv, K); } int main() { // 1. 入力情報取得. LL N, K; cin >> N >> K; vector<LL> v; FOR(i, 0, N) { // ai >= K は, Skip. LL a; cin >> a; if(a < K) v.push_back(a); } // 2. K より 大きい場合は, 以下の内容を調べることになる. // 2-1. v を 昇順sort. sort(v.begin(), v.end()); // 2-2. 不要なカードの枚数を調べる. LL ans = noNeedCards(v, K); // 3. 出力 ~ 後処理. cout << ans << endl; return 0; } |
■デバッグ出力例(問題D/AC版).
[入力例] について, 最初から3つ目までを, 本家のサイトから, 抜粋している.
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 |
[入力例] 3 6 1 4 3 [出力例] 6 0 1 1 1 3 4 2 4 8 2 0 1 1 1 -> 上記, 1 が解答となる. [入力例] 5 400 3 1 4 1 5 [出力例] 400 0 1 1 1 1 2 2 3 5 3 4 9 4 5 14 5 -> 上記, 5 が解答となる. [入力例] 6 20 10 4 3 10 25 2 [出力例] 20 0 2 2 1 3 5 2 4 9 3 10 19 4 10 29 10 0 2 2 1 3 5 2 4 9 3 -> 上記, 3 が解答となる. [入力例] 4 5 1 2 3 4 [出力例] 5 0 1 1 1 2 3 2 3 6 3 4 10 1 0 -> 上記, 0 が解答となる. [入力例] 5 10 1 3 5 7 9 [出力例] 10 0 1 1 1 3 4 2 5 9 3 7 16 4 9 25 1 0 -> 上記, 0 が解答となる. [入力例] 8 16 1 2 3 4 5 16 16 16 [出力例] 16 0 1 1 1 2 3 2 3 6 3 4 10 4 5 15 5 -> 上記, 5 が解答となる. |
■参照サイト
AtCoder Beginner Contest 056