2019-06-16

AOJ 2587 - Elevator Hall Number

競プロ AOJ

問題文

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

解法

桁DPしようと思ったが、遷移がうまく書けないので困った。
そこでオートマトンをイメージする。
結論を言うと、a[i] の値で NFA を作ってから DFA に変換し、その上で DP する。
オートマトンとして考えるべき状態は、以下の4つがある。

P[i] := i 番目のエレベーターまで完了直後
Q[i] := i+1 番目のエレベーターの途中で、low の2桁目の値
R[i] := i+1 番目のエレベーターの途中で、low と high の2桁目の間の値
S[i] := i+1 番目のエレベーターの途中で、high の2桁目の値

low, high の値に応じて、P[i] -> Q[i], Q[i] -> P[i + 1], ... などの遷移を書く。
すると、NFA のノードの数は 4 * n + 1 個になる。
したがって、NFA のノードには P[i] = 4 * i, Q[i] = 4 * i + 1, ... と番号を振っておくと、DFA を作るときに bit で管理できる。
DFA の構築は普通に初期状態 P[0] から BFS して、各ノードに対し、遷移先の ID の集合をbitで管理すればOK。

DFA ができたらあとは普通の DP で、メモ化再帰でやるとすれば終了状態 P[n] の時 1 であり、それ以外のときは遷移先をすべて足し合わせた値になる。
ただし、現状態が終了状態を含む場合（普通にありえます）は、この値に +1 する必要がある。

計算量は O(4^N * 10) 程度でおもそうだが、DFA の探索空間はたいしたことないから問題なし。

ソースコード

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

using ll = long long;

int main() {
    int n;
    while(cin >> n, n) {
        vector<int> low(n), high(n);
        for(int i = 0; i < n; ++i) {
            cin >> low[i] >> high[i];
        }

        // build NFA
        const int fin = n * 4; // finish node
        vector<vector<vector<int>>> nfa(n * 4 + 1, vector<vector<int>>(10));
        for(int i = 0; i < n; ++i) {
            if(low[i] < 10) { // Pi -> Pi+1
                for(int x = low[i]; x <= min(9, high[i]); ++x) {
                    nfa[i * 4][x].push_back(i * 4 + 4);
                }
            } else {
                // Pi -> Qi -> Pi+1
                nfa[i * 4][low[i] / 10].push_back(i * 4 + 1);
                const int ub = low[i] / 10 == high[i] / 10 ? high[i] % 10 : 9;
                for(int x = low[i] % 10; x <= ub; ++x) {
                    nfa[i * 4 + 1][x].push_back(i * 4 + 4);
                }
            }
            // Pi -> Ri -> Pi+1
            for(int x = low[i] / 10 + 1; x < high[i] / 10; ++ x) {
                nfa[i * 4][x].push_back(i * 4 + 2);
            }
            for(int x = 0; x <= 9; ++x) {
                nfa[i * 4 + 2][x].push_back(i * 4 + 4);
            }
            if(high[i] >= 10) {// Pi -> Si -> Pi+1
                nfa[i * 4][high[i] / 10].push_back(i * 4 + 3);
                const int lb = low[i] / 10 == high[i] / 10 ? low[i] % 10 : 0;
                for(int x = lb; x <= high[i] % 10; ++x) {
                    nfa[i * 4 + 3][x].push_back(i * 4 + 4);
                }
            }
        }

        // build DFA
        map<int, array<int, 10>> dfa;
        {
            queue<int> que;
            que.push(1);
            set<int> vis = {1};
            while(!que.empty()) {
                const int S = que.front();
                que.pop();
                for(int x = 0; x <= 9; ++x) {
                    int nS = 0;
                    for(int i = 0; i < 4 * n; ++i) {
                        if(!(S & (1 << i))) continue;
                        for(auto const to : nfa[i][x]) {
                            nS |= 1 << to;
                        }
                    }
                    dfa[S][x] = nS == 0 ? -1 : nS;
                    if(nS == 0 || vis.count(nS)) continue;
                    que.push(nS);
                    vis.insert(nS);
                }
            }
        }

        map<int, ll> memo;
        function<ll(int)> solve = [&] (int S) {
            if(memo.count(S)) return memo[S];
            if(S == (1 << fin)) return 1LL;
            for(int x = 0; x <= 9; ++x) {
                if(dfa[S][x] == -1) continue;
                memo[S] += solve(dfa[S][x]);
            }
            if(S & (1 << fin)) {
                memo[S] += 1;
            }
            return memo[S];
        };

        cout << solve(1) << endl;
    }
}

