POJ-1854 : Evil Straw Warts Live
解法
奇数回現れる文字が2個以上あれば不可。それ以外のときは、以下のような手順で最小コストの回文が得られる(未証明)。
- 最小のスワップ回数で、前半と後半で出現する文字の頻度が一致するように移動する。
- 後半の文字列のみを最小回数で動かして回文になるようにする。
前半部分はやるだけ。後半は、分割統治で解ける。すなわち、文字列を前半と後半に分けて出現回数が一致するようにスワップを繰り返せばよい。
acceptされたコード
const int MAX_N = 8000; int L; char input[MAX_N + 1], target[MAX_N + 1], buf[MAX_N + 1]; void init() { scanf(" %s ", input); L = strlen(input); } //[from, to) int rec(const int from, const int to) { const int len = to - from; if (len <= 1) { return 0; } const int mid = (from + to) / 2; int ret = 0; static char tmp[MAX_N]; int freq[0x100] = {}; for (int i = from; i < mid; ++i) { freq[int(target[i])]++; } for (int i = from, p = from; i < to && p < mid; ++i) { const int c = buf[i]; if (freq[c]) { --freq[c]; ret += i - p; tmp[p++] = c; buf[i] = '*'; } } for (int i = from, p = mid; i < to; ++i) { if (buf[i] != '*') { tmp[p++] = buf[i]; } } for (int i = from; i < to; ++i) { buf[i] = tmp[i]; } return ret + rec(from, mid) + rec(mid, to); } void solve() { int ans = 0; int freq[0x100] = {}, cur[0x100] = {}; for (int i = 0; i < L; ++i) { freq[int(input[i])]++; } int oddCount = 0; for (int i = 0; i < 0x100; ++i) { oddCount += freq[i]&1; } if (oddCount > 1) { puts("Impossible"); return ; } for (int i = 0, p = 0; i < L; ++i) { int c = input[i]; if (cur[c] < freq[c]/2) { ++cur[c]; ans += i - p; target[p++] = c; input[i] = '*'; } } target[L/2] = '\0'; if (L&1) { int nonStar = 0; for (int i = 0; i < L; ++i) { if (freq[int(input[i])]&1) { ans += nonStar; input[i] = '*'; break; } else if (input[i] != '*') { ++nonStar; } } } for (int i = 0, p = 0; i < L; ++i) { if (input[i] != '*') { buf[p++] = input[i]; } } buf[L/2] = '\0'; reverse(target, target + L / 2); ans += rec(0, L / 2); printf("%d\n", ans); }