SRM655 div1 easy BichromePainting

考えたこと

• どんなマスなら白から黒に変えられるか考える
• そのマスの右と下にkマスずつ余裕があれば白から黒にできる
• 各方向からn-k列は何であっても実現できそうなので残りのk列が実現できるか判定できればよさそう
• n-k列の方が埋まってたらk列の方が黒く塗れる位置が変化したり異常に判定が難しい
• 何も思いつかないので問題文を読み返すとn<=50じゃなくてn<=20
• 1列の情報を覚えとくbitDPみたいなのをやろうとしたけど1列だけ覚えたところでどうしようもなさそう
• 何もわからない
  -------解説を見た-------
• 逆に戻していく操作を考える
• k*kマスで全部WかBなら塗る前の色がどんな状態だろうと関係ない
• O(n^6)はじめて見た気がする

逆の操作を考えるのは定番中の定番なのに思いつかなかったのはだめ

学び

• n=20ならO(n^6)が通る

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

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

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class BichromePainting {
   public:
   string isThatPossible(vector <string> board, int k)
  {
    int n = board.size();

    bool update = true;
    while(update) {
      update = false;
      REP(y, n) REP(x, n) {
        if(y+k-1 >= n || x+k-1 >= n) continue;
        // 範囲内がwだけかbだけ
        bool w=false, b=false;
        REP(i, k) REP(j, k) {
          if(board[i+y][j+x] == 'W') w=true;
          if(board[i+y][j+x] == 'B') b=true;
        }
        if((w&&b) || (w==0&&b==0)) continue;
        REP(i, k) REP(j, k) {
          board[i+y][j+x] = '?';
        }
        update = true;
      }
    }

    // 全部?ならPossible
    REP(i, n) REP(j, n) if(board[i][j] != '?') return "Impossible";
    return "Possible";
  }
};