AtCoder AGC #003 : C - BBuBBBlesort!

AGCになって難易度増したなぁ。
http://agc003.contest.atcoder.jp/tasks/agc003_c

問題

互いに異なる要素からなるN要素の数列Aがある。
この数列Aを以下の２種類の処理を繰り返して昇順にソートしたい。

• 連続するある２要素の並びを反転する
• 連続するある３要素の並びを反転する

前者の処理回数の最小値を求めよ。

解法

後者の処理について、反転というと分かりにくいが結局２つ離れたものを入れ替える事である。
とすると、各要素偶数個分要素を移動するのはノーコストででき、奇数個分移動するのはコストが１かかると考えられる。

各要素について、今の位置が偶数番目で移動先が奇数番目であるもの、およびその逆なものの数を考えよう。
これらの数は一致しており、それぞれをペアにして反転させればよい。
よって前者の「今の位置が偶数番目で移動先が奇数番目であるもの」の数を答えればよい。

以下のコードは前者後者両方数えて２で割っている。

int N;
int A[101010],B[101010];
vector<int> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		B[i]=A[i];
	}
	sort(B,B+N);
	int NG=0;
	FOR(i,N) {
		A[i]=lower_bound(B,B+N,A[i])-B;
		NG+=(A[i]-i+1000000)%2;
	}
	cout<<NG/2<<endl;
	
	
}

まとめ

これはすぐ思いつけた。