Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1780-99a29f48
この記事にトラックバックする(FC2ブログユーザー)

SRM491 DIV1 MEDIUM - PrefixTree (この記事を編集する[管理者用])

Source

TopCoder SRM491 DIV1 MEDIUM (600pt)
Problem Statement
SRM491 DIV1 自分の参加記録

問題概要

長さ50以下の文字列がN個 (16以下) 与えられる.文字列はアルファベット小文字のみからなる.
各文字列の中の文字を適当に入れ替えても良い.
与えられた文字列でTrieを作ったときの最小ノード数を求める問題.

解法

O(N^3)時間,領域量O(N^2)のグループ分けのDP.
現在考えてる文字列を2つの集合にわけて,全てに共通する文字列のノードを1つにまとめるため省略できると考える.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define rep(i,n) for(i=0;i<n;i++)
#define REP(i,a,b) for(i=a;i<b;i++)

int n;
int dp[77777], num[77777];
int in[52][26];

class PrefixTree {
public:
int getNumNodes(vector <string> words) {
  int i,j,k,mx;
  int tmp;
  int res;

  n=words.size();
  rep(i,n) rep(k,26) in[i][k] = 0;
  rep(i,n) rep(j,words[i].size()) in[i][words[i][j]-'a']++;

  num[0] = 0;
  REP(i,1,1<<n){
    num[i] = 0;
    rep(k,26){
      mx = 1000;
      rep(j,n) if(i&1<<j) if(mx > in[j][k]) mx = in[j][k];
      num[i] += mx;
    }
  }

  rep(i,1<<n) dp[i] = 1000000000;
  dp[0] = 0;
  rep(i,n) dp[1<<i] = num[1<<i];
  
  REP(i,1,1<<n){
    for(j=((i-1)&i);j;j=((j-1)&i)){
      k = (i^j);
      tmp = dp[j] + dp[k] - num[i];
      if(dp[i] > tmp) dp[i] = tmp;
    }
  }

  res = dp[(1<<n)-1] + 1;

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1780-99a29f48
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。