SRM 428 DIV1 Easy - TheLuckyString (復習×○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10180&rd=13519
ある文字列が与えられる。
文字列を入れ替えた時、隣り合う文字が同じアルファベットにならない
場合の数を求める。
解き方
Ｎ＝１０なので全探索できそうだが、
計算量をきちんとしないとオーバーフローしてしまう。
全ての順列で10!=3628800=3.6*10^6だが
その中で全ての順列について10回の判定で3.6*10^7がぎりぎり。
それ以上、7.2*10^7がエラー境界な感覚なので
上位の人でもエラーとなっている人が多かったです。
nextpermutation＆判定文ではなく、
再帰関数を使うことでO(10!)に近いオーダーで計算することができます。
コード
class TheLuckyString {
public:
int N;
int total;
string str;
int have[26];
void calc(int pos,char prev){
if(pos==N){
total++;
return;
}
for(int ch='a';ch<='z';ch++){
if(ch!=prev && have[ch-'a']>0){
have[ch-'a']--;
calc(pos+1,ch);
have[ch-'a']++;
}
}
}
int count(string s) {
N=s.size();
total=0;
FORE(i,0,26)have[i]=0;
FORE(i,0,N)have[s[i]-'a']++;
calc(0,' ');
return total;
}
};
public:
int N;
int total;
string str;
int have[26];
void calc(int pos,char prev){
if(pos==N){
total++;
return;
}
for(int ch='a';ch<='z';ch++){
if(ch!=prev && have[ch-'a']>0){
have[ch-'a']--;
calc(pos+1,ch);
have[ch-'a']++;
}
}
}
int count(string s) {
N=s.size();
total=0;
FORE(i,0,26)have[i]=0;
FORE(i,0,N)have[s[i]-'a']++;
calc(0,' ');
return total;
}
};
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 TheLuckyString {
public:
int count(string s) {
int ret=0;
int n=s.size();
sort(all(s));
do{
int valid=1;
FORE(i,0,n-1)if(s[i]==s[i+1])valid=0;
ret+=valid;
}while(next_permutation(all(s)));
return ret;
}
};
#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 TheLuckyString {
public:
int count(string s) {
int ret=0;
int n=s.size();
sort(all(s));
do{
int valid=1;
FORE(i,0,n-1)if(s[i]==s[i+1])valid=0;
ret+=valid;
}while(next_permutation(all(s)));
return ret;
}
};
