[AtCoder] ABC 176 E – Bomber
問題
方針
方針1
行と列はそれぞれ独立に選ぶことができることに注目します。 \( i \) 行目にある爆弾の個数を \( R(i) \) とし、\( j \) 列目にある爆弾の個数を \( C(j) \) とします。マス \( (i, j)\) に爆弾を置くとき、このマスに爆破対象がなければ、\( R(i) + C(j) \) 個爆破でき、爆破対象があるとき、\( R(i) + C(j) – 1 \) 個爆破できます。
したがって、行と列の最大値を持つ番号について、そのマスに爆破対象がないかどうかを調べます。
方針2
他の人のコードを見た方法です。方針1より計算量が少なく済みます。行と列に存在する爆破対象の最大値をそれぞれ、\( R, C \) とします。また、爆破対象が \( R \) 個ある行の数を \( a \) とし、爆破対象が \( C \) 個ある列の数を \( b \) とします。このとき最適な行と列の選び方は最大でも \( ab \) 通りあります。 次に \( i \) 個目の爆破対象が \( ab \) 通りの中に含まれるかどうかを調べます。含まれた数が \( ab \) 個あるとき、答えは \( R + C – 1 \) となり、そうでないとき \( R + C \) となります。
コード
方針1
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Data { int p; ll id; Data(int p, ll id) : p(p), id(id){} bool operator < (const Data &d) const { return p > d.p; } }; int main() { ll H, W, M; cin >> H >> W >> M; ll h[M], w[M]; set<ll> s; int ch[H]{}, cw[W]{}; for (int i = 0; i < M; i++) { cin >> h[i] >> w[i]; h[i]--; w[i]--; s.insert(h[i] * W + w[i]); ch[h[i]]++; cw[w[i]]++; } vector<Data> dh, dw; for (int i = 0; i < H; i++) { dh.push_back(Data(ch[i], i)); } for (int i = 0; i < W; i++) { dw.push_back(Data(cw[i], i)); } sort(dh.begin(), dh.end()); sort(dw.begin(), dw.end()); vector<Data> dh_max, dw_max; int maxH = dh[0].p; int maxW = dw[0].p; for (int i = 0; i < H; i++) { if (maxH == dh[i].p) { dh_max.push_back(dh[i]); } else { break; } } for (int i = 0; i < W; i++) { if (maxW == dw[i].p) { dw_max.push_back(dw[i]); } else { break; } } ll ans = dh_max[0].p + dw_max[0].p - 1; for (int i = 0; i < dh_max.size(); i++) { for (int j = 0; j < dw_max.size(); j++) { ll id = dh_max[i].id * W + dw_max[j].id; if (s.count(id) == 0) { cout << ans + 1 << "\n"; return 0; } } } cout << ans << "\n"; return 0; }
方針2
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int H, W, M; cin >> H >> W >> M; int h[M], w[M]; int ch[H]{}, cw[W]{}; int r_max = 0; int c_max = 0; for (int i = 0; i < M; i++) { cin >> h[i] >> w[i]; h[i]--; w[i]--; ch[h[i]]++; cw[w[i]]++; r_max = max(r_max, ch[h[i]]); c_max = max(c_max, cw[w[i]]); } ll cnt_r = 0; ll cnt_c = 0; for (int i = 0; i < H; i++) { if (r_max == ch[i]) cnt_r++; } for (int i = 0; i < W; i++) { if (c_max == cw[i]) cnt_c++; } ll v = cnt_r * cnt_c; for (int i = 0; i < M; i++) { if (ch[h[i]] == r_max && cw[w[i]] == c_max) { v--; } } if (v == 0) { cout << r_max + c_max - 1<< "\n"; } else { cout << r_max + c_max << "\n"; } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません