SRM 625 DIV1 Easy - PalindromePermutations (×)

SRM 625 DIV1 Easy - PalindromePermutations (×)

10:01

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11856&rd=15858

・ある文字列が与えられる。
・この文字をシャッフルした時に、回文となる確率を求める。

解き方


・まず与えられた文字列が回文となるかどうか判定する必要がある。
・すべてのアルファベットについて出現回数を調べる。
・このとき、すべてのアルファベットの出現回数が偶数回なら回文となる。
　また、奇数回出現するアルファベットが１つだけなら回文となる。
　それ以外は回文とならない。
・次に、回文となるときの確率を求める。

→System Failed

・まず奇数回出現するアルファベットがある場合、その中央にそのアルファベットを
　置く必要がある。その確率はその出現回数／文字列長。
　そこから出現回数と文字列長をデクリメントする。

・あとはすべてのアルファベットが偶数回の出現回数となる。
　あるアルファベット２つ置く時、それが回文となるのはひとつアルファベットを置いたときに
　一意に定まる。
　よって、ひとつアルファベットを置かれたとき、そのあと残りのアルファベットを指定の場所に置く　
　ので(出現回数-1)/(L-1)となる。
  （例）
　L(文字列長)=4 ,アルファベットaのcnt(出現回数)=2のとき
　すべての並び：aaxx, axax, axxa, xaax, xaxa, xxaa
　うち回文のもの：axxa, xaax
  つまり(cnt-1)/(L-1)となる。

・反省：確率の計算の基本が・・・。

コード


using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class PalindromePermutations {

public:

double P(int x){
double ret=1.0;
FORE(i,1,x+1)ret*=i;
return ret;
}

double palindromeProbability(string word) {
int n=word.size();
int a[26]={};

FORE(i,0,n)a[word[i]-'a']++;

int flag=0;
FORE(i,0,26)if(a[i]%2)flag++;
if(flag>1)return 0;

int L=n;
double ret=1.0;
if(flag){
FORE(i,0,26)if(a[i]%2){
ret=(double)a[i]/L;
L--;
a[i]--;
}
}

FORE(i,0,26)while(a[i]){
ret*=(double)(a[i]-1)/(L-1);
L-=2;
a[i]-=2;
}

return ret;
}

};

Share this

Google Facebook Twitter More

Related Posts