Digit Permutation [CSAcademy #60 C]

https://csacademy.com/contest/round-60/task/digit-permutation/

N個の数がある。
それぞれK進数でM桁である。
ここで0～(K-1)の順列pを用意する。
全ての数の全ての桁の数を順列pによって置換して、以下の条件をみたすようにせよ。

• 0から始まる数ではない
• N個の数が狭義単調増加している（狭義なので等しいとダメ）

置換しても条件を満たせないなら"-1"
※ 順列pによって置換とは「i桁目の数がaであるなら、これをp[a]に変える」ことを指す

前提知識

• トポロジカルソート

解法

まず自分がハマったコーナーケースを最初にあげておく。

N=3, K=3, M=3
2 0 0
2 0 0
1 1 0
を p = {0, 2, 1} で置換すると
1 0 0
1 0 0
2 2 0
となり、これはちゃんとしているように見えるが、狭義単調増加していない。
つまり、入力で同じ数があると狭義単調増加しない

先頭から順番に大小関係を考えていく。
よく大小関係は有向グラフを使って解決するやり方があるので、今回もそのやり方を当てはめてみる。
f(L, R, d) := [L,R)番目の数のd桁目について大小関係を比較して辺を引く
d桁目をLから順番に見ていって、数の変わり目が出てきたら、変わる前の数がaで、変わった後の数がbならば、abと辺を引く。
数が変わらない区間は大小関係をその後の桁で保証する必要があるので、再帰でd+1桁目で辺を貼っていく。

こうして辺を貼ったら、そのグラフをトポロジカルソートしていく。
トポロジカルソート順で数を小さい方から割り当てていくと、大小関係を正しく保ちつつ数を入れられる。
注意点は数の頭が0となっては行けない所である。
zero_ng[i] := 数iを0にしてはいけないかどうか
in_edge[i] := 数iに入る辺が何個あるか
これをそれぞれ用意し、トポロジカルソートで数を割り当てる過程で「数iを0にしてもいい、かつ、数iに入る辺が無い」ものを0とする。
他は順番に数を割り当てていく。

最後にちゃんと条件を満たしているかどうかチェックして大丈夫なら答える。

struct TopologicalSort {
    vector<set<int>> E;
    void init(int n) { E.resize(n); }
    void add_edge(int a, int b) { E[a].insert(b); }
    bool visit(int v, vector<int>& order, vector<int>& color) { color[v] = 1;
        for (int u : E[v]) { if (color[u] == 2) continue; if (color[u] == 1) return false;
        if (!visit(u, order, color)) return false; } order.push_back(v); color[v] = 2; return true; }
    bool sort(vector<int> &order) { int n = E.size(); vector<int> color(n);
        for (int u = 0; u < n; u++) if (!color[u] && !visit(u, order, color)) return false;
        reverse(order.begin(), order.end()); return true; } };





int N, M, K;
vector<vector<int>> A;
TopologicalSort ts;
int ans[101010], zero_ng[101010], in_edge[101010];
//---------------------------------------------------------------------------------------------------
void f(int L, int R, int d) {
    if (d == M or L == R) return;

    int a = A[L][d], b = L;
    rep(i, L, R) {
        if (A[i][d] != a) {
            ts.add_edge(a, A[i][d]);
            in_edge[A[i][d]]++;
            f(b, i, d + 1);
            a = A[i][d];
            b = i;
        }
    }
    f(b, R, d + 1);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> M;
    A.resize(N, vector<int>(M));
    rep(y, 0, N) {
        rep(x, 0, M) {
            int v; cin >> v;
            A[y][x] = v;
        }
    }

    ts.init(K);
    f(0, N, 0);
    rep(y, 0, N) zero_ng[A[y][0]] = 1;

    vector<int> v;
    rep(i, 0, K) v.push_back(i);

    int res = ts.sort(v);
    if (!res) {
        printf("-1\n");
        return;
    }

    int zero = 1;
    int c = 1;
    rep(i, 0, K) {
        int j = v[i];
        if (zero and zero_ng[j] == 0 and in_edge[j] == 0) {
            ans[j] = 0;
            zero = 0;
        } else {
            ans[j] = c;
            c++;
        }
    }
    if(zero) {
        printf("-1\n");
        return;
    }
    
    rep(y, 0, N) rep(x, 0, M) A[y][x] = ans[A[y][x]];

    rep(y, 0, N - 1) {
        int ok = 0;
        rep(x, 0, M) {
            if (A[y][x] == A[y + 1][x]) continue;
            else if (A[y][x] < A[y + 1][x]) {
                ok = 1;
                break;
            } else {
                break;
            }
        }
        if (!ok) {
            printf("-1\n");
            return;
        }
    }

    rep(i, 0, K) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    } printf("\n");
}