C++の練習を兼ねて, AtCoder Beginner Contest 176 の 問題E (Bomber) を解いてみた.
■感想.
1. 数え上げについて, 方針決めに時間かかったものの, AC版に到達できたので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 176 解説をご覧下さい.
■C++版プログラム(問題E/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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) set<int> h[303030], w[303030]; // 爆破対象: 行方向, 列方向. int main() { // 1. 入力情報取得. int H, W, M; int mhCnt = 0, mwCnt = 0; // 爆破対象の最大数(行方向, 列方向). scanf("%d %d %d", &H, &W, &M); rep(i, M){ int a, b; scanf("%d %d", &a, &b); a--, b--; h[a].insert(b); w[b].insert(a); mhCnt = max(mhCnt, (int)h[a].size()); mwCnt = max(mwCnt, (int)w[b].size()); } // 2. 最大数を持つ行, 列 を 集約. set<int> mhSet, mwSet; rep(i, 303030){ if(mhCnt == h[i].size()) mhSet.insert(i); // 行番号. if(mwCnt == w[i].size()) mwSet.insert(i); // 列番号. } // 3. 最大数を計算. int ans = mhCnt + mwCnt - 1; for(auto &p : mhSet){ bool ok = false; for(auto &q : mwSet){ // 列方向の最大数に該当する 列番号 q で, 行方向の最大数を取る 行番号 p を 含まない // ものが見つかった場合は, 終了. if(w[q].count(p) == 0){ ans++; ok = true; break; } } if(ok) break; } // 4. 出力. printf("%d\n", ans); 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 |
[入力例] 2 3 3 2 2 1 1 1 3 [出力例] 3 ※AtCoderテストケースより [入力例] 3 3 4 3 3 3 1 1 1 1 2 [出力例] 3 ※AtCoderテストケースより [入力例] 5 5 10 2 5 4 3 2 3 5 5 2 2 5 4 5 3 5 1 3 5 1 4 [出力例] 6 ※AtCoderテストケースより [入力例] 7 7 15 2 2 2 3 2 4 2 5 2 6 3 2 3 3 3 4 3 5 3 6 5 2 5 3 5 4 5 5 5 6 [出力例] 7 [入力例] 7 7 15 1 1 1 3 1 5 2 2 2 4 2 6 3 3 3 5 3 7 4 4 4 6 5 5 5 7 6 6 7 7 [出力例] 6 |
■参照サイト
AtCoder Beginner Contest 176