感想

これむずい。
TDPC の文字列作るやつに似てるから1文字ずつ付け加えていって、無理やり一意的な表現にしようとしたけど無理だった。

2019-06-15

AOJ 1317 - Weaker than Planned

AOJ 競プロ

問題文

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

解法

普通のバックトラックで解ける。
バックトラックするときは、どういう順番で探索すると枝刈りが起こりやすいかを考える必要がある。
今回なら、文字の種類数が多い方を先に考えたほうがよい（条件が厳しいので）。
あとは実装するだけだが、考えられる実装として

単語バッグを見ていって、使うか使わないかで場合分け。使うなら、文章中の単語を1つ選んで対応付ける
文章中の単語を見ていって、対応する単語を1つ選ぶ

の2通りあるが、後者のほうが早い。
単語バックを見ていく実装だと、使わない単語がたくさんあったときに無駄な探索がかなり発生する気がするので、まあそうかなという感じ（？）

ちなみに前者の実装でも通る。前者はちょうど 1sec ぐらいかかるが、まあ本番でもぎりぎり通るのではという気がする。

ソースコード

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

int main() {
    int n;
    while(cin >> n, n) {
        vector<string> ws(n);
        for(auto& w : ws) cin >> w;
        vector<string> ss = {""};
        while(cin >> ss.back()) {
            if(ss.back().back() == '.') break;
            ss.push_back("");
        }
        ss.back().pop_back(); // period
        const auto ts = ss;
        sort(begin(ss), end(ss), [] (string s1, string s2) {
                return set<char>{begin(s1), end(s1)}.size() > set<char>{begin(s2), end(s2)}.size();
            });

        auto conv = [] (string s, vector<char> const& m) {
            for(auto& c : s) {
                c = m[c - 'A'];
            }
            return s;
        };
        string ans;
        function<void(int, vector<char>)> dfs = [&] (int i, vector<char> m) {
            if(ans == "-.") return;
            if(i == (int)ss.size()) {
                string tans = conv(ts[0], m);
                for(int j = 1; j < (int)ts.size(); ++j) {
                    tans += " " + conv(ts[j], m);
                }
                tans += ".";
                if(!ans.empty() && ans != tans) {
                    ans = "-.";
                } else {
                    ans = tans;
                }
                return;
            }
            const auto& s = ss[i];
            for(auto const& w : ws) {
                if(s.size() != w.size()) continue;
                bool check = true;
                vector<char> tm = m;
                for(int j = 0; j < (int)s.size(); ++j) {
                    check &= m[s[j] - 'A'] == w[j] || (m[s[j] - 'A'] == '*' && m[w[j] - 'A'] == '*');
                    tm[s[j] - 'A'] = w[j];
                    tm[w[j] - 'A'] = s[j];
                }
                if(!check) continue;
                dfs(i + 1, move(tm));
            }
        };
        dfs(0, vector<char>(26, '*'));

        cout << ans << endl;
    }
}

感想

ICPC っぽい。ICPC の問題なんだからそりゃそうだ。

2019-06-15

AOJ 1307 - Towns along a Highway

AOJ 競プロ

問題文

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

解法

こういうのは確定できるところからさせるもの。
とりあえず一番遠いところは unique に定まるので確定させる。
次は、残ってる d の中で最も大きい値を選ぶ。
こいつは、明らかに端のどっちかと最も遠い位置関係にあるはず。
どっちと遠いかは 2 通りあるが、n <= 20 なので両方試す全探索が可能。
その座標に置いたときに、すでに確定させた位置との相対距離の集合が、残ってる d の集合の部分集合であればOKで、一旦それを消して次の探索に移る。

ソースコード

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

