[AtCoder] ABC 176 E – Bomber

2020年8月23日2020年12月13日

問題

方針

方針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;
}