Codeforces #389 Div2 D. Santa Claus and a Palindrome

Bでしょうもないミスしたり、Eで想定誤解法に引っかかったりして散々。
http://codeforces.com/contest/752/problem/D

問題

K個のN文字の文字列S[i]と、それぞれ対応するスコアA[i]が与えられる。
これらの文字列をいくつか選んで連結したとき、回文となるようなもののうちスコアが最大のものを求めよ。

解法

あるS[i]に対して、ほかにS[i]を反転させた文字列がS[i]にあり、かつ和が正になるなら両者を取り入れるのが良い。
元々S[i]が回文の場合、同じS[i]でスコアが正になるものが２つ以上残っている限り、大きい順に２つをペアにして取り入れよう。

基本的に回文を作る場合はS[i]と、S[i]を反転させたものをセットに取り込むが、中心だけはもともとS[i]が回文の場合1個だけそれを置くことができる。
S[i]がもともと回文になっているものがいくつか余っているものとする。

あまりのうち最大スコアが0のものは無視してよいので、最大スコアは正とする。
２個以上余っているとき、スコアが大きい順に（２個とも正であることはないので）２つ目が負でも１つ目と２つ目を足したら正になる可能性がある。
そのようなものはできるだけ回文に取り入れたいが、１つの文字列だけは２つ目は不要で１つだけ選ぶことができる。
そこはDPで「１つだけ選ぶ処理をした・しない場合」それぞれスコアの総和の最大値を求めていけばよい。

int K,N;
map<string,vector<int>> M;
vector<pair<int,int>> L;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>N;
	FOR(i,K) {
		cin>>s>>x;
		M[s].push_back(x);
	}
	FORR(m,M) sort(ALL(m.second));
	
	ll ret=0;
	
	while(M.size()) {
		auto m=*M.begin();
		M.erase(M.begin());
		
		string a=m.first, b=a;
		reverse(ALL(b));
		
		if(a==b) {
			while(m.second.size()>=2 && m.second.back()>=0 && m.second[m.second.size()-2]>=0) {
				ret += m.second.back() + m.second[m.second.size()-2];
				m.second.pop_back();
				m.second.pop_back();
			}
			if(m.second.size() && m.second.back()>0) {
				int f=m.second.back();
				int s=max(0,f+((m.second.size()>=2)?m.second[m.second.size()-2]:-1<<30));
				L.push_back({f,s});
			}
		}
		else if(M.count(b)) {
			auto m2=M[b];
			M.erase(b);
			while(m.second.size() && m2.size() && m.second.back()+m2.back()>=0) {
				ret += m.second.back() + m2.back();
				m.second.pop_back();
				m2.pop_back();
			}
		}
	}
	
	ll a[2]={};
	FORR(r,L) {
		ll b[2]={0,0};
		// take single
		b[1]=max(b[1],a[0]+r.first);
		b[1]=max(b[1],a[1]+r.second);
		b[0]=max(b[0],a[0]+r.second);
		
		a[0]=b[0];
		a[1]=b[1];
	}
	
	cout<<ret+max(a[0],a[1])<<endl;
	
}

まとめ

スコアの割に、何気に正答者少な目？