int main() {
    int n;
    while(cin >> n, n) {
        multiset<int, greater<>> d;
        for(int i = 0; i < n * (n - 1) / 2; ++i) {
            int x; cin >> x;
            d.insert(x);
        }

        vector<int> cur = {0, *d.begin()}; // x position
        d.erase(d.begin());
        vector<vector<int>> ans;
        function<void(multiset<int, greater<>>&)> dfs = [&] (multiset<int, greater<>>& s) {
            if((int)cur.size() == n) { // ok
                ans.push_back({});
                for(int i = 1; i < n; ++i) {
                    ans.back().push_back(cur[i] - cur[i - 1]);
                }
                return;
            }
            auto attempt = [&] (int p) {
                vector<int> rm;
                for(auto x : cur) {
                    const auto it = s.lower_bound(abs(p - x));
                    if(it == end(s) || *it != abs(p - x)) break;
                    rm.push_back(*it);
                    s.erase(it);
                }
                if(rm.size() == cur.size()) {
                    cur.insert(lower_bound(begin(cur), end(cur), p), p);
                    dfs(s);
                    cur.erase(find(begin(cur), end(cur), p));
                }
                s.insert(begin(rm), end(rm));
            };
            attempt(*s.begin());
            attempt(cur.back() - *s.begin());
        };

        dfs(d);
        sort(begin(ans), end(ans));
        ans.erase(unique(begin(ans), end(ans)), end(ans));
        for(auto const& v : ans) {
            for(int i = 0; i < n - 1; ++i) {
                cout << v[i] << " \n"[i + 1 == n - 1];
            }
        }
        cout << "-----" << endl;
    }
}

感想

800点といわれて身構えてしまい、難しく考えすぎた。良くないね。
考察はわかりきったところから攻めていかないとなあ。

2019-06-14

AOJ 1322 - ASCII Expression

AOJ 競プロ

問題文

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

解法

今の左端と、上下の区間を持ちながら構文解析を書く。
base の位置は左から見ていって、初めて空白以外が現れた行としてよい。
分数表記のときに余計な space がたくさん入ることがあるので、base を見つける関数を切り分けてそこで左端の位置も更新しながらやればいいと思う。
ほかはいつもの構文解析と全く同じなので特に困ることはない。

最初問題を読んでなくて、有理数表現で計算してたら答えが合わなくて泣いてた。

ソースコード

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

constexpr int mod = 2011;

