2015-2016 XVI Open Cup, Grand Prix of Bashkortostan, SKB Kontur Cup Stage 2 A. Abstract Picture

JAG 夏合宿最終日に yurahuna さんに投げたら勝手に AC してくれた問題です。

問題

codeforces.com

N*N のグリッド上に色を塗りたい。
1 回の操作では行に同じ色をバーっと塗るか列に同じ色をバーッと塗るかしかない。

最終的に塗りたい配色が与えられるので, 塗り方を求めよ(塗り方が存在することは保証される)。

解法

後ろから見ていくと, 最終的にある行/列がある一種類のあるアルファベット c + '?' だけで構成されていれば, その行/列を c で塗れば良いです。そこを後から上塗りすればその行/列は塗れることが保証されるので, その行/列を塗る前を考える際は, そこはすべて '?' だったと考えて, 続けて塗れる場所を探していきます。

これを愚直にやると O(N^3) かかりますが(これで通ってもいいじゃない), queue を使うと O(N^2) に出来ます。

cnt[i][c] = (行 i に 文字列 c がいくつあるのか), というのと done[i] = (行 i にまだ残っている文字の種類) というのを覚えておきます。すると, ある列 C を塗ったとき, 各行について, grid[i][C] に書かれている文字はすべて '?' に置換されるので, cnt[i][grid[i][C]]-- 出来ます。これで cnt の値が 0 になったとき, done[i] として残っている文字が 1 種類しかなかったら, その行を que に追加する, というようにやっていきます。

typedef tuple<int, int, char> IIC;

const int MAXN = 3030;
string field[MAXN];

int cnt[MAXN][2][26];
int done[MAXN][2];
bool check[MAXN][2];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    map<int, char> mp;
    mp[0] = 'a';
    for (int i = 0; i < 26; i++) {
        mp[1<<i] = (char)('a'+i);
    }
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> field[i];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (field[i][j] != '?') {
                int num = field[i][j]-'a';
                cnt[i][0][num]++; 
                done[i][0] |= 1<<num;
            }
            if (field[j][i] != '?') {
                int num = field[j][i] - 'a';
                cnt[i][1][num]++;
                done[i][1] |= 1<<num;
            }
        }
    }
    queue<IIC> que;
    for (int i = 0; i < N; i++) {
        if (__builtin_popcount(done[i][0]) <= 1) {
            que.push(IIC(i, 0, mp[done[i][0]]));
            check[i][0] = true;
        }
        if (__builtin_popcount(done[i][1]) <= 1) {
            que.push(IIC(i, 1, mp[done[i][1]]));
            check[i][1] = true;
        }
    }
    vector<string> ans(2*N);
    int t = 0;
    while (!que.empty()) {
        int x, type;
        char c;
        tie(x, type, c) = que.front(); que.pop();
        if (type==0) ans[t] += "h ";
        else ans[t] += "v ";
        ans[t] += to_string(x+1) + " ";
        ans[t] += c;
        t++;
        if (done[x][type]) {
            for (int i = 0; i < N; i++) {
                if (type == 0) {
                    char& c = field[x][i];
                    if (c != '?') {
                        int num = c-'a';
                        if (--cnt[i][1][num] == 0) {
                            done[i][1] ^= 1<<num;
                            if (!check[i][1] && __builtin_popcount(done[i][1]) <= 1) {
                                check[i][1] = true;
                                que.push(IIC(i, 1, mp[done[i][1]]));
                            }
                        }
                    }
                    c = '?';
                } else {
                    char& c = field[i][x];
                    if (c != '?') {
                        int num = c-'a';
                        if (--cnt[i][0][num] == 0) {
                            done[i][0] ^= 1<<num;
                            if ((!check[i][0]) && __builtin_popcount(done[i][0]) <= 1) {
                                check[i][0] = true;
                                que.push(IIC(i, 0, mp[done[i][0]]));
                            }
                        }
                    }
                    c = '?';
                }
            }
        }
    }
    reverse(ans.begin(), ans.end());
    for (string s : ans)
        cout << s << endl;
    return 0;
}