SRM 575 DIV2 250

与えられた整数の数列について、任意の２要素を入れ替えた時にできるユニークな数列は、何通り考えられるか。
入れ替えた後にできる数列は、元の数列と同じになる場合もある。

要素を入れ替えてできる数列が、元の数列と同じになる場合もカウントしますが、「元の数列と同じ数列」は1回のみカウントする。とやればよさそうです。

「元の数列と同じ数列」とは、「入れ替える2要素が同じ数である場合にできる数列」と言えるので、

１．入れ替える2要素が同じ数である場合…
　１−１．「同じ数を入れ替えたよフラグ」がOFFの場合、同フラグをONにして、２へ。
　１−２．同フラグがONの場合、３へ。
２．カウントアップする。
３．次の要素へ。

という方針でやります。

  1 #include <stdio.h>
  2 
  3 #define NUMOF(array)    (sizeof(array)/sizeof(*array))
  4 
  5 int TheSwapsDivTwo_find(const int *p_sequence, const size_t sequence_numof)
  6 {
  7     int i;
  8     int j;
  9     int swap_count = 0;
 10     unsigned char is_same_to_original_sequence = 0;
 11 
 12     for(i=0; i<sequence_numof; i++){
 13         for(j=i+1; j<sequence_numof; j++){
 14             if(p_sequence[i] == p_sequence[j]){
 15                 if(is_same_to_original_sequence){
 16                     continue;
 17                 }else{
 18                     is_same_to_original_sequence = 1;
 19                 }
 20             }
 21             swap_count++;
 22         }
 23     }
 24 
 25     return swap_count;
 26 }
 27 
 28 int main(void)
 29 {
 30 //  const int sequence[] = {4, 7, 4};
 31 //  const int sequence[] = {1, 47};
 32 //  const int sequence[] = {9, 9, 9, 9};
 33     const int sequence[] = {22, 16, 36, 35, 14, 9, 33, 6, 28, 12, \
 34                       18, 14, 47, 46, 29, 22, 14, 17, 4, 15, \
 35                       28, 6, 39, 24, 47, 37};
 36 
 37     printf("Returns: %d\n", TheSwapsDivTwo_find(sequence, NUMOF(sequence)));
 38 
 39     return 0;
 40 }