Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

Codeforces Round #541 (Div. 2) - D 「Gourmet choice」 [2000]

codeforces.com

概要

とあるグルメがレストランで1日目に N種類、2日目に M種類の料理を頼んだ。

そしてグルメは各 1 \leq i \leq N, 1 \leq j \leq Mについて、1日目の i品目と2日目の j品目の料理を

  • 1日目の方が美味しかった
  • 2日目の方が美味しかった
  • 同じくらい美味しかった

のいずれかで評価した。

このとき、グルメの評価に矛盾しないように各料理に正整数のスコアを割り振ることができるか。できるならば、スコアの最大値が最小になるような割り振りを出力せよ。

制約

  •  1 \leq N, M \leq 1,000

解説

まず評価が同じ料理はスコアも同じでならなくてはならないので、UnionFind木でそれらを連結する。このとき、評価が同じでないのに同じグループになっているものがいないか確認する。

こうしてグループ分けされた料理群に対して、今度は「美味しさ」が大きい方から小さい方へ有向辺が張られた有向グラフを作る。このグラフに閉路が存在する場合は、どうスコアを振っても閉路内で矛盾が起こるのでアウトとなる。

そうでない場合、グラフはDAGとなるので矛盾なくスコアが割り振れる。スコアの最大値を最小化しなければならないが、これは「子に割り振られたスコアの最大値+1」(葉のスコアは1)と振るのが最適となる。

実装例

...と解法は一直線なのだが、本当に怠い難しいのは実装である。複数の頂点をひとまとめにしたグラフを扱う機会はあまりないので、どう実装すればいいのか非常に悩んだ。

人々の実装を色々見たが、結局「UnionFindの根を代表元として扱う」というアルメリアさんの実装が一番腑に落ちた。本番でこういう実装がしたいものである。

#include <iostream>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;

class UnionFind {
public:
    int V_NUM;
    vector<int> par, num;

    explicit UnionFind(int N) : V_NUM(N) {
        par.resize(N);
        iota(par.begin(), par.end(), 0);
        num.assign(N, 1);
    }

    int find(int x) {
        return (par[x] == x) ? x : (par[x] = find(par[x]));
    }

    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;

        if (num[x] < num[y]) swap(x, y);
        num[x] += num[y];
        par[y] = x;
    }

    bool same(int x, int y) { return find(x) == find(y); }
    bool ispar(int x) { return x == find(x); }
    int size(int x) { return num[find(x)]; }
};

void fail() {
    cout << "No" << endl;
    exit(0);
}

vector<set<int>> path;
vector<int> ans;
vector<bool> visited;

// 子の中で一番大きいスコア+1を割り振る
void dfs(int v) {
    if (ans[v] > 0) return;  // 前の週で探索済み

    visited[v] = true;
    ans[v] = 1;
    for (int sv : path[v]) {
        if (visited[sv]) fail();  // ループ判定
        dfs(sv);
        ans[v] = max(ans[v], ans[sv] + 1);
    }
    visited[v] = false;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    for (auto& s : S) cin >> s;

    // =で結ばれた料理を結ぶ
    UnionFind uf(N + M);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (S[i][j] == '=') uf.unite(i, j + N);
        }
    }

    // =の関係に矛盾がないか判定
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (uf.same(i, j + N) && S[i][j] != '=') fail();
        }
    }

    // 大小関係に応じて辺を張る
    // ただしUnionFindに於ける根の間にしか張らない
    path.resize(N + M);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (S[i][j] == '>') {
                path[uf.find(i)].insert(uf.find(j + N));
            } else if (S[i][j] == '<') {
                path[uf.find(j + N)].insert(uf.find(i));
            }
        }
    }

    // DFSでスコアを振っていく
    ans.assign(N + M, -1);
    visited.assign(N + M, false);
    for (int v = 0; v < N + M; ++v) {
        if (uf.ispar(v)) dfs(v);
    }

    cout << "Yes" << endl;
    for (int i = 0; i < N; ++i) {
        cout << ans[uf.find(i)] << " ";
    }
    cout << endl;
    for (int j = 0; j < M; ++j) {
        cout << ans[uf.find(j + N)] << " ";
    }
    cout << endl;
    return 0;
}

感想

  • こういう実装ゲーは精神的にしんどい。
  • 強連結成分分解の実装とかも練習すべきだろうか。