AOJ 2646 - Tournament

問題文

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

解法

全探索を考えるところから。
n が小さくで列を愚直に持てるとしたら、次の全探索を考えるはず。

　res(l, r, rank) := 区間 [l, r) における勝者の最終順位が rank になるときの最適解

遷移は、m = (l + r) / 2, d = この区間の最終決戦の高さ（真の決勝からの高さ）として

　res(l, r, rank) = min(res(l, m, rank) + res(m, r, d + 1), res(l, m, d + 1) + res(m, r, rank))

となる。

メモ化してもこのままだと間に合わない…
と思いきや、この探索は別に数列を愚直に持たなくてもできる。
今見ている区間が、ある区間 [a[i], a[i + 1]) に完全に内包されるなら、その瞬間に O(1) で計算できるからである。
このとき、メモ化するのは、rank == d のときだけでOK。
遷移を考えればわかるが、d == rank のときをメモ化しておけば、決勝からの高さ d のところで d != rank となるような探索は全体では d 回しか起こらない（はず、厳密に示してない）。
探索ノード数は、各区間 [a[i], a[i + 1])に対して、2べきサイズでごっそりとっていくイメージ（セグツリと似てる）なので、それぞれ log ぐらいのサイズ (n 以下) しかない。

なので、どんなに悪く見積もっても O(n^2 m) で解けている。
以下は map 使ってるので余計な log が付いてる。
定数倍厳しいときは気をつけないと普通に TLE しそう。

ソースコード

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

using pii = pair<int, int>;

int main() {
    int n, m; cin >> n >> m;
    vector<int> a(m + 1), b(m);
    for(auto& x : a) cin >> x;
    for(auto& x : b) cin >> x;

    vector<map<pii, int>> dp(n + 1);
    // consider ['l', 'r'), 'd' is depth, 'final_rank' represents this block winner's rank (2^r)
    function<int(int, int, int, int)> solve = [&] (int l, int r, int d, int final_rank) {
        if(final_rank == d && dp[final_rank].count({l, r})) return dp[final_rank][{l, r}];
        const int i = lower_bound(begin(a), end(a), r) - begin(a) - 1;
        int res = 0;
        if(0 <= i && a[i] <= l && r <= a[i + 1]) { // contain completely
            if(b[i] >= d + 1) {
                res = r - l - (r - l) / (1 << (n - b[i] + 1));
            } else {
                res = r - l - (b[i] == final_rank);
            }
        } else { // choose which block win
            const int mid = (l + r) / 2;
            res = min(solve(l, mid, d + 1, final_rank) + solve(mid, r, d + 1, d + 1),
                      solve(l, mid, d + 1, d + 1) + solve(mid, r, d + 1, final_rank));
        }
        if(final_rank == d) return dp[final_rank][{l, r}] = res;
        else return res;
    };

    cout << solve(0, 1 << n, 0, 0) << endl;
}

感想

なんか頭いいやり方があるのかと思って無限に悩んだ。
結局ただのメモ化再帰なんだなあ。ただ計算量解析が怪しい。