AAAABBBBAAAABBB

２つの文字 A, B を使って作られる長さ 15 の順列のうち次の条件を満たすものは何個あるか.
条件: 「連続する２文字の (順序) 対として AA が 5 回, AB, BA, BB が各 3 回現れる.」
例えば順列 AABBAAAABAABBBB は, AA が 5 回, AB が 3 回, BA が 2回, BB が 4 回現れるので, 上の条件を満たしていない.

１９９１年数オリ予選より


解けなかったので、悔しいから（＆ヒマだから）プログラムで。

解答の方針はA→B、B→Aと変わる所に注目して、
ABとBAが３回出現するから
Aの”カタマリ”をa,Bのカタマリをbとすると、有り得るのは
abababa
または
bababab
の２つの場合。
両方を数え上げればおｋ（９８０通り）

細かい解説は多分どこかにあるんで検索してください。

んで、一般化したときに（上の条件はAとBだけで、４パターン全て出てる。ABCで作った列で、AB,ACが１回ずつある時のみカウントとか）力技以外で解く方法とかあるのかにゃ？

view plainprint?

1. #include <stdio.h>  
2. #include <math.h>  
3.   
4. int N=15;  
5.   
6. int chk(int a[]){  
7.    
8.  int cntAA=0;  
9.  int cntBB=0;  
10.  int cntBA=0;  
11.  int cntAB=0;  
12.    
13.  for(int i=1;i<=N-1;i++){  
14.     
15.   if(a[i]==0 && a[i+1]==0)  
16.    cntAA++;  
17.      
18.   if(a[i]==0 && a[i+1]==1)  
19.    cntAB++;  
20.     
21.   if(a[i]==1 && a[i+1]==0)  
22.    cntBA++;  
23.     
24.   if(a[i]==1 && a[i+1]==1)  
25.    cntBB++;  
26.     
27.  }  
28.   
29.    
30.  if(cntAA==5 && cntAB==3 && cntBA==3 && cntBB==3){  
31.     
32.   return 1;  
33.    
34.  }else{  
35.     
36.   return 0;  
37.     
38.  }  
39.    
40. }  
41.    
42.    
43.   
44. int main(void)  
45. {  
46.   
47.  int a[N+1];  
48.  int count=0;  
49.    
50.  int MAX=pow(2,15)-1;  
51.   
52.  for(int n=0;n<=MAX;n++){  
53.     
54.   //10進数→2進数  
55.   for(int i=1;i<=N;i++)  
56.    a[i]=(n/(int)pow(2,i-1))%2;  
57.     
58.    
59.   if(chk(a))count++;  
60.     
61.  }  
62.   
63.  printf("%d",count);  
64.    
65.  return 0;  
66. }  
67.   
68. </math.h></stdio.h>  

#include 
#include 

int N=15;

int chk(int a[]){
 
 int cntAA=0;
 int cntBB=0;
 int cntBA=0;
 int cntAB=0;
 
 for(int i=1;i<=N-1;i++){
  
  if(a[i]==0 && a[i+1]==0)
   cntAA++;
   
  if(a[i]==0 && a[i+1]==1)
   cntAB++;
  
  if(a[i]==1 && a[i+1]==0)
   cntBA++;
  
  if(a[i]==1 && a[i+1]==1)
   cntBB++;
  
 }

 
 if(cntAA==5 && cntAB==3 && cntBA==3 && cntBB==3){
  
  return 1;
 
 }else{
  
  return 0;
  
 }
 
}
 
 

int main(void)
{

 int a[N+1];
 int count=0;
 
 int MAX=pow(2,15)-1;

 for(int n=0;n<=MAX;n++){
  
  //10進数→2進数
  for(int i=1;i<=N;i++)
   a[i]=(n/(int)pow(2,i-1))%2;
  
 
  if(chk(a))count++;
  
 }

 printf("%d",count);
 
 return 0;
}