ABC 023 C 収集王

2015/05/13 (Wed) ABC AtCoder アドホック

問題

問題文

方針

ある行及び列に飴はいくつかるか？というのを数えておく． 次に，飴の数から，それだけの数が落ちている行/列はいくつあるかという表を作る． すると，$x$ 個の飴がある行が $a$ 行，$K-x$ 個の飴がある列が $b$ 行あったとき， 交差するところに飴がある場合を無視すれば，条件を満たすマスは $a \times b$ 個存在するということがわかる． 最後に，無視していた交差点に飴がある場合を除いていけば答えになる．

アルゴリズムは分かりやすいけど落ち着いて実装しないとバグる．

実装

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Solver
{
    static void Main()
    {
        int R, C, K;
        {
            var s = Console.ReadLine().Split(' ');
            R = int.Parse(s[0]);
            C = int.Parse(s[1]);
            K = int.Parse(s[2]);
        }
        int N = int.Parse(Console.ReadLine());
        int[] rs = new int[N];
        int[] cs = new int[N];
        int[] cntr = new int[R];
        int[] cntc = new int[C];
        int[] cntrinv = new int[N + 1];
        int[] cntcinv = new int[N + 1];
        for (int i = 0; i < N; i++)
        {
            var s = Console.ReadLine().Split(' ');
            rs[i] = int.Parse(s[0]) - 1;
            cs[i] = int.Parse(s[1]) - 1;
            cntr[rs[i]]++;
            cntc[cs[i]]++;
        }
        for (int r = 0; r < R; r++)
        {
            cntrinv[cntr[r]]++;
        }
        for (int c = 0; c < C; c++)
        {
            cntcinv[cntc[c]]++;
        }
        long ans = 0;
        for (int i = 0; i <= K; i++)
        {
            ans += cntrinv[i] * cntcinv[K - i];
        }
        for (int i = 0; i < N; i++)
        {
            int c = cntc[cs[i]] + cntr[rs[i]];
            if (c == K) ans--;
            if (c == K + 1) ans++;
        }
        Console.WriteLine(ans);
    }
}