SRM330 D1M PrefixFreeSubsets

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

文字列の集合の全ての要素が，他の要素で始まっていない時に$prefix-free$という．与えられた文字列集合の部分集合の内，$prefix-free$である集合の個数を答える．

重複をどう列挙すればいいの全然分からなかった．解説を見た． $$ dp[i] := i番目以降のprefix-freeの集合の個数 $$ として動的計画法．基本的に，$dp[i+1]$が分かっているときに，$i$番目の文字列を追加したい場合は，その文字列を選ぶ場合と選ばない場合の$2$通りがあるので単純に$2$倍で良い．しかし，選ぶ場合に$prefix-free$になってしまってはいけないので，そうではない所から遷移させる．一度辞書順でsortしてしまえば，$pfefix$が同じ場合はsort後に隣接しているはずなので，同じにならない所にまで$1$個ずつずらせばよい．このずらした場所を$j$とすると，$i$番目の文字を選ばない時は$dp[i+1]$，選ぶ時は$dp[j]$なのでこれらの和が$dp[i]$となる．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

bool check(string s, string t) {
  if(s.size() > t.size()) swap(s, t);
  rep(i, s.size()) {
      if(s[i] == t[i]) continue;
      return false;
  }
  return true;
}

class PrefixFreeSubsets {
  public:
  long long cantPrefFreeSubsets(vector <string> words) {
      int n = words.size();
      vector<string> s = words;
      sort(s.begin(), s.end());

      ll dp[55];
      memset(dp, 0, sizeof(dp));
      dp[n] = 1;

      for(int i = n - 1; i >= 0; i--) {
          int j = i + 1;
          while(j < n && check(s[i], s[j])) j++;
          dp[i] = dp[i+1] + dp[j];
      }

      return dp[0];
  }
};
Dec 2nd, 2016
srm, topcoder, 動的計画法