予選B-B エターナルスタティックファイナル 解説
メモ化再帰や動的計画法を使って、並べ方を数え上げます。
f(i) = 呪文Sの先頭からi文字目までの部分文字列についてのフレーズの並べ方の数
と定義すると、
= 1 (i = 0)
f(i) = ∑j{ f(i-|Tj|) } (i > |Tj| かつ Sのi-|Tj|から|Tj|文字がTjとマッチする)
= 0 (それ以外)
という漸化式が成り立ち、f(|S|)
が答えです。
これをそのままプログラミング言語の再帰関数にすると、制限時間内に処理は終了しません。
f(|S|)
の計算途中でf(i)
が何度も呼び出されることになりますが、f(i)
はi
が同じならば必ず同じ値になることを利用し、結果を配列等に記録しておくことで無駄な再計算を減らすことができます。
数え上げる途中で1000000007で割った余りを計算することにより、32bit整数型で計算することができます。
C++言語での解答例です
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int N;
string S;
vector<string> T;
vector<int> memo;
int f(int i){
if(i < 0)return 0;
if(i == 0)return 1;
if(memo[i] != -1)return memo[i];
int ret = 0;
for(const string& t : T)
if(i >= t.length() && S.compare(i - t.length(), t.length(), t) == 0)
ret = (ret + f(i - t.length())) % 1000000007;
return memo[i] = ret;
}
int main(){
cin >> N;
cin >> S;
T.resize(N);
for(int i=0; i<N; ++i)cin >> T[i];
memo = vector<int>(S.length() + 1, -1);
cout << f(S.length()) << endl;
return 0;
}
また、配列と単純なループを使って記述することもできます。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
int N; cin >> N;
string S; cin >> S;
vector<string> T(N); for(int i=0; i<N; ++i)cin >> T[i];
vector<int> dp(S.length() + 1);
dp[0] = 1;
for(int i=1; i<=S.length(); ++i)
for(const string& t : T)
if(i >= t.length() && S.compare(i - t.length(), t.length(), t) == 0)
dp[i] = (dp[i] + dp[i - t.length()]) % 1000000007;
cout << dp[S.length()] << endl;
return 0;
}
ちなみに、タイトルはKLabが開発したゲームエンジンPlaygroundのソースコード中のコメントが元ネタでした。