C++の練習を兼ねて, AtCoder Beginner Contest 058 の 問題C(怪文書 / Dubious Document), 問題D(井井井 / ###) を解いてみた.
■感想.
1. 問題C, 問題D ともに, 時間はかかったもの(※特に, 問題D)の, 解説見ずに解けたので, 良かったと思う.
2. 問題D は, 最初, 同じ長方形を複数回カウントしてよいものと理解したが, 以下の入力値(本家のサイトにあるもの)で,
確認したところ, 誤答となったので, “同じ長方形は, ただ一度だけカウント” すると理解して, ロジックを組み直したものである.
1 2 3 4 5 6 7 8 9 10 11 12 |
[入力値] 6 5 -790013317 -192321079 95834122 418379342 586260100 802780784 -253230108 193944314 363756450 712662868 735867677 [出力値] x方向: 802780784 - (-790013317) = 1592794101 y方向: 735867677 - (-253230108) = 989097785 -> 1575429117260166285 -> (x軸中央4本の選び方)2の4乗 × (y軸中央3本の選び方)2の3乗 = 128倍して, 201654927009301284480 -> MOD(1000000007) すると, 716805301 ※正答は, 835067060 なので, 誤答である. |
本家のサイトABC058 / ARC071 解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. int n; cin >> n; vector<map<char, int>> vm; FOR(i, 0, n) { string s; cin >> s; map<char, int> mp; FOR(j, 0, 26) mp['a' + j] = 0; FOR(j, 0, s.size()) mp[s[j]]++; vm.push_back(mp); } // 2. 条件を満たす最長の文字列のうち、辞書順で最小のものを作成. // 2-1. 各文字列で出現した a-z の最小回数を調べる必要がある. map<char, int> minMap; FOR(i, 0, 26) minMap['a' + i] = 9999; for(auto itr = vm.begin(); itr != vm.end(); ++itr) { for(auto &m : *itr) { auto k = m.first; auto v = m.second; // cout << k << " " << v << endl; if(minMap[k] > v) minMap[k] = v; } } // for(auto &p : minMap) cout << p.first << " " << p.second << endl; // 2-2. 1回以上出現した各文字を, a-z の順に結合. string ans; for(auto &p : minMap) { string s(p.second, p.first); ans += s; } // 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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) typedef long long LL; const LL MOD = 1000000007; int main() { // 1. 入力情報取得. LL N, M; cin >> N >> M; LL x[N + 1] = {}; LL y[M + 1] = {}; FOR(i, 1, N + 1) cin >> x[i]; FOR(i, 1, M + 1) cin >> y[i]; // 2. x, y軸方向で, 一行当たりの面積和を計算. // 例) // N = 7 の 場合, 区間[1, 7] における棒の置き方を確認する. // 長さ1 … 区間[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7] で, 6通り. // 長さ2 … 区間[1, 3], [2, 4], [3, 5], [4, 6], [5, 7] で, 5通り. // 長さ3 … 区間[1, 4], [2, 5], [3, 6], [4, 7] で, 4通り. // 長さ4 … 区間[1, 5], [2, 6], [3, 7] で, 3通り. // 長さ5 … 区間[1, 6], [2, 7] で, 2通り. // 長さ6 … 区間[1, 7] で, 1通り. // // -> 以上の棒の置き方から, 各区間に出現する棒の本数を数えることにする. // 区間[1, 2] … 6回 (DP[1]と置く) // 区間[2, 3] … 10回 (DP[2]と置く) // 区間[3, 4] … 12回 (DP[3]と置く) // 区間[4, 5] … 12回 (DP[4]と置く) // 区間[5, 6] … 10回 (DP[5]と置く) // 区間[6, 7] … 6回 (DP[6]と置く) // // -> 上記までの調査から, 以下の関係式が判明した. // DP[0] = 0, DP[i] = (N - i) + DP[i - 1] - (i - 1) // 2-1. x軸方向について, 一行当たりの面積和を計算. // 出現本数を保管. LL DPX[N + 1] = {}; FOR(i, 1, N) { DPX[i] = (N - i) + DPX[i - 1] - (i - 1); DPX[i] %= MOD; } // FOR(i, 1, N) cout << DPX[i] << endl; // 面積和を保管. LL AreaX = 0; FOR(i, 2, N + 1) { AreaX += (x[i] - x[i - 1]) * DPX[i - 1]; AreaX %= MOD; } // cout << AreaX << endl; // 2-2. y軸方向について, 一列当たりの面積和を計算. // 出現本数を保管. LL DPY[M + 1] = {}; FOR(i, 1, M) { DPY[i] = (M - i) + DPY[i - 1] - (i - 1); DPY[i] %= MOD; } // FOR(i, 1, M) cout << DPY[i] << endl; // 面積和を保管. LL AreaY = 0; FOR(i, 2, M + 1) { AreaY += (y[i] - y[i - 1]) * DPY[i - 1]; AreaY %= MOD; } // cout << AreaY << endl; // 3. すべての長方形についての面積の総和(MOD版) LL ans = AreaX; ans *= AreaY; ans %= MOD; // 4. 出力 ~ 後処理. cout << ans << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 058