C - 収集王 / AtCoderBeginnerContest#023
#include <iostream> #include <vector> using namespace std; #define MAX 100000 typedef pair<int,int> P_II; void Solve(int r, int c, int k) { int n, rr, cc, row[MAX+1]={0}, col[MAX+1]={0}, count_row[MAX+1]={0}, count_col[MAX+1]={0}; long long answer=0; vector<P_II> data(MAX); cin >> n; for (int i=0; i<n; ++i) { cin >> rr >> cc; ++row[rr-1]; ++col[cc-1]; data[i]=make_pair(cc-1,rr-1); } for (int i=0; i<c; ++i) ++count_col[ col[i] ]; for (int j=0; j<r; ++j) ++count_row[ row[j] ]; for (int i=0; i<=k; ++i) answer+=count_row[i]*count_col[k-i]; for (int i=0; i<n; ++i) { P_II p_ii=data[i]; long long count=col[p_ii.first]+row[p_ii.second]; if (count == k) --answer; else if (count == k+1) ++answer; } cout << answer << endl; } int main(void) { int r, c, k; cin >> r >> c >> k; Solve(r,c,k); return 0; }
列と行を足した答えがkになる数を数える。
起点では重複しているのでkの場合は-1、k+1の場合は+1。
〜了〜