Codeforces #492 Div1 B. Suit and Tie

なんだこりゃ。
http://codeforces.com/contest/995/problem/B

問題

1～Nが２個ずつある2N要素の数列がある。
隣接要素のswapを繰り返し、同じ数字を隣接させるには最小何回swapが必要か。

解法

もし同じ数字の間にx個の異なる数字がある場合、その同じ数字同士を隣接させるのにx回のswapは必須である。
だとすると、あとに悪影響を及ぼさないswap方法が良い。
そこで、数列の手前から貪欲に処理していく。未処理の要素のうち先頭要素を見かけたら、その後ろにある同じ数値を見つける。
そしたらそれを先頭要素に向けて移動すればよい。

この問題は実質転倒数と同じような解き方もできるので、O(NlogN)でも解ける。

int N;
int A[202];

int did[202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2*N) cin>>A[i];
	
	int step=0;
	FOR(i,2*N) if(did[i]==0) {
		did[i]=1;
		for(x=i+1;x<2*N;x++) if(did[x]==0) {
			if(A[i]==A[x]) {
				did[x]=1;
				break;
			}
			step++;
		}
	}
	cout<<step<<endl;
	
}

まとめ

これ750ptでもN=10^5上限でいいと思うんだけど、なんでO(N^2)どころかO(N^3)でも通るサイズなんだ。