Codeforces Round #345 (Div. 1) C. Table Compression

問題

codeforces.com

解法

大小関係系は, 「a < b なら a -> b に有向辺を貼る」ということをやるのがよくあります。これもそのタイプです。

すべての数が異なっていたとすると,

• a_ij < a_ik を満たすなら, (i, j) -> (i, k) に辺を貼る
• a_ij < a_kj を満たすなら, (i, j) -> (k, j) に辺を貼る

というようにしてグラフを作ります。で, このグラフをトポロジカルソートして, dp[v] = (頂点 v の値) というのを,

for (int u : G[v]) dp[u] = max(dp[u], dp[v]+1)

という更新式で求めていきます。

ですが, 実際には同じ値もあるので, もう少し工夫が必要です。同じ行, 列で同じ値があったら, unionfind で同じグループにします。同じグループにしたものはひとつの頂点とみなしてグラフを作ると上手く行きます。

bool visit(const vector<vi>& g, int v, vector<int>& order, vector<int>& color) {
    color[v] = 1;
    for (int u : g[v]) {
        if (color[u]==2) continue;
        if (color[u]==1) return false;
        if (!visit(g, u, order, color)) return false;
    }
    order.push_back(v); color[v] = 2;
    return true;
}

// トポロジカルソートする
// 返り値が true の時のみ意味を持つ(false の場合は閉路)
bool TopologicalSort(const vector<vi>& g, vector<int>& order) {
    int n = g.size();
    vector<int> color(n);
    for (int u = 0; u < n; u++) if (!color[u] && !visit(g, u, order, color)) return false;
    reverse(order.begin(), order.end());
    return true;
}

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W;
    cin >> H >> W;
    vector<vector<int> > board(H, vector<int>(W));
    UnionFind uf(H*W);
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> board[i][j];

    for (int i = 0; i < H; i++) {
        vector<pii> v(W);
        for (int j = 0; j < W; j++) {
            v[j] = pii(board[i][j], j);
        }
        sort(v.begin(), v.end());
        for (int j = 0; j < W-1; j++) {
            int from = v[j].second, to = v[j+1].second;
            if (v[j].first == v[j+1].first) uf.unite(i*W+from, i*W+to);
        }
    }
    for (int i = 0; i < W; i++) {
        vector<pii> v(H);
        for (int j = 0; j < H; j++) {
            v[j] = pii(board[j][i], j);
        }
        sort(v.begin(), v.end());
        for (int j = 0; j < H-1; j++) {
            int from = v[j].second, to = v[j+1].second;
            if (v[j].first == v[j+1].first) uf.unite(from*W+i, to*W+i);
        }
    }

    vector<vi> G(H*W);
    for (int i = 0; i < H; i++) {
        vector<pii> v(W);
        for (int j = 0; j < W; j++) {
            v[j] = pii(board[i][j], j);
        }
        sort(v.begin(), v.end());
        for (int j = 0; j < W-1; j++) {
            int from = v[j].second, to = v[j+1].second;
            if (uf.same(i*W+from, i*W+to)) continue;
            G[uf.find(i*W+from)].push_back(uf.find(i*W+to));
        }
    }
    for (int i = 0; i < W; i++) {
        vector<pii> v(H);
        for (int j = 0; j < H; j++) {
            v[j] = pii(board[j][i], j);
        }
        sort(v.begin(), v.end());
        for (int j = 0; j < H-1; j++) {
            int from = v[j].second, to = v[j+1].second;
            if (uf.same(from*W+i, to*W+i)) continue;
            G[uf.find(from*W+i)].push_back(uf.find(to*W+i));
        }
    }

    vector<int> order;
    assert(TopologicalSort(G, order));
    vector<int> dp(H*W, 1);
    for (int i = 0; i < H*W; i++) {
        int v = order[i];
        for (int u : G[v]) {
            dp[u] = max(dp[u], dp[v]+1);
        }
    }

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cout << dp[uf.find(i*W+j)] << " ";
        }
        cout << endl;
    }
    return 0;
}