読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

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]でスコアが正になるものが2つ以上残っている限り、大きい順に2つをペアにして取り入れよう。

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

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

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;
	
}

まとめ

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

広告を非表示にする