ferinの競プロ帳

競プロについてのメモ

SRM623 div1easy UniformBoard

考えたこ

PをAに置き換えるためにはPをどこか別の空マスに移し、Aをどこかから持ってくるため2手かかる。.をAに置き換えるためには1手かかる。
ある長方形の範囲を条件を満たす範囲とできるかを考える。Aが2個、Pが1個、.が1個ある範囲を全てAに置き換えるためには、
* Aが他の部分に2個以上存在する
* Pが1個→2手 .が1個→1手 より 3手 <= K
の条件を満たす必要がある。したがって、長方形の範囲内のP、A、.の数を高速に求める必要がありこれは累積和で前計算しておくことでO(1)でできる。長方形はO(N^4)個存在するため合計O(N^4)で解くことが出来る。

考察はすぐにできたが実装でバグらせて時間を掛けて反省。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int cnt[25][25][3];
class UniformBoard {
  public:
  int getBoard(vector <string> board, int K)
  {
    int n = board.size();
    memset(cnt, 0, sizeof(cnt));
    FOR(i, 1, n+1) FOR(j, 1, n+1) {
      cnt[i][j][0] = cnt[i-1][j][0] + cnt[i][j-1][0] - cnt[i-1][j-1][0];
      if(board[i-1][j-1] == 'A') cnt[i][j][0]++;
    }
    FOR(i, 1, n+1) FOR(j, 1, n+1) {
      cnt[i][j][1] = cnt[i-1][j][1] + cnt[i][j-1][1] - cnt[i-1][j-1][1];
      if(board[i-1][j-1] == 'P') cnt[i][j][1]++;
    }
    FOR(i, 1, n+1) FOR(j, 1, n+1) {
      cnt[i][j][2] = cnt[i-1][j][2] + cnt[i][j-1][2] - cnt[i-1][j-1][2];
      if(board[i-1][j-1] == '.') cnt[i][j][2]++;
    }

    int all = cnt[n][n][0];
    if(cnt[n][n][0] == 0) return 0;

    int ret = 0;
    FOR(sx, 1, n+1) FOR(sy, 1, n+1) FOR(gx, sx, n+1) FOR(gy, sy, n+1) {
      int apple = cnt[gy][gx][0] - cnt[sy-1][gx][0] - cnt[gy][sx-1][0] + cnt[sy-1][sx-1][0];
      int pear = cnt[gy][gx][1] - cnt[sy-1][gx][1] - cnt[gy][sx-1][1] + cnt[sy-1][sx-1][1];
      int emp = cnt[gy][gx][2] - cnt[sy-1][gx][2] - cnt[gy][sx-1][2] + cnt[sy-1][sx-1][2];
      int menseki = (gy-sy+1)*(gx-sx+1);
      // 交換不可能
      if(cnt[n][n][2] == 0) {
        if(menseki == apple) chmax(ret, apple);
        continue;
      }
      if(all - apple < menseki - apple) continue;
      if(pear*2 + emp <= K) chmax(ret, menseki);
    }
    return ret;
  }
};