TopCoder SRM 618 Div1 Hard MovingRooksDiv1

Div1はDiv2の正当な高難易度化版。
http://community.topcoder.com/stat?c=problem_statement&pm=13065

問題

Div2同様、チェスとかルークがどうこう書いてあるが、まとめるとこうなる。
0～(N-1)のpermutationの形を成す数列Aを成す。
ここで、数列の２要素について、後ろにある要素の方が小さい場合、両者をスワップ可能である。

初期状態と終了状態の数列が与えられたとき、上記スワップ処理を適切に繰り返して初期状態から終了状態の数列に遷移可能か答えよ。
また、遷移可能ならスワップする要素の順番を列挙せよ。

解法

自力でうまく解けなかったので他の人の解法を参考に解いた。

Div2との違いは、具体的なスワップ順を答えることと、N<=2500と制限が大きいことである。

まず最適手を考える。Div2 Hardにあった以下の例を考える。

3 1 2 0
  ↓
0 2 1 3

0と3をスワップすると1と2をスワップできず、それ以上動かせなくなる。
大きな数字が左にあると、その分交換対象の小さな数字が右に多数あるので自由度が増える。
よって大きな数字をいきなり右に動かす手は悪手である。

例えば以下のように大きな数字が徐々に動いていくようにすればよい。

3 1 2 0
1 3 2 0
0 3 2 1
0 2 3 1
0 2 1 3

もっとアルゴリズムで書くと以下のようになる。

• 各要素iを0～(N-1)の順で処理
  • j=(i+1)～(N-1)について、A[i] < A[j]かつA[j]が終了状態より大きいならスワップする

この処理だと大きな数字はちょっとずつ右に移動していく。

class MovingRooksDiv1 {
	public:
	vector <int> move(vector <int> Y1, vector <int> Y2) {
		vector<int> V;
		int N=Y1.size();
		int i,j,x;
		
		FOR(i,N) for(j=i+1;j<N;j++) {
			if(Y1[i]>Y2[i] && Y1[i]>Y1[j] && Y2[i]<=Y1[j]) {
				if(V.size()<2500) V.push_back(i),V.push_back(j);
				swap(Y1[i],Y1[j]);
			}
		}
		
		if(!equal(Y1.begin(),Y1.end(),Y2.begin())) {
			V.clear();
			V.push_back(-1);
		}
		return V;
	}
};

まとめ

このスワップ手順はさらっとは思いつかないなぁ…。