Codeforces ECR #145 : D. Binary String Sorting

7問回なのに4問目から正答者の少ない回。
https://codeforces.com/contest/1809/problem/D

問題

01で構成された文字列Sが与えられる。

• 隣接2要素のスワップを、コスト10^12で行う。
• 1文字の削除を、コスト10^12+1で行う。

Sをソートするのにかかるコストの最小値を求めよ。

解法

1つの文字に対し、スワップを2回以上行う意味はなく、それなら削除してしまった方が良い。
そこで、"10"となっている箇所を総当たりし、そこをswapしつつ、"10"の手前にある"1"や後にある"0"を削除することにして、各ケースのコストを求めよう。

int T;
int N;
string S;
int A[303030][2];
void solve() {
	int i,j,k,l,r,x,y; string s;
	const ll C=10000LL*10000LL*10000LL;
	cin>>T;
	while(T--) {
		cin>>S;
		N=S.size();
		FOR(i,N) {
			A[i+1][0]=A[i][0];
			A[i+1][1]=A[i][1];
			A[i+1][S[i]-'0']++;
		}
		ll mi=1LL<<60;
		FOR(i,N+1) {
			ll a=A[i][1];
			ll b=A[N][0]-A[i][0];
			mi=min(mi,(a+b)*(C+1));
			if(i>0&&i<N&&S[i-1]=='1'&&S[i]=='0') {
				mi=min(mi,(a+b-2)*(C+1)+C);
			}
		}
		cout<<mi<<endl;
	}
}

まとめ

なんでこれ妙に本番の正答者少なかったんだろうな。