Codeforces Round #302 (Div.1) C. Remembering Strings

問題文

http://codeforces.com/contest/543/problem/C

解法

n <= 20 から bitDP が頭をよぎって，実際そのとおりなんですが，この制約にはもう1つ意味がある．
それは，a-z の26文字より小さいので，各文字は1箇所変更するだけで easy to remember にできるということ．
つまり，ある文字列 i を easy to remember にするには，以下のどちらかしかない．

ある位置 j に着目して，a[i][j] のコストを払う
ある位置 j に着目して，位置 j の他の文字列をすべて見たときに s[i][j] と同じ文字のものを，すべて easy to remember にする（これは，この集合の中で最もコストが大きいもの以外を変えれば良い）

場合によっては，結果的に場合2の部分集合だけ変えるような方法が最適なことがあるかもしれないが，これは1つ目のケースを何回か適用したものであると考えられるので，これで全ケース列挙できる．

bitDP の遷移が問題で，多分いつもどおり bitDP をやろうとすると，各集合 S （ビットで管理してるやつ）から遷移の候補がたくさんあって困る．
そこで，各集合 S について，まだ使ってない文字列の中で最小インデックスの文字列を easy to remember にする遷移だけ考えると，遷移のオーダーが削減できる．
このためにはループの順番を S -> i にしないといけない（0 <= i < m）．
遷移自体は先の2パターンだけ考えればよいので，トータル O(m2^n + 前計算) でできる．

ソースコード

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

constexpr int inf = 1e9;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for(int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    vector<vector<int>> a(n, vector<int>(m));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    vector<vector<int>> cost(m, vector<int>(n, inf));
    vector<vector<int>> mask(m, vector<int>(n));
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n; ++j) {
            vector<int> cs;
            int msk = 0;
            for(int k = 0; k < n; ++k) {
                if(s[j][i] == s[k][i]) {
                    cs.push_back(a[k][i]);
                    msk |= (1 << k);
                }
            }
            sort(begin(cs), end(cs));
            cost[i][j] = accumulate(begin(cs), end(cs) - 1, 0);
            mask[i][j] = msk;
        }
    }

    vector<int> dp(1 << n, inf);
    dp[0] = 0;
    for(int S = 0; S < (1 << n) - 1; ++S) {
        int lb = 0;
        while(S & (1 << lb)) ++lb;
        for(int i = 0; i < m; ++i) {
            dp[S | (1 << lb)] = min(dp[S | (1 << lb)], dp[S] + a[lb][i]);
            dp[S | mask[i][lb]] = min(dp[S | mask[i][lb]], dp[S] + cost[i][lb]);
        }
    }

    cout << dp.back() << endl;
}

感想

普通にやろうとすると O(3^n) が出てきてしまってつらくなる．
ちょっと工夫して考える遷移を減らす，みたいなのは bitDP だと結構見る．
例えば O(n^2 2^n) -> O(n2^n) とか，O(3^n) -> O(n^2 2^n) とか．
こないだの ARC でも見たような……．