kmjp's blog

競技プログラミング参加記です

Google Code Jam 2014 Round 2 : B. Up and Down

これは本番すんなり思いつけた。
https://code.google.com/codejam/contest/3014486/dashboard#s=p1

問題

distinctな数値で構成されたN要素の数列A[i]が与えられる。
これらの数列の隣接要素のswapを繰り返し、A[0] < A[1] < A[2] < .. < A[m] > A[m-1] > ... > A[N-1]となるようにしたい。
最小で何回swapを行えばよいか。

解法

A[i]を小さい順に見て、Aの先頭または末尾の近い方に移動させれば良い。
以下のコードは先頭または末尾に移動した要素をその都度削除しており、O(N^2)で処理している。

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	int N;
	vector<int> V;
	
	cin>>N;
	FOR(i,N) cin>>x, V.push_back(x);
	
	int ret=0;
	FOR(i,N) {
		x=0;
		FOR(j,V.size()) if(V[j]<V[x]) x=j;
		ret+=min(x,(int)V.size()-1-x);
		V.erase(V.begin()+x);
	}
	
	_P("Case #%d: %d\n",_loop,ret);
}

解法

最大値をどこに置こうと考えると大変だけど、小さいものを一回外に出してしまえば後は考慮しなくてよい、と考えるとラク。