山傘のプログラミング勉強日記[Java & Unity]

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.11 カードマッチ [レベル: 2]

組み合わせの問題

f:id:yamakasa3:20180610023444p:plain

No.11 カードマッチ - yukicoder

考え方

手札にある数字の種類をカウントし、その値を a とします。

次に、手札のマーク i の枚数をカウントします。その値を  b_i とします。

手札に存在しないマークの数を c とします。

これらの値を計算することで答えが導けます。

コード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Exec0011 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int W = scan.nextInt();
        int H = scan.nextInt();
        int N = scan.nextInt();

        long ans = 0;
        int []a = new int[H + 1];
        Arrays.fill(a, 0);
        // 隣接リスト
        Map<Integer, ArrayList<Integer>> map =
                new TreeMap<Integer, ArrayList<Integer>>();
        for(int i = 0; i < N; i++) {
            int S = scan.nextInt();
            int K = scan.nextInt();
            a[K] = 1;
            if(!map.containsKey(S)) {
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add(K);
                map.put(S, list);
            }else {
                map.get(S).add(K);
            }
        }
        scan.close();
        int cnt = 0;
        for(int i = 1 ; i <= H; i++) {
            if(a[i] == 1) {
                cnt ++;
            }
        }
        for(int i = 1; i <= W; i++) {
            if(map.containsKey(i)) {
                ans += (long) (H - map.get(i).size());
            }else {
                ans += (long) cnt;
            }
        }
        System.out.println(ans);
    }
}