mayoko’s diary

プロコンとかいろいろ。

SRM 504 div1 med:AlgridTwo

解法

基本的な方針は以下の通り。


まず0行目は必ずoutputの0行目と一致していなければならない(0行目は変更することが出来ないから)。

そして1行目以降は,i行目とi-1行目にのみ依存してoutputが生成されることがわかる。

これらのことから,各i(i=1〜H-1)について,

・i-1行目の情報からi行目のわかるところを構成する
・構成したものとoutputの間に矛盾があった場合は0を返す
・構成したものを見て,どれくらい自由度があるか(何を入れてもi行目の結果が同じになるもの)を考慮しながら場合の数を求める

すこしわかりづらいと思うので具体例を考えます。問題のサンプル1でこのやり方を実行してみます。

・0行目は
BBWBBB
で決定
・これを元に,1行目を考える。
最初にi行目の状態を"??????"とすると,
??????(BBでスワップ)
?BB???(BWで黒に変換)
?BWW??(WBで白に変換)
?BW?W?(BBでスワップ)
?BW??W(BBでスワップ)
要するに,1行目の1,2,5番目の要素はそれぞれB, W, Wで確定しているということがわかる。

これとoutputの1行目を比べると,outputの1行目の1,2,5番目はそれぞれB, W, Wなので矛盾していない。よって,0を返す必要はない。

次に,答えとして何通りの可能性があるのかを考える。あとで理由を説明するが,W-(?の数)だけ自由度があるので,今回の場合は3つ自由度があり,場合の数は2^3=8倍になる。

よって,答えは8通り。

で,この問題で一番難しいのは多分自由度を求めるところだと思います。先ほど書いたようにW-(?の数)だけ自由度があるのですが,これを示すには基本的には1つの?と一つのマスが1対1に対応していることを示せばよいです。

まずW-1番目のマスが?でない場合は,i番目のマスを塗ることになる色は結局i+1番目のマスの色になるので,1対1対応です。

次にW-1番目のマスが?の場合を考えます。このようになる場合は,
・上の行がすべてB
・上の行の最後から数えて1, 2番目はすべてW
のいずれかでしかありえません。

1つ目の場合は「上の行がすべてBならば,下の行をoutputに合わせるような色の組み合わせ方は1通りしかない」ということから示したいことを言えます(数学的帰納法)。これは1対1とか関係ないですね。

2つ目の場合はW-1番目のマスが自分自身で自分の色を決定することになります。この場合はW-1番目のマスがW-1番目の?を決定するので1対1対応です。他のマスは上と同様にi-i+1の対応があるので大丈夫です。

本番はW-1番目がどうなるかよくわからないままエイヤで出したら通りました。ちょっと危うい(もっと簡単にアルゴリズムの正当性が示せるのかな…?)。

const ll MOD = 1e9+7;

class AlgridTwo {
public:
    int makeProgram(vector <string> output) {
        int H = output.size();
        int W = output[0].size();
        ll ans = 1;
        for (int i = 1; i < H; i++) {
            string s = output[0];
            for (int j = 0; j < W; j++) s[j] = '?';
            for (int j = 0; j < W-1; j++) {
                char c = output[i-1][j], d = output[i-1][j+1];
                if (c == 'B' && d == 'W') {
                    s[j] = 'B';
                    s[j+1] = 'B';
                } else if (c == 'W' && d == 'B') {
                    s[j] = 'W';
                    s[j+1] = 'W';
                } else if (c == 'B' && d == 'B') {
                    swap(s[j], s[j+1]);
                }
            }
            cout << s << endl;
            for (int j = 0; j < W; j++) {
                if (s[j] != '?' && output[i][j] != s[j]) return 0;
            }
            int cnt = 0;
            for (int j = 0; j < W; j++) {
                if (s[j] == '?') cnt++;
            }
            cnt = W-cnt;
            for (int j = 0; j < cnt; j++) (ans *= 2) %= MOD;
        }
        return ans;
    }
};