Codeforces #225 Div1. A. Milking cows

うーむ、CF2連敗。Aだけさっさと解けたけど、Bは実装が間に合わず、C・Dは方針が立たずじまい。
http://codeforces.com/contest/383/problem/A

問題

牛が横１列に並んでおり、それぞれ左か右を向いている。
それぞれの牛から１回ずつ牛乳を搾りたいが、それぞれの牛は自分の見ている向きにいる牛が牛乳を搾られているのを見ると、自分の牛乳の生産量が１落ちる。

ここで、牛乳を搾る牛の順番を最適化し、落ちてしまう牛乳の生産量を最適化せよ。

解法

牛のうち、まずは片方だけを向いている牛たちのことを考える。
例えばみんな牛が左側を向いている場合、右側から絞れば生産量が落ちないことがわかる。

このことから、先に左側を向いている牛を右側から絞ってから、右向きの後ろを左から絞るか、逆に右向きの牛を左から絞った後左を向いている牛を左から絞り、生産量の低下幅の小さい方を選べばよい。

…と本番に考えたが、実はこの上の２通りの手順は同じ結果となる。
左側に右を向いた牛がいて、右側に左を向いた牛がいる場合、どちらを先に選んでももう片方の生産量が１落ちるので、順番は関係ないことがわかる。

int N;
int A[200100];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	ll mi=1LL<<60;
	ll l1=0,r=0;
	FOR(i,N) {
		if(A[i]==0) r+=l1;
		else l1++;
	}
	ll l0=0,r2=0;
	for(i=N-1;i>=0;i--) {
		if(A[i]==1) r2+=l0;
		else l0++;
	}
	
	cout << min(r,r2) << endl;
}

まとめ

まぁこの問題は特に問題なかったね。