天下一プログラマーコンテスト2014予選B C - 天下一王国の歴史

問題ページ

まず答えの一番上の行を適当に定める。このとき入力の1~n-1行目までが正しく生成されるように、答えの2~n行目までを定めると一意に定まる。入力のn行目についても正しく生成されるような、一番上の行を探したい。 通りを全列挙することは不可能なので、一番上の行を変化させたときに、生成されるn行目がどのように変化するか考える。

のときに を変化させた場合に、答えのどこが変化するのかを以下に示す。規則的な変化になっている。

diff:  
    0123456789  
i=0 ...x......  
i=1 ..x.x.....  
i=2 .x.x.x....  
i=3 x.x.x.x...  
i=4 .x.x.x.x..  
i=5 ..x.x.x.x.  
i=6 ...x.x.x.x  
i=7 ....x.x.x.  
i=8 .....x.x..  
i=9 ......x...  

ここで一番下の行に注目すると、隣接する変化しているマスの個数は必ず偶数個である。一番上の行をどのように変化させたとしても同様のことが示せ、 行目は変化しないことがわかる。入力で与えられる文字列は必ず生成できる制約なので、一番上の行をどのように固定したとしても条件を満たす答えを得ることができる。

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#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()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<string> v(n);  
    REP(i, n) cin >> v[i];  
  
    ll dx[] = {-1, 0, 1}, dy[] = {0, -1, 0};  
    auto f = [&](string s) {  
        vector<string> ret(n, string(n, '.'));  
        ret[0] = s;  
        FOR(i, 1, n) REP(j, n) {  
            ll cnt = 0;  
            REP(k, 3) {  
                ll ni = i-1+dy[k], nj = j+dx[k];  
                if(0<=ni && ni<n && 0<=nj && nj<n) {  
                    cnt += ret[ni][nj]=='#';  
                }  
            }  
            if(v[i-1][j]=='#') {  
                if(cnt%2==0) ret[i][j] = '#';  
            } else {  
                if(cnt%2) ret[i][j] = '#';  
            }  
        }  
        return ret;  
    };  
  
    auto ret = f(string(n, '.'));  
    REP(i, n) cout << ret[i] << "\n";  
  
    return 0;  
}  

結構すき