TopCoder SRM 612 Div1 Hard LeftAndRightHandedDiv1

Hardとはいえ900ptだと自力で解けることもある。
http://community.topcoder.com/stat?c=problem_statement&pm=13037

問題

N人の人が円形のテーブルに座っており、各人の利き腕が与えられる。
右利きの人の右に左利きの人がいると、互いのひじが当たり具合が悪い。

コスト１で隣り合う2人の位置を入れ替えることができるとき、具合の悪い組み合わせを最小化するのにかかる最小コストを答えよ。

解法

全員の利き腕が同じなら、ひじはぶつからないのでコストは0。
以後は左利きと右利きが最低1人以上いる場合を前提とする。

具合の悪さを最小化するには、左利き同士と右利き同士が互いに固まって座ればよい。
そうすると具合の悪い組み合わせは1か所だけになる。

よって問題は以下のように書き換えることができる。
「隣り合う人をコスト１で入れ替えられるとき、左利き同士および右利き同士を1か所に固まるコストを最小化せよ」

以下のように考えると、それぞれの位置はN通りあるので固め方はN^2通り考えることができる。

• テーブルのある位置を1か所決め、そこを中心に右利きが集まるようにする。
• ある境目を1か所定め、それより右側の右利きは左回りで、左側の右利きは右回りで上記中心に集まる。

ただ、N<=10^6なのでN^2通りを列挙することはできない。
しかし、後者については、先に中心を定めてしまうと境目に対して必要なコストは下に凸な関数となるため、3分探索を行うことでO(logN)で求めることができる。

先に部分和計算をしておくと、中心と境目の位置にたいしコストはO(1)で求められるので、全体でO(N logN)で最小コストを求めることができる。

int T[2000006];
int NL[2000006],NR[2000006];
ll SL[2000006],SR[2000006];

class LeftAndRightHandedDiv1 {
	public:
	int N;
	ll calc(int cur,int sp) {
		int nlR=sp-(NL[cur+sp]-NL[cur]);
		int nrR=(N-sp)-(NR[cur+N+1-(N-sp)]-NR[cur+N+1]);
		ll lv=SL[cur+sp]-SL[cur]-NL[cur]*(ll)nlR;
		ll rv=SR[cur+N+1-(N-sp)]-SR[cur+N+1]-NR[cur+N+1]*(ll)nrR;
		return lv+rv;
	}
	
	long long countSwaps(string Y, int A, int B, int C, int D, int N) {
		int i,j;
		this->N=N;
		ll mi=1LL<<50;
		FOR(i,N) {
			T[i]=T[i+N]=Y[A%Y.size()]=='L';
			A=(A*(ll)B+C)%D;
		}
		T[2*N]=T[0];
		T[2*N+1]=T[1];
		if(count(T,T+N,0)==0) return 0;
		if(count(T,T+N,1)==0) return 0;
		
		FOR(i,2*N+2) {
			NL[i]=(i?NL[i-1]:0);
			SL[i]=(i?SL[i-1]:0);
			if(T[i]) NL[i]++;
			else SL[i]+=NL[i];
		}
		for(i=2*N+1;i>=0;i--) {
			NR[i]=NR[i+1];
			SR[i]=SR[i+1];
			if(T[i]) NR[i]++;
			else SR[i]+=NR[i];
		}
		
		FOR(i,N) {
			int le=0,ri=N;
			mi=min(mi,min(calc(i,le),calc(i,ri)));
			FOR(j,35) {
				int po1=(le*2+ri)/3;
				int po2=(le+ri*2)/3;
				ll hoge1=calc(i,po1);
				ll hoge2=calc(i,po2);
				mi=min(mi,min(hoge1,hoge2));
				if(hoge1<hoge2) ri=po2;
				else le=po1;
			}
			mi=min(mi,min(calc(i,le),calc(i,ri)));
		}
		return mi;
	}
};

まとめ

本番はO(N^2)にはたどり着いたけど、そこから３分探索に至れなかった。
平方分割も試したけど微妙に時間切れ。

今回の円形テーブルのように周回する配列に対し2倍の長さの配列を準備するテク、Codeforcesとかでも見かけるね。