ACM/ICPC国内予選2問目
問題はこちら。これまた頭の悪い方法で解いてます。全ての編成について1つ1つ調べてます。1つ1つの編成を作成して今までにあった編成全てと比較し、それが今までにないものだったら新たに記憶します。まず最初に初期状態の編成をそのまま記憶します。次にそれを丸々ひっくり返して最初のものと比較し同じでなければ記憶します。あとは無理やりです。編成の各部分で切り離してそのままにしたりひっくり返したりして6パターンを検証します。
#include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; static char record[560][80]; void reverse(char* out, const char* in) { int len = strlen(in); for (int i = 0; i < len; i++) { out[i] = in[len - i - 1]; } out[len] = '\0'; } bool is_conflict(const char* work, int rec_num) { for (int i = 0; i < rec_num; i++) { if (strcmp(work, record[i]) == 0) return true; } return false; } void do_record(int& rec_no, const char* work) { strcpy(record[rec_no++], work); // printf("%d = %s\n", rec_no - 1, record[rec_no - 1]); } int main() { int m; scanf("%d", &m); for (int i = 0; i < m; i++) { memset(record, 0, 560*80); char dataset[80]; scanf("%s", dataset); int length = strlen(dataset); int rec_no = 0; char work[80]; char work_fwd[80]; // first half. char work_bck[80]; // second half.abcdefghijklmnopqrstuvwxyz char work_fwd_inv[80]; // inverse of first half. char work_bck_inv[80]; // inverse of second half. // record original. never conflicts. strcpy(record[rec_no++], dataset); // printf("%d = %s\n", rec_no - 1, record[rec_no - 1]); // record inverse of original. may conflict. reverse(work, dataset); if (!is_conflict(work, rec_no)) do_record(rec_no, work); for (int j = 0; j < length - 1; j++) { // consider input as "abcd" and j as 1. // length is therefore 4. // cut at next of dataset[j]. // split dataset into work_fwd and work_bck. memcpy(work_fwd, dataset, j + 1); memcpy(work_bck, dataset + j + 1, length - j - 1); work_fwd[j + 1] = '\0'; work_bck[length - j - 1] = '\0'; // make reverse of them. reverse(work_fwd_inv, work_fwd); reverse(work_bck_inv, work_bck); // case of "abdc"; strcpy(work, work_fwd); strcat(work, work_bck_inv); if (!is_conflict(work, rec_no)) do_record(rec_no, work); // case of "bacd"; strcpy(work, work_fwd_inv); strcat(work, work_bck); if (!is_conflict(work, rec_no)) do_record(rec_no, work); // case of "badc"; strcpy(work, work_fwd_inv); strcat(work, work_bck_inv); if (!is_conflict(work, rec_no)) do_record(rec_no, work); // case of "cdab"; strcpy(work, work_bck); strcat(work, work_fwd); if (!is_conflict(work, rec_no)) do_record(rec_no, work); // case of "cdba"; strcpy(work, work_bck); strcat(work, work_fwd_inv); if (!is_conflict(work, rec_no)) do_record(rec_no, work); // case of "dcab"; strcpy(work, work_bck_inv); strcat(work, work_fwd); if (!is_conflict(work, rec_no)) do_record(rec_no, work); } printf("%d\n", rec_no); } }