NOMURA プログラミングコンテスト 2020 : E - Binary Programming

これ方針あってたのに時間切れしたの残念。
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_e

問題

空文字Sから、任意の場所に0,1を追加することを繰り返し、最後Tにする。
その際、1文字追加毎に先頭から奇数文字目の位置に1がある分だけスコアに加算される。
最適な追加順を取るとき、最大スコアはいくつか。

解法

Editorialは文字を減らす方でやっているけど自分は追加していった。
ただし考え方は同じ。

まずは1を全部追加してしまおう。0を先に入れるより、0を後にしたほうが1がたくさんある分スコアを増やしやすい。
次に、最終的に1が2連続するところは、0を追加するたびに常にどちらか1スコアが入るので、その分先に計上し、以後無視する。
よって、1が2連続する箇所を取り除くと、1の間に1個以上の0をどう挿入するかという問題になる。
まず最初にスコアを最大化するため、1の間に1個ずつ0を挿入していこう。

その後、後ろから順に0を挿入していく。
挿入する0の後ろの1は、挿入毎に計上可否が切り替わるが、挿入する0より手前の1は確実にスコア計上できるので、前から挿入するよりトクである。

string T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	
	vector<int> num;
	num.push_back(0);
	int C1=0;
	ll ret=0;
	int cur=0;
	int fix=0;
	FOR(i,T.size()) {
		if(T[i]=='0') {
			if(cur%2) num.push_back(0);
			fix+=cur/2;
			num.back()++;
			cur=0;
		}
		else {
			C1++;
			cur++;
			ret+=(C1+1)/2;
		}
	}
	fix+=cur/2;
	if(cur%2) num.push_back(0);
	
	ret+=1LL*count(ALL(T),'0')*fix;
	
	
	FOR(i,num.size()-1) if(i && num[i]) {
		num[i]--;
		ret+=i+(num.size()-1-i+1)/2;
	}
	fix=num.size()-1;
	int CC[2]={};
	for(i=num.size()-1;i>=0;i--) {
		while(num[i]) {
			swap(CC[0],CC[1]);
			ret+=fix+CC[1];
			num[i]--;
		}
		CC[1]++;
		fix--;
	}
	
	
	cout<<ret<<endl;
	
}

まとめ

本番微妙な計算ミスで落としてたのでもったいない…。