Topcoder SRM 499 div2 hard "PalindromeGame"

問題：http://www.topcoder.com/stat?c=problem_statement&pm=11331（要ログイン）

文字列と数値の組が与えられる．この文字列を組み合わせて回文になるような組の数値の合計値の最大を求める．

すべて同じ長さの文字列なので，それぞれの反転と等しい組が存在する場合，回文の前後に付与することができるのでこれを合計する．そして使わなかった部分のうち，その文字列自身が回文であれば求める回文の中心に据えることができる．

コード

import java.util.*;

public class PalindromeGame {

	public int getMaximum(String[] front, int[] back) {
		int n = front.length;
		A[] a = new A[n];
		for (int i = 0; i < n; ++i) {
			a[i] = new A(front[i], back[i]);
		}
		Arrays.sort(a, new Comparator<A>() {
			public int compare(A o1, A o2) {
				return o2.p - o1.p;
			}
		});
		int r = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				if (!a[i].used && !a[j].used && a[i].s.equals(a[j].r())) {
					r += a[i].p + a[j].p;
					a[i].used = a[j].used = true;
				}
			}
		}
		for(int i = 0; i < n; ++i){
			if(!a[i].used && a[i].s.equals(a[i].r())){
				r += a[i].p;
				break;
			}
		}

		return r;
	}

	class A {
		String s;
		int p;
		boolean used;

		A(String s, int p) {
			this.s = s;
			this.p = p;
			this.used = false;
		}

		String r() {
			return new StringBuilder(s).reverse().toString();
		}
	}

}