Typical DP Contest Q - 連結

競プロ AtCoder TDPC

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_concatenation

解法

同じ文字列を複数選んでも良いので，何を使ったかを保存する必要はないです．
今作っている文字列の状態がどうか，がわかれば十分．

そこで突然ですが，以下のような dp をします．
dp[i][j][k] := 文字列が i 文字目まで出来ているとき，直近 7 文字が j で，単語の区切り位置としてありえるのが k であるような場合の数

この DP において，今できている文字列から次の新しい文字列を作る時，単語単位で追加していくのではなく，文字単位(0 or 1)で追加していくと，自然に単語間の重複を防ぐことができます．

さて，1文字追加したあとに，単語の区切りの位置としてあり得る位置から末尾までの文字列と等しい文字列が単語の中に含まれていれば，末尾も区切り位置としてあり得る位置になります．

求める答えは，きちんと単語列で表現できるものなので，dp[L][i][末尾が区切り位置になっているもの] の総和です．
（末尾が区切り位置になっている <-> 最下位のビットが 1 である）

実装に関しては，直近7文字と，区切り位置の8箇所分はビットで持ちます．
1文字追加は左シフトで，末尾の情報を OR で追加してやると良いです．


どうしてこれで重複カウントされないかという大雑把な説明をします．
そもそもどうして重複カウントが起こるのかというと，例えば "0011"，"00"，"11"という単語があったときに，"0011" を作るパターンが2通りあり，これは単語ごとに追加する遷移では区別するのが難しいということに起因します．
上の状態で表現するなら，空文字の状態から "0011 |"が作れてしまうし，"00 |"の状態から"00 | 11 |" が作れてしまって，これらが別にカウントされてしまうということです．

しかし一文字ずつ遷移し，区切り位置を保存しておくDPにおいては，"0011"という文字列は必ず "00 | 11 |" というパターンにマッチして，"0011 |"というパターンにはマッチしません．これは遷移を考えればあきらかにわかることです．
（"0" に '0' を追加するときに，必ず次状態は "00 |" になるから．）


以下例．
w = {"01", "10", "11"}
今 "010" まで出来ているとすると，区切り位置としてありえるのは "01 | 0" の1箇所だけ．
ここに 1 を追加しようとすると，"01 | 01"になる．"01" は単語列にあるので，次の状態は "01 | 01 |" になる．
0 を追加しようとすると，"01 | 00" になるが，"00" は単語列にないので，次の状態は "01 | 00" になる．

ソースコード

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

constexpr int M = 1e9 + 7;

int main() {
    int N, L;
    cin >> N >> L;
    vector<vector<int>> w(16, vector<int>(1 << 8));
    for(int i = 0; i < N; ++i) {
        string s;
        cin >> s;
        int b = 0;
        for(int j = 0; j < (int)s.size(); ++j) {
            b |= (s[j] - '0') << j;
        }
        w[s.size()][b] = 1;
    }

    vector<vector<vector<int>>> dp(128, vector<vector<int>>(1 << 7, vector<int>(1 << 8)));
    dp[0][0][1] = 1;
    for(int i = 0; i < L; ++i) {
        for(int j = 0; j < 1 << 7; ++j) {     // 直前の 7 文字
            for(int k = 0; k < 1 << 8; ++k) { // 区切りの位置
                for(int l = 0; l < 2; ++l) {  // 次に追加する文字 0 or 1
                    int f = 0;                // 次に l を追加したとき，ある接尾辞に対応する単語があるか？
                    for(int m = 0; m < 8; ++m) {
                        int b = ((j << 1) | l) & ((1 << (m + 1)) - 1);
                        if(k >> m & 1 && w[m + 1][b]) { // 位置 k で区切った後ろの文字列に対応する w がある
                            f = 1;                      // 区切り位置として末尾が増える
                        }
                    }
                    int nj = (j << 1) & 127 | l;
                    int nk = (k << 1) & 255 | f;
                    (dp[i + 1][nj][nk] += dp[i][j][k]) %= M;
                }
            }
        }
    }

    int res = 0;
    for(int i = 0; i < 1 << 7; ++i) {
        for(int j = 0; j < 1 << 7; ++j) {
            (res += dp[L][i][(j << 1) + 1]) %= M;
        }
    }
    cout << res << endl;
}

感想

直前の7文字まで持てば十分 <- これは自然な発想
区切りの位置を持つ <- 文字列を単語のブロックに分けて表現したいという発想なので，まあ自然
1文字ずつ見れば重複も避けられるよね <- これが一番気づきにくくて，一番大切なところかな？

最初の2つまでは考えるけど，重複どうするかが辛くて答え見ちゃった．
この問題は個人的に結構面白かったです．