Typical DP Contest - Q 連結

Q: 連結 - Typical DP Contest | AtCoder

  • わけがわからないよ simezi_tan ...(´・ω・`)
  • 他の人の解説記事をみってもさっぱりわからず、悩みに悩んだ問題。
  • ループの処理上、いろんな状態遷移を計算しているが、結局初期状態からの遷移が可能なもの以外は消えてしまう。と理解(解釈?)した。
  • 下のコードでは文字の構築を文字列の右端を末尾として追加して作っているが左端を末尾として追加していくとちょっとは実装は楽かも。(Typical DP Contest Q - 連結 - simezi_tanの日記とかは逆になっているっぽい)
const int MOD = (int)(1E+9)+7;
class q_connect {
public:
    //
    // wi が 01 11 0 00 ... のとき
    //
    // xxx 01 11 0
    // xxx 0 11 10
    //
    // のような重複をどうやって検知するのか?
    // wi の組み合わせを考えては重複を排除できない。
    // ---------------------------------------------------------------------
    //
    // wi を組み合わせて文字列を作るのではなくて
    // 0 or 1 を追加していくとき wi の組み合わせでできる文字列であるかどうかを判定できればよい。
    //
    // 以下のような手順を考える
    //
    // a. 0 or 1 を追加して文字列を作っていく
    // b. 追加して文字列を伸ばすたびにセパレータから末尾までを wi で分解していく
    // ex)
    //  wi = 01, 010, 10
    //  1. 0
    //  2. 01|
    //  3. 01 1
    //  4. 01 10|
    //  5. 01 10 0
    //  6. 01 10 01|
    //  7. 01 10 01 0|        <- セパレータから末尾までが 010 になっているかで判定
    //           ~~~~
    //  8. 01 10 01 0 0
    //     :
    //  このようにできるだけ多くのセパレータを入れてゆくことを考える
    //  L 文字目構築したときに末尾にセパレータを入れられればその文字列は条件を満たすものとなる。
    //
    //  ...00000000 のようにセパレータがいれられない末尾列が 8 文字を超えると wi で構築できないことが確定するので
    // そのような文字列はいらない。またセパレータを末尾に追加できるかの判定は wi が最大 8 文字なので現在の位置から
    // 8 文字前までの分割位置がわかればよい。
    //
    //  よって末尾 7 文字までと分割方法を保持しておく。
    //  (8文字目は現在追加する 0 or 1 なのでわかっている)
    //  つまり
    //
    // dp[i][j][k] := 文字列の長さが i で末尾 7 文字が j で分割方法が k であるような組み合わせの数
    //
    // とすればよい。
    //
    // 以下 (i,j,k) -> (i+1,j',k') の遷移を考える。
    //
    //  * 末尾 8 文字を bits とする。末尾に 0 or 1 を追加するとき bits の先頭は以降の判定で不要になる。
    //
    //     ... 010 010 10
    //         ---bits---
    //  -> ... 010 010 101
    //  -> ... x10 010 101
    //          --bits'---
    //
    //  * このとき同じ bits' に遷移するような別の文字列(上の例では bits=11001010 なるもの)は明らかに
    //    現在の文字列と異なるので、文字列総数としてマージできる。(重複がない)
    //
    //  dp[i+1][bits'][k'] = dp[i][bits1][k1] + dp[i][bits2][k2]
    //
    //    (i,bits1,k1) -> (i+1,bits',k')
    //    (i,bits2,k2) -> (i+1,bits',k')
    //
    //   問題は bits が同じで分割が異なるものが同じ状態遷移に移動しないかどうかとなる。
    //
    //   (i,bits,k1) -> (i+1,bits',k')      (k1 != k2)
    //   (i,bits,k2) -> (i+1,bits',k')      これらは重複しうる
    //
    //    ...010 010 1x
    //    ...01001  01x       文字列として同じ
    //       ---bits---
    //
    // しかし  k -> k' の遷移は分割文字列のあるセパレータから最後までが wi でちょうど表現できるときのみ
    // なので
    //
    // (bits,k1) = 01 00 10 1  -> (bits',k1') = 01 00 10 10
    // (bits,k2) = 01 00  101  -> (bits',k2') = 01 00  1010
    //
    // のように k1!=k2 ならその遷移先は必ず異なる。
    // (遷移するときはかならず右端に分割位置がくるので k1->k2 のような遷移もありえない)
    // つまりこの dp は i -> i+1 の遷移で
    //
    //  * bits が異なるものの結果をマージ
    //  * 分割位置がことなるものによる結果はマージしないで各 dp に持ち続けて更新
    //
    // を行っている。
    //
    // そしてセパレータの追加は現在の分割からできるだけ多く追加されるようにしているので
    // dp[i][j][k] > 0 なる状態の数え上げには (0,0,1) からの遷移だけが含まれる。(※)
    //
    // 例えば wi = 01, 010, 10 として 01010 という文字列を構築するとき
    //  010 10 に対応する遷移状態はありえない。(01 0 10 という遷移状態が最も多くの分割をもつため。)
    // ありえない遷移状態のからの寄与は初期化で 0 になっている。なので最後にそのまま加えてよい(※)
    //
    void solve(void) {
            int N, L;
            cin>>N>>L;
            // word[len][bit] := 長さが len の bit 表現があるか?
            // len があるのは
            // 0001
            //    1
            // を区別するため
            vector<vector<bool>> word;
            vector<pair<int,int>>   w;
            mdv::resize(word, 9, (1<<8), false);

            REP(i, N)
            {
                int bit = 0;
                string s;
                cin >> s;
                // bit として変換する
                REP(j, s.length())
                    if(s[j] == '1')
                        bit |= (1<<(s.length()-1-j));
                word[s.length()][bit] = true;
                w.emplace_back(s.length(),bit);
            }

            //
            // dp[i][j][k] := 文字列の長さが i で末尾 7 文字が j で分割方法が k であるような組み合わせの数
            // 分割方法はセパレータを置く位置として表現する。(1<<8)
            // ...1 01 011 0
            //   0 1 01 001 0
            vector<vector<vector<ll>>> dp;
            mdv::resize(dp, L+1, (1<<7), (1<<8), 0);
            dp[0][0][1] = 1;    // 右端に separator がある状態から始める

            const int mask8 = (1<<8)-1;
            const int mask7 = (1<<7)-1;

            REP(i, L)
            REP(j,   (1<<7))    // 末尾 7 文字
            for (int sep = 1; sep < (1<<8); ++sep)    // seprator 位置
            REP(d, 2)
            {
                // 末尾 8 文字を作る
                int bits = ((j<<1)|d) & mask8;
                int sepD = (sep<<1);

                int k = 0;
                for (;k < 9; ++k)
                {
                    if ( !((1<<k) & sepD) )
                        continue;
                    // セパレータから末尾までの bit を抜き出す
                    int mask = ((1<<k)-1);
                    if (k <= 8 && word[k][bits&mask]) // 分割方法が変わるケース
                        sepD |= 1;     // セパレータを右端に追加
                }
                // 遷移先にマージ
                (dp[i+1][bits&mask7][sepD&mask8] += dp[i][j][sep]) %= MOD;
            }
            ll ans = 0;
            REP(j, (1<<7))
            for (int k = 1; k < (1<<8); ++k)
            {   // bits が等しいが分割方法がことなるケースであるがこれらで重複することはない。
                // (cached されている 7 bit よりも前で差が出ている。)
                // (※)よりこれらも加算が必要
                if (k & 1)  // 末尾がちゃんとくぎられているものを数える
                    (ans += dp[L][j][k]) %= MOD;
            }
            cout << ans << endl;
    }
};