日記

のみろぐ

主に競プロ日記です

ABC045-D「すぬけ君の塗り絵 」

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

考察

  • 愚直に考えると、$HW$の盤面を用意してすべての座標に対し$9 \times 9$を全探索することになる。しかし、$HW$の最大値は$10^{18}$となるため全探索では間に合わない。
  • ここで入力の制約に注目すると、$N \leq 10^{5}$となっている。
  • 別に$HW$の座標全部見なくても関係のある部分だけ見ればいいんじゃね?ってところに気づく。
  • あと、なんか$9\times9が$白いマスのみの個数がたくさんありそう。黒マスを含む塊の個数はそれほど多くなさそう。
  • 答えを求めるのに関係のありそうな部分は、黒マスの周りの9この座標くらいだと気づく。
  • つまり、見るべき座標は最大でも$9N$個となる。見ている座標に黒マスが含まれているかどうかは$O(logN)$出判定できるので全体の計算量は$O(NlogN)$となる。

細かいこと

  • $9\times9$がすべて白いマスである個数の数え方を考える。
    • 初期値を$(H-2)(W-2)$とする。
    • $9\times9$に黒いマスがある場合、初期値から1を引く。これを繰り返すことで何も塗られていないマスの数がわかる。


解法

f:id:nomikura:20180607082258p:plain

  • 図のように、$9 \times 9$のマスにおいて黒マスが含まれるようなものを列挙したい。
  • なので、色つきのマスの周りの9つの座標をsetで持っておく。
  • 次に、そのマスから右下の$9\times9$にいくつ黒マスが含まれているかを数える。カウントした数はans[cnt]++のようにして答えに加算する。
  • 計算量は$O(NlogN)$となる。


コード

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

using ll = long long;
using pii = pair<ll, ll>;

ll H, W, N;
ll A[111111], B[111111];
set<pii> coord, S; // 入力座標, 入力座標の周辺座標
ll ans[100];

// 黒マス周辺の9座標を列挙するための左上の座標をsetに格納する
void make(ll y, ll x) {
   for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
         int ny = y - i, nx = x - j;
         if (ny >= 1 && ny <= H-2 && nx >= 1 && nx <= W-2) {
            S.insert({ny, nx});
         }
      }
   }
}

int main() {
   cin >> H >> W >> N;
   for (int i = 0; i < N; i++) {
      cin >> A[i] >> B[i];
      coord.insert({A[i], B[i]});
      make(A[i], B[i]);
   }

   ll white = (H-2) * (W-2); // 9*9が白いマスの個数
   for (pii p : S) {
      ll y = p.first, x = p.second;
      int cnt = 0;
      for (ll i = y; i < y+3; i++) {
         for (ll j = x; j < x+3; j++) {
            if (coord.find({i, j}) != coord.end()) {
               cnt++;
            }
         }
      }
      if (cnt) white--;
      ans[cnt]++;
   }

   ans[0] = white;
   for (int i = 0; i <= 9; i++) {
      cout << ans[i] << endl;
   }


   return 0;
}

差分の列挙について

  • for分で$i, j(0 \leq i, j < 3)$について列挙する処理、上手いなあって感じ。
  • 僕は解いたとき$i, j(-2 \leq i, j \leq 0)$で回した。
  • でも、$0 \leq i, j < 3$で回してそれを座標から引くって言う処理の方が楽な気がする。


要点

  • 無駄な処理をしている部分を考えることが大事だった。
    • 今回の場合、白マスのみの部分を数えるのは無駄だった。
    • 無駄な部分を考えると計算量を落とすきっかけになることはよくある気がする。
  • 答えを求めるために関係のある部分のみについて考えることが大事だった。
    • すべての情報を見ていては間に合わないときにこの考え方を使うと良いのかなーと思う。
  • 無駄な処理を見つける→関係のありそうな部分を考えるっていう流れは大事かもしれない。


感想

  • 1度解いたことがあるので考察は一瞬だった。でも本番でこれを思いつける気はしない
  • 実装に時間がかかってしまった。結構複雑だよなー、これ。