天下一プログラマーコンテスト2016本選（オープン） C & D

http://tenka1-2016-final-open.contest.atcoder.jp/
　なんか異様に眠かったのでこの日は二問だけやってやめてしまったんですが、気になるDPがあったので復習。

Cは文字列ナップサックみたいな問題。

dp[i] := 部分文字列[0, i]に対する最大のスコア
とすると、部分文字列[i + 1, j]がスコアs[k]の文字列だったとき　dp[j] = max(dp[j], dp[i] + s[k])のように更新できます。

このとき、jを辿っていったとすると文字列比較にやたら時間がかかりそうなのでもっと効率よくやることを考えます。
具体的にはTrieを持って、iを全部辿るときiから始まるスコア付き文字列があるかどうか見て配るDPをします。

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

template<int Code>
struct Node_ {
    Node_* next[Code];
    int w;
    Node_() : w(0)
      { fill_n(next, Code, nullptr);}
};

typedef Node_<26> Node;

Node* buildTrie(const vector<string>& p, const vector<int>& w) {
    Node* root = new Node();
    for(int i : _in(p.size())) {
        Node* cur = root;
        for(const auto& c : p[i]) {
            int k = c - 'a';
            if(cur->next[k] == nullptr)
              cur->next[k] = new Node;
            cur = cur->next[k];
        }
        cur->w = max(cur->w, w[i]);
    }
    return root;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    
    string s; cin >> s;
    int M; cin >> M;
    vector<string> p(M);
    for(auto& x : p) cin >> x;
    vector<int> w(M);
    for(int& x : w) cin >> x;

    Node* root = buildTrie(p, w);

    int N = s.size();
    vector<int> dp(N + 1, 0);
    for(int i : _in(N)) {
        dp[i + 1] = max(dp[i + 1], dp[i]);
        Node* cur = root;
        for(int len : _in(200)) {
            int j = i + len;
            if(j >= N) break;
            cur = cur->next[s[j] - 'a'];
            if(cur == nullptr) break;
            dp[j + 1] = max(dp[j + 1], dp[i] + cur->w);
        }
    }

    cout << dp[N] << endl;
}

Trieは初めて実装したんですけど面白いですね。機会があればaho-corasickとかと併せてブログにまとめたいです。

DはいかにもビットDPっぽいなあという感じの問題。
TSPの印象が強いせいか最後にやった仕事を持たないといけないと勘違いしていてハマりました。そんなもの持ってても何の役にも立たないのに…。

dp[i][j][k] := ビット集合iの仕事を終え、j回移動し、いまオフィスkにいるとき

でDP

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

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N, M, C, D;
    while(cin >> N >> M >> C >> D && N) {
        vector<vector<int>> cost(2, vector<int>(N, 0));
        for(int i : _in(N))
          for(int k : _in(2))
            cin >> cost[k][i];
        vector<int> dep(N, 0);
        for(int _ : _in(M)) {
            int x, y;
            cin >> x >> y;
            --x; --y;
            dep[y] |= 1 << x;
        }

        vector<vector<int>> dp(1 << N, vector<int>((N + 1) * 2, 1e9));
        dp[0][0] = dp[0][N + 1] = 0;
        for(int s : _in(1 << N)) {
            int cnt = __builtin_popcount(s) + 1;
            for(int i : _in(cnt)) for(int k : _in(2)) {
                int x = dp[s][(N + 1) * k + i];
                int _k = k ^ 1;
                for(int j : _in(N)) if((~s & (1 << j)) && (dep[j] & s) == dep[j]) {
                    int ns = s | (1 << j);
                    dp[ns][(N + 1) * k + i] = min(dp[ns][(N + 1) * k + i], x + cost[k][j]);
                    dp[ns][(N + 1) * _k + i + 1] = min(dp[ns][(N + 1) * _k + i + 1], x + cost[_k][j] + C * i + D);
                }
            }
        }
        int S = (1 << N) - 1;
        cout << *min_element(dp[S].begin(), dp[S].end()) << endl;

//        for(int i : _in(1 << N)) for(int j : _in(N + 1)) for(int k : _in(2))
//          cout << static_cast<bitset<8>>(i) << ' ' << j << ' ' << k << ' ' << dp[i][k * (N + 1) + j] << endl;
    }
    return 0;
}

この解答は3600msくらいかかりました。
ベクターのオーバーヘッドもあるんだろうけど、やっぱりキャッシュ効率のせいかな？という気がします。
まあ面倒だから書きなおしたりはしないんですが……。