SRM 589 DIV1 Easy - GooseTattarrattatDiv1

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12730&rd=15701

解き方

回文にするために一致させなければならアルファベットの集合を考えた時、
もっとも出現回数の大きいものだけを残して、他を変換するのが
一番コストをおさえられる。

あとは、上記の集合をしらべるのに無向グラフを利用すればよい。

コード

class GooseTattarrattatDiv1 {

public: int getmin(string S) {
int n=S.size();
int d[26][26],num[26],used[26];

memset(num,0,sizeof(num));
FORE(i,0,n)num[S[i]-'a']++;

memset(d,0,sizeof(d));
for(int i=0;i<n/2;i++){
d[S[i]-'a'][S[n-1-i]-'a']=1;
d[S[n-1-i]-'a'][S[i]-'a']=1;
}
FORE(k,0,26)FORE(i,0,26)FORE(j,0,26)d[i][j]|=(d[i][k] && d[k][j]);

int ret=0;
memset(used,0,sizeof(used));
FORE(i,0,26)if(!used[i]){
used[i]=1;
int sum=num[i],mx=num[i];
FORE(j,0,26)if(i!=j && d[i][j]){
mx=max(mx,num[j]);
sum+=num[j];
used[j]=1;
}
ret+=sum-mx;
}

return ret;
}

};

SRM 625 DIV1 Easy - PalindromePermutations (×)

問題

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;
}

};

SRM 607 DIV1 Easy - PalindromicSubstringsDiv1 xx

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12964&rd=15840

ある文字列が与えられる。
文字列はアルファベットと、？からなり、？には任意の文字を入れることができる。

？に任意の文字が入れられたとき、
その文字列中の回文であるサブ文字列の数の期待値を求める。

解き方

文字列は最大５０００であるため、？の全ての場合に対して期待値を求めては間に合わない。

ここで回文の判定については、その両端の２つの文字列だけを見ればよいことがわかる。
ある文字列が回文であれば、その両端の文字の判定結果をかけていけば回文の判定は時間内に間に合う。

データ構造としてdp[i][j]をi番目からj番目までの文字列、と定義することで
計算量は最大で5000*5000/2になるので時間内に解くことができる。

コード

double dp[5010][5010];
string s;

class PalindromicSubstringsDiv1 {

public:

double calc(int i,int j){
if(s[i]!='?'&&s[j]!='?') return s[i]==s[j] ? 1.0 : 0.0;
return 1.0/26.0;
}


double expectedPalindromes(vector<string> S1, vector<string> S2) {
double ret=0.0;

memset(dp,0,sizeof(dp));

s="";
FORE(i,0,S1.size())s+=S1[i];
FORE(i,0,S2.size())s+=S2[i];
int n=s.size();

FORE(i,0,n){
dp[i][i]=1.0;
ret+=dp[i][i];
}

FORE(i,0,n-1){
dp[i][i+1]=calc(i,i+1);
ret+=dp[i][i+1];
}

FORE(len,3,n+1){
for(int i=0;i+len-1<n;i++){
int j=i+len-1;
dp[i][j]=dp[i+1][j-1]*calc(i,j);
ret+=dp[i][j];
}
}

return ret;
}

};