AtCoder Beginner Contest ABC023 C - 収集王

C - 収集王

問題へのリンク

解説

行にある点の個数が個のとき、列が個のとき和がになりそうなところから考察を進める。

ここで、列が個の列の個数を追加すれば良さそうだが、ここに罠がある。その列に点があるときはその列は、点がないときはであることが条件であり、そのように単純に数えることができない。

よって、まず個の点を持つ列の個数を追加した後、実際の頂点を見て、その列が個だったら削除し、だったら追加するというアルゴリズムでうまく数えることができる。

計算量は。

実装

• 提出へのリンク

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)

int H, W, K, N;
int x, y;
int mpy[100050];
vector<pair<int, int>> v[100050], vv[100050];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> H >> W >> K;
    cin >> N;
    rep(i,N){
        cin >> x >> y;
        x--;
        y--;
        v[x].emplace_back(x,y);
        vv[y].emplace_back(x,y);
    }
    rep(j,W)mpy[vv[j].size()]++;
    long long ans = 0;
    rep(i,H){
        int r = v[i].size();
        int add = mpy[K-r];
        for(auto p: v[i]){
            int cnty = vv[p.second].size();
            if(cnty == K-r)add--;
            if(cnty == K-r+1)add++;
        }
        ans += add;
    }
    cout << ans << endl;
}