2010-11-12

第 9 回 JOI 予選 4 問題

問題4 を読んでから、正直何度も試行錯誤しました。

カードの組合せ(順列といったほうが正しいのかな)の枚数が固定されていないため、for文を入れ子にする方法はダメ。再帰を使えば解ける気もしたけどそんな技量はない。

ボーッとTwitterを見ていたら、思いがけぬヒントが。「2 進数ビット列をインクリメント…」。そうか、0 で初期化したカードの枚数分のビット列をインクリメントしていき、 1 のビットが 3 つ立ったときにそのビット目を取り出せばいいのか、と。

でも実際にコーディングしてみると、これでは順番を指定しない「組合せ」になってしまいます。順番が決まった「順列」ではありません。

…やっぱり再帰を使うしかない。

ということで、ソースをなんとか完成させました。

#include <stdio.h>
#include <string.h>

int *pstcard;

int seisu(int a, int b){
  /*数値aと数値bを結合させる関数*/
  int result = a;
  if(b < 10){
    result *= 10;
  }else{
    result *= 100;
  }
  result += b;
  return result;
}

int kaijo(int n){
  /*階乗用関数。普通にfor文でやればよかった*/
  if(n != 1) return n * kaijo(n-1);
}

int junre(int *cards, int *temp, int n, int r, int time){
  /*再帰が最深点まで着いたとき*/
  if(time == 0){
    int result = cards[temp[0]];
//    printf("[%d]", temp[0]); //**
    for(int i = 1; i < r; i++){
//      printf("[%d]", temp[i]); //**
      result = seisu(result, cards[temp[i]]);
    }
    *pstcard++ = result;
//    printf("結果:%d\n", result); //**
    return 0;
  }
  /*再帰*/
  int find = 0;
  for(int i = 0; i < n; i++){
    find = 0;
    for(int j = 0; j < (r-time); j++) if(temp[j] == i) find++;
    if(find == 0){
      temp[r-time] = i;
      junre(cards, temp, n, r, time-1);
    }
  }
  return 0;
}

int main(){
  /*入力は読み込んどく。*/
  int n, r;
  scanf("%d", &n);
  scanf("%d", &r);
  int cards[n], stcardlen = kaijo(n) / kaijo(n-r);
  for(int i = 0; i < n; i++){
    scanf("%d", &cards[i]);
  }
  
  /*すべての順列を一応stcard配列にいれる。*/
  int stcard[stcardlen], temp[r];
  memset(stcard, 0, sizeof(stcard));
  pstcard = stcard;
  junre(cards, temp, n, r, r);
  
  /*stcard配列をソートする*/
  int tempv;
  for(int i = 0; i < stcardlen; i++){
    for(int j = 0; j < stcardlen -1; j++){
      if(stcard[j] < stcard[j+1]){
        tempv = stcard[j];
        stcard[j] = stcard[j+1];
        stcard[j+1] = tempv;
      }
    }
  }
  
  /*重複しないものを数える*/
  tempv = 0;
  int result = 0;
  for(int i = 0; i < stcardlen; i++){
    if(tempv != stcard[i]){
      tempv = stcard[i];
      result++;
    }
  }
  printf("\n%d\n", result);
  return 0;
}

はい、見ての通りソートはサボりました。はい。無駄が多いですね。

しかし採点用データもなんとか通り、一見落着です。本番ではこんなに時間かけてやることはできないですが、実は自分で考えて再帰プログラムを書くのはこれが初めてだったりします。 (ハノイの塔でビビッちゃってヨォ(笑))

それにしても… これまでのプログラムは採点用データを入れて一瞬もしないうちに答えが表示されていたのに、今回は少し時間がかかったのには感動してしまいました。

…ん？ふと思ったのですが、選ぶ枚数が２〜４枚なら再帰を使うよりも、 for文を２つ重ねたもの、３つ重ねたもの、４つ重ねたもの、の３種類を用意したほうが早くて手軽かも…。