POJ-1854 : Evil Straw Warts Live

問題概要

長さL(<8000)の文字列が与えられる。隣り合う2文字をスワップして回文になるようにしたい。必要なスワップの最小回数を求める問題。回文にできないのであれば指摘する。

解法

奇数回現れる文字が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);
}