Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM528 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

長さN (40以下) のoかxからなる文字列が与えられる.文字列の長さNは偶数.
互いに共通部分のない長さN/2の部分列を2つ選んで,それを一致させる方法は何通りあるかを求める問題.
つまり,N/2文字選んで,それだけ取り出して順番を変えずにくっつけた文字列と,残った文字をそのままくっつけた文字列が一致するようなN/2文字の選び方の数を求める問題.

解法

解法を何通りかある.
部分列に含まれるoの数とxの数は簡単に計算可能で,それから考えうる部分列は最大でもC(20,10)通り.
後は,O(N^2)のDPでそれぞれに対して選び方のパターン数をカウントする.(自分の解答はこれ)
他の方法は,文字列を半分に分けて,それぞれ全列挙で2^(N/2)パターン作って,くっつける.
後は,どこまで文字を処理したか,まだ一致していない部分の文字列を状態としてDPしたとしても,一致してない部分の文字列は長さ20までしか考えなくてよいので,状態数は最大で40*2^20でなんとかなる.

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

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

#define ll long long

class SPartition {
public:
ll getCount(string s) {
  int i,j,k;
  int a = 0, b = 0, n, n2;
  ll res = 0, dp[22][22];
  string go;

  n = s.size(); n2 = n/2;
  rep(i,n){
    if(s[i]=='o') a++;
    if(s[i]=='x') b++;
  }
  if(a%2 || b%2) return 0;
  a/=2; b/=2;

  go = "";
  rep(i,a) go += 'o';
  rep(i,b) go += 'x';
  sort(go.begin(), go.end());

  do{
    rep(i,n2+1) rep(j,n2+1) dp[i][j] = 0;
    dp[0][0] = 1;

    rep(i,n2+1) rep(j,n2+1){
      k = i+j;

      if(i<n2 && go[i]==s[k]) dp[i+1][j] += dp[i][j];
      if(j<n2 && go[j]==s[k]) dp[i][j+1] += dp[i][j];
    }

    res += dp[n2][n2];
  }while(next_permutation(go.begin(), go.end()));

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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