SRM 655 Div1 Easy - BichromePainting

問題

TopCoder Statistics - Problem Statement

問題概要

のグリッドがあり、最初は全て白に塗られている。の領域を白または黒に塗るという動作をすることが何回も出来るときに、最終状態がboardとして与えられるのでこの最終状態を作ることができるか否かを判定せよ。

• 
• 

アイデア

最終状態が真っ白でなければ、最終状態にするためには必ず1回は色を塗る動作をすることが必要になる。つまり、最後に塗る位置というものが存在しうる。この最後に塗る動作をして最終状態が完成すると考えるなら、最終状態にはの同じ色のセルが存在しているはずである。

全探索していき、の同じ色のセルを見つけたら、そこを最後に塗る位置だと仮定することが出来る。

例として、で、次のような最終状態の場合を考えてみる：

BWBWBB
WBWBBB
BWBWBB
WBWBBB
BBBBBB
BBBBBB

この例のように、の同じ色の正方形が様々な位置に見つかる場合もある。その時にどの正方形をいいのかというのはこの時点では判断がつかない。とりあえず今はその問題を考えないことにして、最終状態の1つ前の状態をどうなっているか見てみる。その時、分からない部分を?として表すと例えば次のようになっている：

BWBWBB
WBWBBB
BWBWBB
WBW??B
BBB??B
BBBBBB

このように?で表された最終状態の1つ手前の形を見た時に、この?を拡大していく形で更にこの状態を戻していくことが出来る。具体的には、このように?に隣り合う部分を見た時に?がどちらの色でも良いとみなしてまたの正方形がある場合はその部分の色を?に変換することができるわけである。例えば、上の状態から、右下の部分は全部黒に塗られていたと考えられるので、次のように?を拡大できる：

BWBWBB
WBWBBB
BWBWBB
WBW??B
BBB???
BBBB??

この拡大を繰り返していくことによって、全て黒の部分だけを戻していくと以下の状態に達する：

BWBW??
WBWB??
BWBW??
WBW???
??????
??????

このように?を拡大していくことで黒の領域を全て返還できた。これをこのどの位置から始めていたとしてもこの状態にたどり着くことが出来るのは想像できる。つまり、順番とかは気にする必要がないという結論に達する。つまり1つ見つかればそこをスタート地点にしてしまおうということが出来る。

そして、この次は右下の白の部分に注目して例えば次のような状態にできる：

BWBW??
WBWB??
BWBW??
WB????
??????
??????

以下、これを繰り返していくことによって全てのセルを?に変換することが出来る。つまり初期状態から最終状態への塗る順番を逆順にたどれたとみなせるので、実現可能という判定ができる。逆にこの?の変換が最後までできずに途中で止まってしまった場合には、初期状態には戻せないということになるので、不可能ということになる。

さて、あとは計算量を考慮しながら今やってきたような操作をやっていきたい。まず、?に変換する位置の候補としては個の位置がある。さて、この各候補に対して、?への変換が可能かどうかを判定し、見つけた場合に変換を行うためにかかる。つまり、この動作を1回やろうとするとかかるということになる。そして、全てが?になるまでこの動作が何回行われるのかということについて考えてみると1箇所変換できる場所を見つけるということは最低でも1つBまたはWになっている位置が?へと変わるわけであるから、この動作を行う回数は回ということになる。よって全体の計算量はということになり、今回のの制約を見るとこれで十分間に合う。

最終状態から辿っていくようにするというアイデアだけがポイントだったという感じがする。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

class BichromePainting {
    public:
    string isThatPossible(vector<string> board, int k) {
        // k=1なら絶対できるのでその場合はこれ以降は考慮しない
        if(k==1) return "Possible";

        int n = board.size();

        while(1)
        {
            int Y=-1,X=-1;
            // ?変換を出来る場所を探す
            rep(i,n+1-k)rep(j,n+1-k)
            {
                int q=0,b=0,w=0;
                for(int y=i; y<i+k; ++y)for(int x=j; x<j+k; ++x)
                {
                    if(board[y][x]=='W') ++w;
                    else if(board[y][x]=='B') ++b;
                    else ++q;
                }

                // 全てのセルが?なのでここは対象外
                if(q==k*k) continue;

                // どちらかの色しか含まれていない時、そこを?変換の対象とできる
                if(b==0 || w==0)
                {
                    Y=i;
                    X=j;
                    break;
                }
            }

            // 見つからなかった
            if(Y==-1) break;

            // 変換
            for(int y=Y; y<Y+k; ++y)for(int x=X; x<X+k; ++x) board[y][x]='?';
        }

        // 最後に初期状態に戻せるかを判定
        bool valid=true;
        rep(i,n)rep(j,n)
        {
            if(board[i][j]!='?') valid=false;
        }
        string ret="Impossible";
        if(valid) ret="Possible";
        return ret;
    }
};