cafelier@SRM

SRM491 600

あとで | 11:38 |

• 上手い問題だなあ

class PrefixTree { public:
   static vector<int> wordToFreq( const string& word )
   {
      vector<int> freq(26);
      for(int i=0; i<word.size(); ++i)
         freq[word[i]-'a']++;
      return freq;
   }

   static vector< vector<int> > wordsToFreqs( const vector<string>& words )
   {
      vector< vector<int> > freqs;
      transform(words.begin(), words.end(), back_inserter(freqs), &wordToFreq);
      return freqs;
   }

   static int commonPrefix(const vector< vector<int> >& freqs, int s)
   {
      vector<int> common;
      for(int first=1,i=0; (1<<i)<=s; ++i)
         if( s & (1<<i) )
            if( first ) {
               common = freqs[i];
               first = 0;
            } else {
               for(int k=0; k<26; ++k)
                  common[k] = min(common[k], freqs[i][k]);
            }
      return accumulate(common.begin(), common.end(), 0);
   }

   int getNumNodes(vector<string> words) 
   {
      const int N = words.size();
      const vector< vector<int> >& freqs = wordsToFreqs(words);

      vector<int> dp(1<<N);
      for(int s=1; s<(1<<N); ++s)
      {
         dp[s] = 1;
         for(int i=0; i<N; ++i)
            if( s & (1<<i) )
               dp[s] += words[i].size();

         int cp = commonPrefix(freqs, s);
         for(int ss=s-1; ss&=s; --ss)
            dp[s] = min(dp[s], dp[ss]+dp[s&~ss]-cp-1);
      }
      return dp[(1<<N)-1];
   }
};

• 文字列集合 s から作る trie のベストスコアは
• s = ss ∪ (s/ss) に二分割して
  • ssのベストスコア + (s/ss)のベストスコア - s全体の共通部分
• になる（直感的にはなりそうだけど証明できてない…）
• ということに気づけばこれをDPでそのまま書くだけ。