解いた問題のソースコードと解説など。


SRM 330 Div1 Medium PrefixFreeSubsets

問題

どの要素も互いの接頭辞にならないような文字列の集合をprefixfreeな集合と言う。与えられた文字列の集合のうちprefixfreeとなるような部分集合の数を求めよ。空集合も含める。

やりかた

メモ化再帰による。
文字列をソートするとprefixfreeとならないような文字列はひとつづきに現れるので都合が良い。そこで各文字列にたいして、prefixfreeとなる次点の文字列の番号を予め計算する。
その上で、ある文字列を使用した場合と使用していない場合に分けて再帰を繰り返していく。

以下ソース。

int N;
int p[100];
ll dp[100];

class PrefixFreeSubsets {
public:
  ll rec(int idx){
    if(idx == N) return 1;
    if(dp[idx] != -1) return dp[idx];
    ll notuse = rec(idx + 1); //文字列idxはsubsetに含めない場合
    ll use =    rec(p[idx]);  //含める場合
    return dp[idx] = notuse + use;
  }
  long long cantPrefFreeSubsets(vector <string> words){
    N = words.size();
    sort(ALL(words));
    memset(dp, -1, sizeof(dp));
    memset(p, 0, sizeof(p));
    for(int i = 0; i < N; i++){
      int j;
      for(j = i + 1; j < N; j++) //文字列iが接頭辞とならないような次点の文字列を計算
	if(words[j].length() < words[i].length() ||
	   words[j].substr(0, words[i].length()) != words[i]) break;
      p[i] = j;
    }
    return rec(0);
  }
};
しょげないでよBaby 眠れば治る