C++の練習を兼ねて, AtCoder Beginner Contest 062 の 問題C(Chocolate Bar), 問題D(3N Numbers) を解いてみた.
■感想.
1. 両問題とも, 解答方針が間違えていたので, 解けなかった.
2. 問題C では, 長方形を, 同じ方向に3分割するパターンが, H or W が 3の倍数という先入観で解いたため, 正答に至らなかった.
-> 例として, [入力例] 5 13 に対し, WA版だと 8, AC版だと, 5 というように出力されるので, WA版のロジック誤りについて, 具体的に理解できた.
3. 問題D では, 中央N項の数列に着目して, 数列a’ の前半N要素の総和, 数列a’ の後半N要素の総和 を 考えてみたが, 上手く行かなかったので, 解答通りに実装し直した.
※LL ans = -99999999999; からスタートして, 最大値を計算しようとすると, 1_10.txt, 2_02.txt で, Wrong Answerとなるので, LL ans = -100000000000000; (10の5乗 × 10の9乗 の符号を マイナス にした数)からスタートして, 最大値を計算する必要があるので注意.
4. 優先順位付きキュー std::priority_queue を使う練習が出来たと思われる(※存在を知らなかった(汗)).
本家のサイトABC #062 / ARC #074 Editorialをご覧下さい.
■C++版プログラム(問題C/WA版).
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 |
// 1_04.txt, 1_09.txt で, Wrong Answer となった. #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define abs(x) ((x > 0) ? x : (-(x))) typedef long long LL; int main() { // 1. 入力情報取得. LL H, W; cin >> H >> W; // 2. Smax - Smin を 計算. LL ans = 99999999999; // 2-1. H or W が 3 の倍数 なら, 0. if(H % 3 == 0 || W % 3 == 0) ans = 0; // 2-2. H and W が 3 の倍数でない なら, 以下のような分岐. if(H * W % 3 != 0) { if(H % 2 == 0) { FOR(i, 1, W) { LL Sa = H * i; // H × i の 長方形. LL Sb = H / 2 * (W - i); // (H / 2) × (W - i) の 長方形. ans = min(ans, abs(Sa - Sb)); } } if(W % 2 == 0) { FOR(i, 1, H) { LL Sa = W * i; // W × i の 長方形. LL Sb = W / 2 * (H - i); // (W / 2) × (H - i) の 長方形. ans = min(ans, abs(Sa - Sb)); } } // テストケース 1_04.txt, 1_09.txt 対応. if(H % 2 != 0 && W % 2 != 0) { FOR(i, 1, W) { LL Sa = H * i; // H × i の 長方形. LL Sb = H / 2 * (W - i); // (H / 2) × (W - i) の 長方形. LL Sc = (H / 2 + 1) * (W - i); // (H / 2 + 1) × (W - i) の 長方形. LL Smax = max(Sa, Sb); Smax = max(Smax, Sc); LL Smin = min(Sa, Sb); Smin = min(Smin, Sc); ans = min(ans, abs(Smax - Smin)); } FOR(i, 1, H) { LL Sa = W * i; // W × i の 長方形. LL Sb = W / 2 * (H - i); // (W / 2) × (H - i) の 長方形. LL Sc = (W / 2 + 1) * (H - i); // (W / 2 + 1) × (H - i) の 長方形. LL Smax = max(Sa, Sb); Smax = max(Smax, Sc); LL Smin = min(Sa, Sb); Smin = min(Smin, Sc); ans = min(ans, abs(Smax - Smin)); } } } // 4. 出力 ~ 後処理. cout << ans << endl; return 0; } |
■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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
// 解き直し. // ABC #062 / ARC #074 Editorial // https://atcoder.jp/img/arc074/editorial.pdf #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define abs(x) ((x > 0) ? x : (-(x))) typedef long long LL; int main() { // 1. 入力情報取得. LL H, W; cin >> H >> W; // 2. Smax - Smin を 計算(4ケース確認). LL ans = 99999999999; // 2-1. 縦方向で, 3分割するパターン. FOR(ha, 1, H) { LL Sa = ha * W; // ha × W の 長方形. LL hb = (H - ha) / 2; LL Sb = hb * W; // hb × W の 長方形. LL hc = H - ha - hb; LL Sc = hc * W; // hc × W の 長方形. LL Smax = max(Sa, Sb); Smax = max(Smax, Sc); LL Smin = min(Sa, Sb); Smin = min(Smin, Sc); ans = min(ans, abs(Smax - Smin)); } // 2-2. 縦方向で, 2分割し, B, C を横方向で, 2分割するパターン. FOR(ha, 1, H) { LL Sa = ha * W; // ha × W の 長方形. LL wb = W / 2; LL hbc = H - ha; LL Sb = hbc * wb; // hbc × wb の 長方形. LL wc = W - wb; LL Sc = hbc * wc; // hbc × wb の 長方形. LL Smax = max(Sa, Sb); Smax = max(Smax, Sc); LL Smin = min(Sa, Sb); Smin = min(Smin, Sc); ans = min(ans, abs(Smax - Smin)); } // 2-3. 2-1. で 縦横入れ替えしたパターン. FOR(wa, 1, W) { LL Sa = H * wa; // H × wa の 長方形. LL wb = (W - wa) / 2; LL Sb = H * wb; // H × wb の 長方形. LL wc = W - wa - wb; LL Sc = H * wc; // H × wc の 長方形. LL Smax = max(Sa, Sb); Smax = max(Smax, Sc); LL Smin = min(Sa, Sb); Smin = min(Smin, Sc); ans = min(ans, abs(Smax - Smin)); } // 2-4. 2-2. で 縦横入れ替えしたパターン. FOR(wa, 1, W) { LL Sa = H * wa; // H × wa の 長方形. LL hb = H / 2; LL wbc = W - wa; LL Sb = hb * wbc; // hb × wbc の 長方形. LL hc = H - hb; LL Sc = hc * wbc; // hc × wbc の 長方形. LL Smax = max(Sa, Sb); Smax = max(Smax, Sc); LL Smin = min(Sa, Sb); Smin = min(Smin, Sc); ans = min(ans, abs(Smax - Smin)); } // 4. 出力 ~ 後処理. cout << ans << endl; return 0; } |
■C++版プログラム(問題D/WA版).
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 |
// 1_03.txt, 1_05.txt, 1_10.txt - 1_11.txt, 1_13.txt, 1_16.txt - 1_23.txt, 2_02.txt - 2_03.txt // 2_05.txt, 2_08.txt - 2_15.txt で, Wrong Answer となった. #include <bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) #define FORR(i, a, b) for(LL i = (a); i >= (b); --i) int main() { // 1. 入力情報取得. LL N; cin >> N; LL As[N], Am[N], Ae[N]; LL AsTotal[N + 1] = {}; LL AeTotal[N + 1] = {}; FOR(i, 0, N) { LL ai; cin >> ai; // 数列a の 前半N項. As[i] = ai; // 数列a の 前半N項の総和 を保存. AsTotal[0] += ai; } FOR(i, 0, N) cin >> Am[i]; // 数列a の 中央N項. FOR(i, 0, N) { LL ai; cin >> ai; // 数列a の 後半N項. Ae[i] = ai; // 数列a の 後半N項の総和 を保存. AeTotal[N] += ai; } // 2. sort. // As … 昇順sort. // Am … sort無し. // Ae … 降順sort. sort(As, As + N); sort(Ae, Ae + N, greater<LL>()); // FOR(i, 0, N) cout << As[i] << " "; // FOR(i, 0, N) cout << Am[i] << " "; // FOR(i, 0, N) cout << Ae[i] << " "; // 3. 残った数列a'について, スコアを確認. // 3-1. 数列a' の前半N要素の総和を, 順次保存. LL minAs = As[0]; FOR(i, 1, N + 1) { // Am[i - 1] が, minAs よりも大きいか確認. if(Am[i - 1] > minAs) { AsTotal[i] = AsTotal[i - 1] + Am[i - 1] - minAs; minAs = max(minAs, As[i]); minAs = min(minAs, Am[i - 1]); } else { AsTotal[i] = AsTotal[i - 1]; } // cout << i << " " << Am[i - 1] << " " << minAs << " " << AsTotal[i - 1] << " -> " << AsTotal[i] << endl; } // 3-2. 数列a' の後半N要素の総和を, 順次保存. LL maxAe = Ae[0]; FORR(i, N - 1, 0) { // Am[i] が, maxAe よりも小さいか確認. if(Am[i] < maxAe) { AeTotal[i] = AeTotal[i + 1] + Am[i] - maxAe; maxAe = min(maxAe, Ae[N - i]); maxAe = max(maxAe, Am[i]); } else { AeTotal[i] = AeTotal[i + 1]; } } // FOR(i, 0, N + 1) cout << AsTotal[i] << " "; // FOR(i, 0, N + 1) cout << AeTotal[i] << " "; // 4. 出力 ~ 後処理. LL ans = -99999999999; FOR(i, 0, N) ans = max(ans, AsTotal[i] - AeTotal[i]); 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 |
// 解き直し. // ABC #062 / ARC #074 Editorial // https://atcoder.jp/img/arc074/editorial.pdf #include <bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) #define FORR(i, a, b) for(LL i = (a); i >= (b); --i) int main() { // 1. 入力情報取得. LL N; cin >> N; // How can I create Min stl priority_queue? // https://stackoverflow.com/questions/2439283/how-can-i-create-min-stl-priority-queue priority_queue<LL, vector<LL>, greater<LL>> Qs; LL Am[N]; priority_queue<LL> Qe; LL QsTotal[N + 1] = {}; LL QeTotal[N + 1] = {}; FOR(i, 0, N) { LL ai; cin >> ai; // 数列a の 前半N項. Qs.push(ai); // 数列a の 前半N項の総和 を保存. QsTotal[0] += ai; } FOR(i, 0, N) cin >> Am[i]; // 数列a の 中央N項. FOR(i, 0, N) { LL ai; cin >> ai; // 数列a の 後半N項. Qe.push(ai); // 数列a の 後半N項の総和 を保存. QeTotal[N] += ai; } // 2. 数列a の 中央N項 について, 順次確認. // 2-1. 数列a' の前半N要素の総和を, 順次保存. FOR(i, 0, N) { LL ai = Am[i]; Qs.push(ai); QsTotal[i + 1] = QsTotal[i] + ai - Qs.top(); Qs.pop(); } // 2-2. 数列a' の後半N要素の総和を, 順次保存. FORR(i, N - 1, 0) { LL ai = Am[i]; Qe.push(ai); QeTotal[i] = QeTotal[i + 1] + ai - Qe.top(); Qe.pop(); } // FOR(i, 0, N + 1) cout << QsTotal[i] << " "; // FOR(i, 0, N + 1) cout << QeTotal[i] << " "; // 3. 出力 ~ 後処理. // LL ans = -99999999999; // 1_10.txt, 2_02.txt で, Wrong Answer. LL ans = -100000000000000; FOR(i, 0, N + 1) ans = max(ans, QsTotal[i] - QeTotal[i]); cout << ans << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 062