yukicoder No.11 カードマッチ 解説

問題文

解説

まず、各マークおよび数字について各々マッチするかを調べるという方法がある。
もしこれで愚直に判定するのであれば、実行時間は$O(HNW)$。制約は、$H\leqq 10^6$、$W\leqq 10^6$、$N\leqq 10^2$なので、当然、間に合わない。
ここで、マッチしないカードについて考えてみよう。
xoxo
oooo
oooo
xoxo
たとえば、マッチするカードをoにし、マッチしないカードをxとしたとき、こんな感じになったとする。
しかし、oを右に、そして下にずらしてしまえば
xxoo
xxoo
oooo
oooo
こんな感じで、xは長方形になる。
こんな感じで、どんな取り除き方をしてもマッチしないカードを寄せたら長方形になる。
よって、マッチしないカードの枚数を求めるときは、$(W-重複を取り除いたSの要素数)*(H-重複を取り除いたKの要素数)$という計算でできる。
実際に書くときはsetで重複を消して計算をするのがいいだろう。
では、本題のマッチするカード数を求めるにはどうすればいいのか。
今回は余事象を使う。
すると、次のことが言える。
マッチするカードの枚数=カード全体-マッチしないカード
カード全体の枚数は$HW$で求められるので、マッチするカードの枚数は上記の計算式通りに求めればいいだろう。
そして、最後に手札のカードを引く。
手札のカードに重複はないし、かならずマッチしてるのでそのまま$N$を引く。
実行時間は、set処理がボトルネックとなり$O(N log N)$。よって、十分高速。
$W$および$H$が十分に大きいため、long long型を使おう。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
  ll w,h,n;cin>>w>>h>>n;
  set<int> tate,yoko;
  for(int i=0;i<n;i++){
    int s,k;cin>>s>>k;
    tate.insert(s);
    yoko.insert(k);
  }
  cout<<h*w-(w-tate.size())*(h-yoko.size())-n<<endl;
}