天下一予選B C - 天下一王国の歴史

解法
一行目の色は適当に決定して構わない。一行目の決定に従う形で二行目以降は繰り返しに色が定まっていく。これは蟻本の反転と同じ要領の考え方。

今、色を決めようとしている場所 (j, i) は、既に決定した上のマス (j, i-1) の色が成立するように帳尻を合わせる色に決める。O(N^2)

#include <iostream>

using namespace std;

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

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)

int MAP[760][760];
int ANS[760][760];

inline bool valid(int x, int y, int n) {
  return 0<=x&&x<n&&0<=y&&y<n;
}

int main() {
  
  int n; cin >> n;
  rep(i, n) rep(j, n) {
    char ch; cin >> ch;
    MAP[i][j] = ch == '#';
  }
  
  rep(i,n) {
    ANS[0][i] = 0;
  }
  
  REP(i,1,n) {
    rep(j,n) {
      int cnt = 0;
      rep(k,3) {
        int ni = i-1+dy[k], nj = j+dx[k];
        if(valid(nj,ni,n)) {
          if(ANS[ni][nj]) { cnt ++; }
        }
      }
      ANS[i][j] = (MAP[i-1][j]+cnt)%2;
    }
  }

  rep(i,n) {
    rep(j,n) cout << (ANS[i][j] ? '#' : '.');
    cout << endl;
  }
  
  return 0;
}