TopCoder SRM 791 : Div1 Easy NearPalindromesDiv1

MediumがSubmitできず残念。
https://community.topcoder.com/stat?c=problem_statement&pm=16129&rd=18307

問題

文字列がnear-palindromeであるとは、並べ替えると回文にできる文字列であることとする。
今文字列Sが与えられる。
1文字を選び、1つ文字種をrotateできる(aとzも遷移可能)とする。
Sをnear-palindromeにするために必要な最小rotate回数を求めよ。

解法

near-palindromeである条件は、奇数回登場する文字が1個以下であることである。
そこで、Sで奇数回登場する文字を数え上げよう。

奇数回登場する文字をrotateしてペアにして除いていくことを考える。
その場合、文字順に並べて隣接する要素をペアにするのが効率が良い。
ただし、以下2点注意点。

• 文字列長が奇数のとき、奇数回登場する文字が1個残る。そこでその候補を総当たりしよう。
• 基本的に隣接要素をペアにするが、先頭と末尾をペアにするパターンもある。

class NearPalindromesDiv1 {
	public:
	int solve(string S) {
		int num[26]={};
		FORR(c,S) {
			c-='a';
			num[c]^=1;
		}
		vector<int> V;
		int i,x,y;
		FOR(i,26) if(num[i]) V.push_back(i);
		int ret=55555;
		if(V.size()<=1) {
			ret=0;
		}
		else {
			FOR(x,V.size()) {
				int sum=0;
				for(i=0;i+2<=V.size();i+=2) {
					int a=V[(x+i)%V.size()];
					int b=V[(x+i+1)%V.size()];
					sum+=min(abs(a-b),26-abs(a-b));
				}
				ret=min(ret,sum);
			}
		}
		return ret;
	}
}

まとめ

こっちはすんなりだったのに。