AOJ 2693 JAG-channel II

問題文

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

解法

いかにもな bitDP 感がある．
しかしそれでもなんらかの形で順番は保持しないとどうしようもなさそうに見える．
うまくやれば状態に順列持てたりしないかな～と制約を読むと N - 3 <= K <= N - 1 とかいう怪しすぎる制約がある．
冷静に考えてみると，今使ったやつがわかれば先頭 K 文字は確定するので，残りの文字だけの並びを状態に持てば十分である．
N - K はたかだか3だから，この並びの状態は 6 通りしか無い．
したがって，
dp[S][ord] := 使った人の集合が S で，その時のスレッドの並びが ord であるときから始めて，辞書順最小の答え
とするメモ化再帰DPを書く．
あとは一番最初に何を使うか，そしてその時に考えられる初期状態の順列はなにか，を全探索すると解ける．

計算量は O(2^n * n^2 * 6 * 6) ぐらい．

こういう辞書順最小構築はメモ化再帰DPで書くと実装がきれいになりやすいと思う．

ソースコード

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<string> post(n);
    for(int i = 0; i < n; ++i) {
        cin >> post[i];
    }

    vector<map<string, string>> dp(1 << n);
    function<string(int, string)> rec = [&](int S, string order) {
        if(S == (1 << n) - 1) return string();
        if(dp[S].count(order)) return dp[S][order];
        string& res = dp[S][order];
        res = "invalid";
        for(int i = 0; i < n; ++i) {
            if(S & (1 << i)) continue;
            int idx = 0;
            for(int j = 0; j < n; ++j) {
                if(post[i][idx] == order[j]) {
                    idx++;
                }
            }
            if(idx != k) continue;
            string nord = post[i];
            reverse(begin(nord), end(nord));
            for(auto c : order) {
                if(find(begin(nord), end(nord), c) == end(nord)) {
                    nord += c;
                }
            }
            string s = rec(S | (1 << i), nord);
            if(s != "invalid") {
                res = (char)('A' + i) + s;
                break;
            }
        }
        return res;
    };

    string ans = "Z";
    for(int fst = 0; fst < n && ans == "Z"; ++fst) {
        string s = post[fst];
        reverse(begin(s), end(s));
        string remain;
        for(char c = 'A'; c < 'A' + n; ++c) {
            if(find(begin(s), end(s), c) == end(s)) {
                remain += c;
            }
        }
        do {
            string ord = s + remain;
            auto t = rec(1 << fst, ord);
            if(t != "invalid") {
                ans = min(ans, (char)('A' + fst) + t);
            }
        } while(next_permutation(begin(remain), end(remain)));
    }

    cout << ans << endl;
}

感想

N - 3 <= K <= N - 1 とか書かれると意外と気が付かないもんだなあ（反省）．