[[ACM/ICPC]]&br;
&br;
&br;
[[2006Bの問題:http://www.acm-japan.org/past-icpc/domestic2006/contest/all_ja.html#section_B]]&br;
&br;
&br;
回答者：[[ほへい]]&br;
&br;
解法：区切り位置を変えて電車を前後に分割し、前後入れ替え・逆向き等を全検索。&br;
これまでに見つかったパターンと比較して、一致しなかったらスタックに追加&br;
最後にスタックの要素を数え上げてファイルに書き込む&br;
&br;
所要時間：80分&br;
&br;
速度：データセット瞬殺&br;
&br;
実行環境：PenM 1.6GHz 512M Win2000&br;
&br;
備考：コンセプトは『文字列の扱いに慣れよう』&br;
なんて無駄なことを…。って意見はなしの方向で。&br;
きれいなコードは他の人に任せたいです。&br;
&br;
#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 initTrain()
void getAnswer(const char *original, int length)
{
Train *temp_train = start_train.next;
while (temp_train != &end_train) {
Train *del_train = temp_train;
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;
free(del_train);
}
start_train.next = &end_train;
end_train.prev = &start_train;
fprintf(fp_out, "%d\n", answer);
}
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;
}
}
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++;
}
}
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);
}
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;
}
}
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
