AOJ 2611 Ordering

競プロ AOJ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2611&lang=jp

解法

問題文を丁寧に読まなければならない問題です．
「それぞれの塔は自分自身よりも大きな塔とは高々1回しか比較されていない」とあるので，与えられた関係 (a, b) を有向辺とみるとこれは木になっています．

この時点で木DPかなあという見通しが立ちます．
ある頂点のそれぞれの部分木は独立に考えることができるので，あとはそれらをいい感じにマージしていくことになります．

引き分けがなければ単純に挿入していくDPなんですが，今回は引き分けがあるのでうまく処理しなければなりません．
（高さの異なる塔を高さ順に並べていくイメージだとすると，引き分けは同じところに複数の塔を置くということになります．）
ここで以下のDPを考えます．
dp2[i][j][k] := 高さが異なる i 個の集合 A と，高さが異なる j 個の集合 B をマージして，最終的に高さが異なる k 個の集合にする場合の数
遷移は以下の通り，3通りあります．

  • A の i 番目の塔が B の j 番目よりも高い => dp2[i - 1][j][k - 1]
  • A の i 番目と B の j 番目の高さが等しい => dp2[i - 1][j - 1][k - 1]
  • A の i 番目より B の j 番目のほうが高い => dp2[i][j - 1][k - 1]

dp2[i][j][k] はこれらの和になります．
このDPテーブルは前もって計算できるのでそうします．

あとはマージしていくだけで，これは難しくありません．以下のDPでできます．
dp[v][i] := 根が v の部分木で，高さが異なる塔が i 個あるような関係の作り方の総数
この dp テーブルを先程の dp2 を使って計算していきます．
今構築中の高さの関係を
tmp[i][j] := i 番目の子まで見たときに，高さが異なる塔が j 個であるような総数
とすると，
tmp[i + 1][l] += tmp[i][j] * dp[ch[i]][k] * dp2[j][k][l]
という式が書けるので，各 i, j, k, l についてループを回します．

各頂点でこれをやるので，ぱっと見た感じでは（ch の i は無視できるので）j, k, l の3重ループと合わせて O(N^4) っぽいですが，計算量の漸化式を書いてみると実は O(N^3) になっています．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll M = 1e9 + 7;
ll dp2[256][256][256];
int sz[256];

int dfs(int v, vector<vector<int>>& g, vector<vector<ll>>& dp) {
    if(g[v].size() == 0) {
        dp[v][1] = 1;
        return sz[v] = 1;
    }

    sz[v] = 1;
    for(auto ch : g[v]) {
        sz[v] += dfs(ch, g, dp);
    }

    vector<vector<ll>> tmp(g[v].size() + 1, vector<ll>(sum));
    tmp[0][0] = 1;
    for(int i = 0; i < (int)g[v].size(); ++i) {
        int ch = g[v][i];
        for(int l = 0; l < sz[v]; ++l) {
            for(int j = 0; j <= l; ++j) {
                for(int k = 1; k <= sz[ch]; ++k) {
                    (tmp[i + 1][l] += (tmp[i][j] * dp[ch][k] % M) * dp2[j][k][l]) %= M;
                }
            }
        }
    }
    for(int i = 0; i < sum; ++i) {
        dp[v][i + 1] = tmp[g[v].size()][i];
    }
    return sz[v];
}

int main() {
    for(int i = 0; i < 201; ++i) {
        dp2[i][0][i] = 1;
        dp2[0][i][i] = 1;
    }
    for(int k = 1; k < 201; ++k) {
        for(int i = 1; i < 201; ++i) {
            for(int j = 1; j < 201; ++j) {
                (dp2[i][j][k] += dp2[i - 1][j - 1][k - 1] + dp2[i - 1][j][k - 1] + dp2[i][j - 1][k - 1]) %= M;
            }
        }
    }

    int N;
    cin >> N;
    vector<vector<int>> g(N);
    vector<bool> in(N);
    for(int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        in[b] = true;
    }
    int root = -1;
    for(int i = 0; i < N; ++i) {
        if(!in[i]) {
            root = i;
            break;
        }
    }
    vector<vector<ll>> dp(N + 1, vector<ll>(N + 1));
    dfs(root, g, dp);

    ll res = 0;
    for(int i = 0; i <= N; ++i) {
        (res += dp[root][i]) %= M;
    }
    cout << res << endl;
}

感想

O(N^4) から落ちへんやんけ！と言いながらヤケクソで投げたら通り，計算量の見積もりが甘かったと気付かされた．
実はオーダーが落ちて（？）いるというのは，結構面白かったし今後も使えそうなので覚えておきたい．