CODE FESTIVAL 2015 あさプロ Hard : A - 一次元オセロ

想定解とは違うかも？
http://code-festival-2015-morning-hard.contest.atcoder.jp/tasks/cf_2015_morning_hard_a

問題

一次元のオセロを考える。
初期状態で、白黒の石が同じ色が交互にA[0],A[1],A[2],...,A[N-1]個ずつ並んでいる。
Nは奇数であり、両端は白石である。

この状態で、オセロのルールに則り黒石・白石を交互に置いていき、最終的には全て白石になるまで続ける。

その過程で、石をひっくり返す回数の最小値を求めよ。

解法

どこか1か所1回もひっくり返らない白石群を仮定する。
その両隣の黒石群は1回ずつ、その両隣の白石群は2回ずつ、またその両隣の黒石群は3回ずつ…とひっくり返る。
事前に累積和を取っておくと、ひっくり返す総数はO(1)で計算できる。

あとはひっくり返らない白石群の位置を総当たりすればよい。

黒石を置く際、両側連続する白石の少ない方を貪欲に取ってく戦略でもいいらしい？（未確認）

int N;
ll A[101010],S[101010],SM[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
		SM[i+1]=SM[i]+i*A[i];
		
	}
	ll mi=1LL<<60;
	for(i=0;i<N;i+=2) {
		ll lad=i;
		ll rad=(N-1-i);
		lad=lad*(lad-1)/2;
		rad=rad*(rad-1)/2;
		
		ll ltot=i*S[i]-SM[i];
		ll rtot=SM[N]-SM[i+1]-i*(S[N]-S[i+1]);
		
		mi=min(mi,lad+rad+ltot+rtot);
	}
	
	cout<<mi<<endl;
}

まとめ

どうやっても黒石が負ける絶望的なオセロ、誰が遊ぶんですかね？