http://poj.org/problem?id=1854
蟻本には分割統治法と書いてあるがBITでやってしまった。
同じ文字だったら一番右にあるのと一番左にあるのを回文のペアにするのが良くて、二番目三番目…についても同様である。
違う文字だったら、対称性よりどっちを先に端に持っていってもコストは変わらない。
なので一番左から順番に見ていき、見ている文字とそれとペアを組んでいる文字を文字列から抜いた時の各文字のindexを求める。
これはBITを{0,1,2,3...}と初期化して、range_sumで更新すればできる。
int N, Q; vector<int> A[26]; int B[MAX_N]; char str[MAX_N]; BIT bit; int main() { scanf("%d", &Q); while(Q--) { scanf("%s", str); N = strlen(str); rep(i, 0, 26) A[i].clear(); rep(i, 0, N) { A[str[i] - 'a'].push_back(i); } int odd = 0; rep(i, 0, 26) { if((int)A[i].size() % 2 == 1) odd++; } if(odd >= 2) { printf("Impossible\n"); continue; } rep(i, 0, 26) { int n = (int)A[i].size(); rep(j, 0, (n + 1) / 2) { B[A[i][j]] = A[i][n - j - 1]; } } int res = 0; bit.init(N); rep(i, 0, N) bit.range_add(i + 1, i + 1, i); int n = N; rep(i, 0, N) { if(bit.range_sum(i + 1, i + 1) == 0) { int j = B[i] + 1; res += n - bit.range_sum(j, j) - 1; if(i + 1 != j) { bit.range_add(1, j - 1, -1); bit.range_add(j, N, -2); } else { bit.range_add(j, N, -1); } bit.range_add(i + 1, i + 1, inf); bit.range_add(j, j, inf); n -= 2; } } printf("%d\n", res); } return 0; }
実装のアイディアがなかなか思いつかなかった。
見ていく順番を単純化することが重要。