int add(int a, int b) {
    return (a + b) % mod;
}
int mul(int a, int b) {
    return a * b % mod;
}
int inv(int n) {
    int a = n, b = mod, u = 1, v = 0;
    while(b) {
        const int t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    (u += mod) %= mod;
    return u;
}

int expr(int& x, int y1, int y2, vector<string> const&);
int term(int& x, int y1, int y2, vector<string> const&);
int factor(int& x, int y1, int y2, vector<string> const&);
int powexpr(int& x, int y1, int y2, vector<string> const& s);

int find_base(int& x, int y1, int y2, vector<string> const& s) {
    int res = -1;
    while(res == -1) {
        assert("[base] cannot find base" && x < (int)s[0].size());
        for(int y = y1; y < y2; ++y) {
            if(s[y][x] == '.') continue;
            res = y;
            break;
        }
        x += (res == -1);
    }
    return res;
}

int digit(int& x, int y1, int y2, vector<string> const& s) {
    const int base_y = find_base(x, y1, y2, s);
    assert(isdigit(s[base_y][x]));
    return s[base_y][x++] - '0';
}

int expr(int& x, int y1, int y2, vector<string> const& s) {
    // find base
    const int base_y = find_base(x, y1, y2, s);
    auto res = term(x, y1, y2, s);
    while(x + 1 < (int)s[0].size() && (s[base_y][x + 1] == '-' || s[base_y][x + 1] == '+')) {
        ++x; // space
        const char op = s[base_y][x];
        x += 2;
        const auto r = term(x, y1, y2, s);
        if(op == '+')      res = add(res, r);
        else if(op == '-') res = add(res, mod - r);
        else assert("[expr] invalid op" && false);
    }
    return res;
}

int term(int& x, int y1, int y2, vector<string> const& s) {
    const int base_y = find_base(x, y1, y2, s);
    auto res = factor(x, y1, y2, s);
    while(x + 1 < (int)s[0].size() && s[base_y][x + 1] == '*') {
        ++x; // space
        assert("[term] invalid op" && s[base_y][x] == '*');
        x += 2; // op
        res = mul(res, factor(x, y1, y2, s));
    }
    return res;
}

int factor(int& x, int y1, int y2, vector<string> const& s) {
    const int base_y = find_base(x, y1, y2, s);
    if(s[base_y][x] == '-' && s[base_y][x + 1] == '-') { // fraction
        int x1 = x + 1, x2 = x + 1;
        auto a = expr(x1, y1, base_y, s);
        auto b = expr(x2, base_y + 1, y2, s);
        x = max(x1, x2) + 1;
        return mul(a, inv(b));
    } else if(s[base_y][x] == '-') { // neg
        x += 2;
        return mul(factor(x, y1, y2, s), 2010);
    } else {
        return powexpr(x, y1, y2, s);
    }
}

// primary is in
int powexpr(int& x, int y1, int y2, vector<string> const& s) {
    const int base_y = find_base(x, y1, y2, s);
    int res = 1;
    if(s[base_y][x] == '(') {
        x += 2;
        res = expr(x, y1, y2, s);
        x += 2; // ".)"
    } else {
        assert(isdigit(s[base_y][x]));
        res = digit(x, base_y, base_y + 1, s);
    }
    if(base_y != 0 && isdigit(s[base_y - 1][x])) { // power
        int cnt = digit(x, base_y - 1, base_y, s);
        int t = 1;
        while(--cnt >= 0) {
            t = mul(t, res);
        }
        res = t;
    }
    return res;
}

int main() {
    int n;
    while(cin >> n, n) {
        vector<string> s(n);
        for(auto& ss : s) cin >> ss;
        int p = 0;
        cout << expr(p, 0, n, s) << endl;
    }
}

感想

ついに倒せたー。
個人的には Matrix Calculator のほうが虚無だった．

2019-06-13

AOJ 2017 - Karakuri Doll

AOJ 競プロ

問題文

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

解法

行きの位置、向き、戻りの位置、向きを同時にもって遷移するだけなんだけど、結構めんどくさい。
一番楽なのは DFS で1マスずつ動かしていくのだと思う。
曲がれるタイミングは、行きの位置の前にあるのが壁で、かつ、戻りの位置を回転させたときに目の前に壁がある時。
戻りの位置の曲がる場所の候補は複数あるけど、DFS するときに、戻りの位置と行きの位置を同時に移動するのではなくて、別々に移動させてやると実装がスッキリする。
accomplish になるのは、行き・戻りの両方の位置が M にあって、行きの位置の前に壁があり、戻りの位置の前に壁がないとき。

実装上の注意

DFS にすると手元だとオプションつけないとスタックオーバーフローするかも
到達したかのフラグを vector で持つと MLE するので、グローバルの bool 配列にしよう

ソースコード

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

// direction
// 0: N, 1: E, 2:S, 3:W
constexpr int dx[4] = {0, 1, 0, -1};
constexpr int dy[4] = {-1, 0, 1, 0};
constexpr int dd[2] = {1, 3}; // turn right, left

bool reach1[16][64][4]; // only go to kitchen
bool reach[16][64][4][16][64][4];

int main() {
    int w, h;
    while(cin >> w >> h, w) {
        memset(reach1, false, sizeof(reach1));
        memset(reach, false, sizeof(reach));
        vector<string> v(h);
        for(auto& s : v) cin >> s;

        int sy = -1, sx = -1, sd = -1, gy = -1, gx = -1;
        for(int i = 0; i < h; ++i) {
            for(int j = 0; j < w; ++j) {
                if(v[i][j] == '#') continue;
                if(v[i][j] == 'K') {
                    sy = i, sx = j;
                    for(int d = 0; d < 4; ++d) {
                        if(v[sy + dy[d]][sx + dx[d]] == '#') continue;
                        sd = d;
                    }
                }
                if(v[i][j] == 'M') {
                    gy = i, gx = j;
                }
            }
        }

        function<bool(int, int, int)> go_to_kitchen = [&] (int y, int x, int d) {
            if(reach1[y][x][d]) return false;
            reach1[y][x][d] = true;
            if(y == gy && x == gx) return true;
            bool res = false;
            if(v[y + dy[d]][x + dx[d]] != '#') {
                res = go_to_kitchen(y + dy[d], x + dx[d], d);
            } else {
                res = go_to_kitchen(y, x, (d + 1) % 4);
                res |= go_to_kitchen(y, x, (d + 3) % 4);
            }
            return res;
        };
        function<bool(int, int, int, int, int, int)> dfs = [&] (int y1, int x1, int d1, int y2, int x2, int d2) {
            if(reach[y1][x1][d1][y2][x2][d2]) return false;
            reach[y1][x1][d1][y2][x2][d2] = true;
            if(gy == y2 && gx == x2 && gy == y1 && gx == x1
               && v[y2 - dy[d2]][x2 - dx[d2]] != '#' && v[y1 + dy[d1]][x1 + dx[d1]] == '#') {
                return true;
            }
            bool res = false;
            if(v[y1 + dy[d1]][x1 + dx[d1]] != '#') {
                res = dfs(y1 + dy[d1], x1 + dx[d1], d1, y2, x2, d2);
            } else { // can turn
                for(int i = 0; i < 2; ++i) {
                    const int nd1 = (d1 + dd[i]) % 4, nd2 = (d2 + dd[i]) % 4;
                    if(v[y2 - dy[nd2]][x2 - dx[nd2]] != '#') continue; // front must be wall
                    res |= dfs(y1, x1, nd1, y2, x2, nd2);
                }
            }
            if(v[y2 + dy[d2]][x2 + dx[d2]] != '#') {
                res |= dfs(y1, x1, d1, y2 + dy[d2], x2 + dx[d2], d2);
            }
            return res;
        };

        bool ac = false;
        for(int d = 0; d < 4; ++d) {
            ac |= dfs(sy, sx, sd, sy, sx, d);
        }

        if(ac) {
            cout << "He can accomplish his mission." << endl;
        } else if(go_to_kitchen(sy, sx, sd)) {
            cout << "He cannot return to the kitchen." << endl;
        } else {
            cout << "He cannot bring tea to his master." << endl;
        }
    }
}

感想

最初の実装は行きと帰りの位置を同時に更新（前計算で曲がれる位置を求めておく感じ）してたので、実装が結構重くなってた。
片方ずつ動かすときれいにかけるんだなあ。
かなりバグったが、サンプルが強くて助かった。

2019-06-13

AOJ 2623 - Optimal alpha beta pruning

AOJ 競プロ

問題文

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

解法

普通にαβ法をメモ化再帰でやるだけ。minimize も maximize も同じ。

　dp[v][alpha][beta] := negamax(v, alpha, beta) で最善の選び方をした時の解

子供の順番は next_permutation で全部試してOK。
葉の探索回数をあえて少なくして、その代わりとして返り値を小さくするように潜ったほうがいいこともあるのでは？とか一瞬考えちゃったけど、今の状態から最初に潜る子の結果をどうするかは選択できないので、全探索だけで良かった。

計算量は O(5! n^3) だけど、どう考えてもこんなに遅くならないので、余裕で間に合う。

ソースコード

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

using pii = pair<int, int>;
const int inf = 1e9;

template<typename T>
std::vector<T> table(int n, T v) { return std::vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return std::vector<decltype(val)>(n, std::move(val));
}

int main() {
    int n; cin >> n;
    vector<int> p(n), vs = {-inf, inf};
    for(auto& x : p) {
        cin >> x;
        vs.push_back(x);
        vs.push_back(-x);
    }
    sort(begin(vs), end(vs));
    vs.erase(unique(begin(vs), end(vs)), end(vs));
    auto get_idx = [&] (int val) -> int {
        return lower_bound(begin(vs), end(vs), val) - begin(vs);
    };
    vector<vector<int>> g(n);
    for(int i = 0; i < n; ++i) {
        int k; cin >> k;
        g[i].resize(k);
        for(auto& c : g[i]) {
            cin >> c;
            c--;
        }
    }

    auto max_dp = table(n, vs.size(), vs.size(), make_pair(-inf, 0));
    auto min_dp = table(n, vs.size(), vs.size(), make_pair(inf, 0));
    function<pii(int, int, int, bool)> dfs = [&] (int v, int alpha, int beta, bool is_min) {
        if(g[v].empty()) return make_pair(1, p[v]); // leaf

        auto& res = (is_min ? min_dp[v][alpha][beta] : max_dp[v][alpha][beta]);
        if(abs(res.first) != inf) return res;

        sort(begin(g[v]), end(g[v]));
        do {
            int talpha = alpha;
            pii cur = make_pair(0, -inf);
            for(auto const ch : g[v]) {
                auto val = dfs(ch, get_idx(-vs[beta]), get_idx(-vs[talpha]), is_min);
                val.second = -val.second;
                cur.first += val.first;
                if(val.second >= vs[beta]) {
                    cur.second = val.second;
                    break;
                }
                if(val.second > vs[talpha]) {
                    talpha = get_idx(val.second);
                }
            }
            if(cur.second == -inf) { // not occured val.second >= beta
                cur.second = vs[talpha];
            }
            if(is_min) res = min(res, cur);
            else       res = max(res, cur);
        } while(next_permutation(begin(g[v]), end(g[v])));

        return res;
    };

    cout << dfs(0, 0, vs.size() - 1, true).first << " " << dfs(0, 0, vs.size() - 1, false).first << endl;
}

感想

問題文を読むのに少し手間取った。

2019-06-12

AOJ 2646 - Tournament

AOJ 競プロ

問題文

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;
}

感想

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