2006Bの解答

ACM/ICPC


2006Bの問題


回答者：ほへい

解法：区切り位置を変えて電車を前後に分割し、前後入れ替え・逆向き等を全検索。
　　　　これまでに見つかったパターンと比較して、一致しなかったらスタックに追加
　　　　最後にスタックの要素を数え上げてファイルに書き込む

所要時間：80分

速度：データセット瞬殺

実行環境：PenM 1.6GHz 512M Win2000

備考：コンセプトは『文字列の扱いに慣れよう』
　　　　なんて無駄なことを…。って意見はなしの方向で。
　　　　きれいなコードは他の人に任せたいです。

#include <stdio.h>
#include <stdlib.h>

FILE *fp_in, *fp_out;
const char *f_source = "2006B_in.txt";
const char *f_answer = "2006B_out.txt";

typedef struct __Train {
   struct __Train *prev, *next;
   char boxes[73];
} Train;

Train start_train, end_train;

void initTrain(void);                        // 重複しないパターンを保存するスタックの初期化
void push(Train train);                      // スタックに要素を追加する

/* 文字を結合して、新しいパターンであれば、それを要素に持つ Train をスタックに追加する。 */
void append(const char *before, const char *after);
void reverse(char *string, int length);             // 文字列を逆順にする。
void copy(char *copy_string, const char *source);   // 文字列をコピーする

/* 電車をある部分で前と後ろに分割する。　*/
void setBeforeAfter(const char *original, char *before, char *after, int length, int devide);

int isEqual(const char *string1, const char *string2);  // 二つの文字列が等しいかを返す。
int isNewTrain(Train new_train);                        // 電車が新しいパターンであるかを返す。
void getAnswer(const char *original, int length);       // データセット一つ分の動作を担当する。



int main(void)
{
   int num_data;
   fp_in = fopen(f_source, "r");
   fp_out = fopen(f_answer, "w");
   start_train.next = &end_train;
   end_train.prev = &start_train;
   
   fscanf(fp_in, "%d", &num_data);
   for(; num_data > 0; num_data--) {
       Train original;
       int length = 0;
       fscanf(fp_in, "%s", original.boxes);
       while(1) {
           if(original.boxes[length] != '\0') {
               length++;
           }
           else break;
       }
       getAnswer(original.boxes, length);
       
       initTrain();
   }
   fclose(fp_out);
   fclose(fp_in);
   
   return 0;
}


void getAnswer(const char *original, int length)
{
   int i, answer = 0;
   Train *temp_train;
   for(i = 0; i < length; i++) {
       char before[73] = {0}, after[73] = {0}, rev_after[73] = {0};
       
       setBeforeAfter(original, before, after, length, i);
       
       append(after, before);
       
       copy(rev_after, after);
       reverse(rev_after, length - i);
       
       append(rev_after, before);
       append(before, rev_after);
       
       reverse(before, i);
       
       append(before, after);
       append(after, before);
       append(before, rev_after);
       append(rev_after, before);
   }
   temp_train = start_train.next;
   while(temp_train != &end_train) {
       answer++;
       temp_train = temp_train->next;
   }
   fprintf(fp_out, "%d\n", answer);
}


void append(const char *before, const char *after)
{
   Train create;
   int i = 0, j = 0;
   while(1) {
       if(before[i] != '\0') {
           create.boxes[i] = before[i];
           i++;
       }
       else {
           break;
       }
   }
   
   while(1) {
       if(after[j] != '\0') {
           create.boxes[i] = after[j];
           i++, j++;
       }
       else {
           break;
       }
   }
   create.boxes[i] = '\0';
   if(isNewTrain(create)) {
       push(create);
   }
}


void setBeforeAfter(const char *original, char *before, char *after, int length, int devide)
{
   int i, j;
   for(i = 0; i < devide; i++) {
       before[i] = original[i];
   }
   
   for(j = 0; i < length; i++, j++) {
       after[j] = original[i];
   }
}


void copy(char *copy_string, const char *source)
{
   int i = 0;
   while(1) {
       if(source[i] == '\0') break;
       copy_string[i] = source[i];
       i++;
   }
}

 
int isNewTrain(Train newTrain)
{
   Train *temp_train = start_train.next;
   while(temp_train != &end_train) {
       if(isEqual(temp_train->boxes, newTrain.boxes)) return 0;
       temp_train = temp_train->next;
   }
   return 1;
}


int isEqual(const char *string1, const char *string2)
{
   int i = 0;
   while(1) {
       if(string1[i] == '\0') break;
       if(string1[i] != string2[i]) return 0;
       i++;
   }
   return 1;
}


void initTrain()
{
   Train *temp_train = start_train.next;
   while (temp_train != &end_train) {
       Train *del_train = temp_train;
       temp_train = temp_train->next;
       free(del_train);
   }
   start_train.next = &end_train;
   end_train.prev = &start_train;
}


void push(Train train)
{
   Train *append = (Train*)malloc(sizeof(Train));
   *append = train;
   append->prev = end_train.prev;
   append->next = &end_train;
   end_train.prev = append;
   append->prev->next = append;
}


void reverse(char *string, int length)
{
   int i;
   char temp;
   for (i = 0; i < length / 2; i++) {
       temp = string[i];
       string[i] = string[length - i - 1];
       string[length - i - 1] = temp;
   }
}