Codeforces ECR #031 : F. Anti-Palindromize

こんな単純な解法でいいのね…。
http://codeforces.com/contest/884/problem/F

問題

N文字(偶数)の文字列Sと各位置に対応するスコアA[i]が与えられる。
Sを並べ替えたTを考える。
SとTで各位置における文字が一致するとき、A[i]のスコアが得られる。

Anti-PalindromeであるTのうちスコアの最大値を求めよ。
Anti-Palindromeとは、T[i]!=T[N-1-i]であることを意味する。

解法

最小コストフローに持ち込んでも解けるが、もっと単純に解くことも可能である。
まずS[i]=S[N-1-i]になってしまっているiを列挙しよう。
この時、少なくともA[i]とA[N-1-i]の少ない方のスコアはあきらめざるを得ない。
また、そのような各文字S[i]の登場回数を覚えておこう。

一致してしまう文字の登場回数について、過半数を占める文字がない場合、それらの並べ替えでAnti-Palindrome状態を構成できるのでそれ以上スコアを失うことはない。
過半数を占める文字cがある場合、それらを並べ替えてもいくつかPalindrome状態の箇所が残ってしまう。
その場合、S[i]!=S[N-1-i]かつS[i]!=cかつS[N-i-1]!=cの場合、A[i]かA[N-i-1]の小さい方のスコアをあきらめ、Palindrome状態の箇所の解消に充当しよう。

int N;
string S;
int B[101];
map<char,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	int ret=0;
	FOR(i,N) cin>>B[i], ret+=B[i];
	int same=0;
	FOR(i,N/2) {
		if(S[i]==S[N-1-i]) {
			ret-=min(B[i],B[N-i-1]);
			M[S[i]]++;
			same++;
		}
	}
	
	if(M.size()) {
		char c=-1;
		FORR(r,M) if(c==-1 || r.second>M[c]) c=r.first;
		int ma=M[c]-(same-M[c]);
		if(ma>0) {
			multiset<int> cand;
			FOR(i,N/2) {
				if(S[i]!=S[N-1-i] && S[i]!=c && S[N-1-i]!=c) {
					cand.insert(min(B[i],B[N-1-i]));
				}
			}
			while(ma) {
				ret-=*cand.begin();
				cand.erase(cand.begin());
				ma--;
			}
		}
	}
	cout<<ret<<endl;
	
}

まとめ

本番「上限的に最小コストフローなんだろうな。でも思いつかないしE行くか…」ということでさっさとあきらめてしまった。