の先頭から 文字目までの部分文字列で(ビットマスクで表現された)集合 に含まれるハッシュタグを全て使えるか
と定義した、要素が真偽値の二次元配列を埋めていく bit DP でこの問題を解くことができます。ただし、遷移に必要な の部分文字列と の一致判定をローリングハッシュなどで高速化する必要があります。
解答例 (C++17) (ローリングハッシュの長いライブラリが貼ってあり、488 行目から main
関数が始まります)
以下にこの解法に辿り着くまでの考察過程の一例と解答の擬似コードを示します。ただし、入力の受け取りやローリングハッシュのコードは省略しています。
まず「同一のハッシュタグを複数回使用しても 回目以降の使用で新たに拡散力を得ることはできない」という設定を外して、同一のハッシュタグを複数回使った場合にはその回数分だけ拡散力が得られる場合を考えます。(どのハッシュタグを今まで使ったかは考えなくてよくなります。)
その問題に対しては「 ではなく『 の先頭から 文字目までの部分文字列』が として与えられていた場合の問題の答え(拡散力の総和の最大値)」を格納する配列を用意して が小さい方から埋めていく動的計画法で正解が得られます(EDPC - F と同じような発想です)。
// score[i] を S の先頭から i 文字目までの部分文字列が S として与えられていた場合の問題の答えにしたい // ここで score[0] は 0 と定義する score = (要素数 N+1 の配列; 要素は 0 で初期化) for (i = 1; i <= N; i++) { // 取りあえず、文字列が長くなって損することは無いので score[i-1] を入れておく // でも本来の score[i] はもっと大きいかもしれない score[i] = score[i-1] // ハッシュタグにできる文字列 T[j] を全探索して、i 文字目まで見ることによって // 新たに使えるようになったハッシュタグがあればそれを使って拡散力が増えるか調べる(増えるなら更新する) for (j = 0; j < M; j++) { if (S の i 文字目までの部分文字列の末尾 == T[j]) { score[i] = max(score[i], score[i - (T[j] の長さ)] + p[j]) } } } // score[N] は元の S に対する答えになっている print(score[N])
一方、元の問題には「同一のハッシュタグを複数回使用しても 回目以降の使用で新たに拡散力を得ることはできない」という設定があります。よって「どのハッシュタグをこれまでに使ったか」という情報も持っておく必要があることが分かります。
// score[i][a] は S の先頭から i 文字目までの部分文字列が S として与えられていた場合で、 // 集合 a (ビットマスクで表現する)に含まれるハッシュタグを全て使える場合に使ったときのツイートの拡散力の総和 // (使えない場合は score[i][a] = 0) score = (要素数 N+1 × 2^M の二次元配列; 要素は 0 で初期化) // ...(bit DP)
この方法で元の問題に正解することはできますが、使ったハッシュタグの集合が決まっている場合にはツイートの拡散力の総和がそこで定まるのでこの二次元配列の要素を真偽値にすることで使用メモリを削減することができます。
// possible[i][a] が true であるとき、かつそのときに限り S の先頭から i 文字目までで // ハッシュタグの集合 a に含まれるハッシュタグを全て使うことができる possible = (要素数 N+1 × 2^M の真偽値の二次元配列; 要素は false で初期化) // 「S の先頭 0 文字で空集合に含まれるハッシュタグを全て使うことはできる」 possible[0][0] = true for (i = 1; i <= N; i++) { for (a = 0; a < (1 << M); a++) { // もし前の文字までで既に可能なら調べる必要もない if (possible[i-1][a]) { possible[i][a] = true continue } // i 文字目まで見ることによって a に含まれるハッシュタグ T[j] が新たに使えるようになったか調べる for (j = 0; j < M; j++) { if (a の j ビット目が 0、すなわちハッシュタグ T[j] は a に含まれない) { continue } if (S の i 文字目までの部分文字列の末尾 == T[j] && possible[i - (T[j] の長さ)][a ^ (1 << j)]) { possible[i][a] = true break } } } } // 最後に possible[N][a] が true であるようなハッシュタグの集合 a について、 // 含まれるハッシュタグの拡散力の総和が最も大きいものを計算して出力する score = 0 for (a = 0; a < (1 << M); a++) { if (possible[N][a]) { score = max(score, 集合 a に含まれるハッシュタグの拡散力の総和) } } print(score)
S の i 文字目までの部分文字列の末尾 == T[j]
というように文字列の比較をしていますが、これはローリングハッシュを前計算しておくと定数時間で行えるようになります。よって三重ループの内側の処理は定数時間で実行可能で、この問題を 時間で解くことができます。
(他の解法があれば教えてください)