「え、妻が松江?」
テストケースは1番目しか通らず、評価は20点でした。
/* 11 sk nw jx ob oo xj uh rn wn hu nr ========= 2 sk sk 0 nw wn 0 jx xj 2 ob ob 1 oo oo 0 hu uh 0 nr rn ========= 0 nw wn 0 jx xj 0 hu uh 0 nr rn 1 oo oo 2 sk sk 2 ob ob ========= 0 hu uh 0 jx xj 0 nr rn 0 nw wn 1 oo oo 2 ob ob 2 sk sk hujxnrnwoownrnxjuh */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 1000 #define IW 11 struct KEYWORD{ int f; char key[IW]; }keywords[N]; int n; struct NODE{ int f; struct KEYWORD *p; struct KEYWORD *q; }nodes[N]; int noden; void strreverse(char *p, char *q) { char *t = p; long n; while(*t++) ; t--; n = t - p; while(n--){ *q++ = *--t; } *q = '\0'; return; } void pairs(void) { char s[IW]; int i, j; for(i = 0; i < n; i++){ if(keywords[i].f == 0){ strreverse(keywords[i].key, s); for(j = 0; j < n; j++){ if(strcmp(keywords[j].key, s) == 0){ if(strcmp(keywords[i].key, s) <= 0){ nodes[noden].p = &keywords[i]; nodes[noden].q = &keywords[j]; }else{ nodes[noden].p = &keywords[j]; nodes[noden].q = &keywords[i]; } if(i == j){ nodes[noden].f = 1; }else{ nodes[noden].f = 0; } keywords[j].f = 1; break; } } if(n <= j){ nodes[noden].f = 2; nodes[noden].p = nodes[noden].q = &keywords[i]; } keywords[i].f = 1; noden++; } } return; } int cmp(struct NODE *p, struct NODE *q) { return(p->f - q->f); } int cmp1(struct NODE *p, struct NODE *q) { if(p->f < q->f){ return(0); } return(strcmp(p->p->key, q->p->key)); } void sort(int(*f)(struct NODE *p, struct NODE *q)) { int i, j; struct NODE w; for(i = 0; i < noden; i++){ for(j = 0; j < noden - i - 1; j++){ if(0 < f(&nodes[j], &nodes[j+1])){ w = nodes[j]; nodes[j] = nodes[j+1]; nodes[j+1] = w; } } } return; } void tesprint(void) { int i; printf("=========\n"); for(i = 0; i < noden; i++){ printf("%d %s %s\n", nodes[i].f, nodes[i].p->key, nodes[i].q->key); } return; } void pairsprint(int i) { if(noden < i){ return; } if(nodes[i].f < 2){ printf("%s", nodes[i].p->key); pairsprint(i+1); } if(nodes[i].f < 1){ printf("%s", nodes[i].q->key); } return; } int main(int argc, const char * argv[]) { int i; scanf("%d", &n); for(i = 0; i < n; i++){ scanf("%s", keywords[i].key); } pairs(); tesprint(); sort(cmp); tesprint(); sort(cmp1); tesprint(); pairsprint(0); printf("\n"); return 0; }
考え方
①ある単語nのペア’nが存在するか調べる
ペア'nは単語nを逆順に並び替えたもの。
②あるなら①を回文の候補にする
③回文の候補をアルファベット順に並び替える
④回文の候補から回文を作成する
例:
入力単語リストの一部がa,b,cで、そのペアが'a,'b,'cとする。
すると回文の出力形式はabcc'b'a'になる。
ただしペアが同じ場合(qaqなど逆順に並び替えても同じ値)は中央に1つだけ出力する。
という考え方で問題を解いたけど、テストケース1番目しか通らなかったよ。