ABC045-D：すぬけ君の塗り絵 / Snuke's Coloring

問題

https://beta.atcoder.jp/contests/abc045/tasks/arc061_b

考え方

黒く塗る点は N 個しかないので、 N 個の点に着目する。

3 * 3 のマスに含まれる数を数えるとき、ある黒く塗る点 (i, j) は自身を含めて周囲 9 マスにしか影響を及ぼさない。

よって影響のあるマスを数を数えばよい。3 * 3 マスの数え上げに影響のあるマスは高々 9N である。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            long h = in.nextLong(), w = in.nextLong();
            int n = in.nextInt();
            int[] a = new int[n];
            int[] b = new int[n];

            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
                b[i] = in.nextInt();
            }

            Map<P, Integer> map = new HashMap<>();

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 9; j++) {
                    int mh = a[i] + mh9[j];
                    int mw = b[i] + mw9[j];

                    if (2 <= mh && mh < h && 2 <= mw && mw < w) {
                        map.merge(new P(mh, mw), 1, Integer::sum);
                    }
                }
            }

            TreeMap<Long, Long> ans = new TreeMap<>();
            ans.put(0L, (h-2)*(w-2));
            for (long i = 1L; i <= 9; i++) {
                ans.put(i, 0L);
            }

            for (long count : map.values()) {
                ans.merge(0L, -1L, Long::sum);
                ans.merge(count, 1L, Long::sum);
            }

            for (long i : ans.values()) {
                out.println(i);
            }
        }

ポイント

• 数え上げる対象を別に対応させる
• 要素をまとめる

類題

D - 連結 / Connectivity
要素をまとめる考え方は似ています。

雑記

これ系苦手な感じがある...