ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

ABC #018 C 菱型カウント

概要

※問題文の内容を少し変更しています。

RxCのグリッドがあり、各マスにはoまたはxの印がついている。

そこに、「あるマスからユークリッド距離でK-1以内のマスの印を全て変えることのできるスタンプ」を1回押すことができる。

例えばK=2のときは、
□■□
■■■
□■□

K=3のときは、
□□■□□
□■■■□
■■■■■
□■■■□
□□■□□
の黒い菱型の範囲に書かれている印を変更することができる。

またこのスタンプはoにしか押すことができない。(スタンプの範囲内にxが含まれてはいけない。)
このとき何パターンの押し方があるか求めよ。

http://abc018.contest.atcoder.jp/tasks/abc018_3

解法

3種類の解法で解いてみた。


幅優先探索
スタンプを押すことのできない部分をBFSで調べる。


動的計画法
4方向からDPする。

説明が下手だけどイメージとしては例えばK=3のときに、
①菱型の左上部分
□□■□□
□■■□□
■■■□□
□□□□□
□□□□□

②菱型の右上部分
□□■□□
□□■■□
□□■■■
□□□□□
□□□□□

③菱型の右下部分
□□□□□
□□□□□
□□■■■
□□■■□
□□■□□

④菱型の左下部分
□□□□□
□□□□□
■■■□□
□■■□□
□□■□□
二等辺三角形について辺の長さを求める感じ。

それである座標を選んだときに4方向から求めたものの中で最小となる辺を選び、それが条件を満たしているかどうかを調べる。


いもす法
幅優先探索ではなく、いもす法でスタンプを押すことのできないマスを調べる。

どのように差分を取らせるかを決め、左上から右下へ、右上から左下へと値を更新させていく。

配列の範囲外アクセスが怖いのであらかじめ大きめに取っておいたほうがよい。

いもす法についてはこちら
http://imoz.jp/algorithms/imos_method.html

この記事の差分を取る手法を読みながらやった。

ソースコード

幅優先探索

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long int lli;
typedef pair<int, int> Pii;

static const int INF = 1 << 30;
static const int dx[] = {1, -1, 0, 0};
static const int dy[] = {0, 0, 1, -1};

int R, C, K;
string s[500];
int blackArea[500][500];

void bfs(int x, int y) {
  queue<pair<int, int>> Q;
  Q.push(mp(x, y));
  blackArea[y][x] = 0;

  while(!Q.empty()) {
    int cx = Q.front().F;
    int cy = Q.front().S;
    Q.pop();

    if(blackArea[cy][cx] >= K - 1) continue;
    
    rep(k, 4) {
      int nx = cx + dx[k];
      int ny = cy + dy[k];
      if(!(0 <= nx && nx < C)) continue;
      if(!(0 <= ny && ny < R)) continue;
      if(blackArea[ny][nx] <= blackArea[cy][cx] + 1) continue;
      blackArea[ny][nx] = blackArea[cy][cx] + 1;
      Q.push(mp(nx, ny));
    }
  }
}

int main() {
  // ios_base::sync_with_stdio(false);

  cin >> R >> C >> K;
  rep(i, R) cin >> s[i];

  rep(i, R) rep(j, C) blackArea[i][j] = INF;

  rep(i, R) rep(j, C) if(s[i][j] == 'x') bfs(j, i);
  
  int ans = 0;
  for(int i = K - 1; i < R - K + 1; i++) {
    for(int j = K - 1; j < C - K + 1; j++) {
      if(blackArea[i][j] == INF) ans++;
    }
  }

  cout << ans << endl;
  
  return 0;
}

動的計画法

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long int lli;
typedef pair<int, int> Pii;

int R, C, K;
string s[500];
int dp[4][500][500];

int main() {
  // ios_base::sync_with_stdio(false);
  cin >> R >> C >> K;
  rep(i, R) cin >> s[i];

  memset(dp, 0, sizeof(dp));

  for(int i = 0; i < R; i++) {
    for(int j = 0; j < C; j++) {      
      if(s[i][j] == 'x') continue;
      if(i == 0 || j == 0) dp[0][i][j] = 1;
      else dp[0][i][j] = min(dp[0][i - 1][j], dp[0][i][j - 1]) + 1;
    }
  }


  for(int j = C - 1; j >= 0; j--) {
    for(int i = 0; i < R; i++) {
      if(s[i][j] == 'x') continue;
      if(i == 0 || j == C - 1) dp[1][i][j] = 1;
      else dp[1][i][j] = min(dp[1][i - 1][j], dp[1][i][j + 1]) + 1;
    }
  }

  for(int i = R - 1; i >= 0; i--) {
    for(int j = C - 1; j >= 0; j--) {      
      if(s[i][j] == 'x') continue;
      if(i == R - 1 || j == C - 1) dp[2][i][j] = 1;
      else dp[2][i][j] = min(dp[2][i + 1][j], dp[2][i][j + 1]) + 1;
    }
  }

  for(int j = 0; j < C; j++) {      
    for(int i = R - 1; i >= 0; i--) {
      if(s[i][j] == 'x') continue;
      if(i == R - 1 || j == 0) dp[3][i][j] = 1;
      else dp[3][i][j] = min(dp[3][i + 1][j], dp[3][i][j - 1]) + 1;
    }
  }

  int ans = 0;
  rep(i, R) rep(j, C) {
    int tmp = 1e9;
    rep(k, 4) tmp = min(tmp, dp[k][i][j]);
    if(tmp >= K) ans++;
  }

  cout << ans << endl;
  
  return 0;
}

いもす法

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long int lli;
typedef pair<int, int> Pii;

int R, C, K;
string s[500];
int blackArea[1510][1510];

int main() {
  // ios_base::sync_with_stdio(false);
  cin >> R >> C >> K;
  rep(i, R) cin >> s[i];

  memset(blackArea, 0, sizeof(blackArea));

  rep(i, R) rep(j, C) if(s[i][j] == 'x') {
    int y = i + K;
    int x = j + K;
    blackArea[y + K][x]++;
    blackArea[y + K + 1][x]++;
    blackArea[y - K + 1][x]++;
    blackArea[y - K + 2][x]++;
    blackArea[y + 1][x - K]--;
    blackArea[y + 1][x - K + 1]--;
    blackArea[y + 1][x + K]--;
    blackArea[y + 1][x + K - 1]--;
  }

  REP(i, 1, R + 2 * K + 5) rep(j, C + 2 * K + 5) {
    blackArea[i][j] += blackArea[i - 1][j + 1];
  }
  
  REP(i, 1, R + 2 * K + 5) REP(j, 1, R + 2 * K + 5) {
    blackArea[i][j] += blackArea[i - 1][j - 1];
  }

  int ans = 0;
  for(int i = K - 1; i < R - K + 1; i++) {
    for(int j = K - 1; j < C - K + 1; j++) {
      if(blackArea[i + K][j + K] == 0) ans++;
    }
  }

  cout << ans << endl;
  
  return 0;
}