TopCoder SRM 792 : Div1 Medium IncreasingJumpsDiv1

これは賢いな…。
https://community.topcoder.com/stat?c=problem_statement&pm=16539&rd=18340

問題

1次元座標上で、N個の点が与えられる。初期状態で、0～2500の範囲のいずれかの整数座標に点がある。
これらを動かし、(並び順は問わないので)N個が連続した格子点に配置されるようにしたい。

動かす際、i手目では1つ点を選んで+iか-iだけ動かすことができる（必ず1点動かさないといけない）。
2500手以内で条件を満たす移動方法を答えよ。

解法

Editorialの解法がわかりやすかったのでそれを紹介。
全点を1275周辺に並べることにする。並べ先は任意。
それに先立ち、全点を[1000,1500]の範囲に収まるように貪欲に寄せていこう。
全点がこの範囲に入るまで、500手以下で済むので、貪欲に寄せれば必ず条件を満たせる。

以降、各点を狙った並べ先に向け微調整する。
その際、連続する2k手を使うとk*kだけ移動できることを利用しよう。
例えばk回左に移動したのちk回右に移動すると、全体でk*k右に移動した状態になる。
これを用いて微調整を行うと、全体で2500手以下で済む。

class IncreasingJumpsDiv1 {
	public:
	
	int ok(vector <int> frogs,vector <int> ret) {
		int i;
		for(i=0;i<ret.size();i++) {
			if(ret[i]>0) frogs[ret[i]-1]+=i+1;
			else if(ret[i]<0) frogs[-ret[i]-1]-=i+1;
			else return 0;
		}
		sort(ALL(frogs));
		FOR(i,frogs.size()-1) if(frogs[i]+1!=frogs[i+1]) return 0;
		return 1;
	}
	
	vector <int> jump(vector <int> frogs) {
		int N=frogs.size();
		int x,i;
		
		
		vector<int> R,D=frogs;
		for(x=1;x<=2500;x++) {
			FOR(i,N) {
				if(D[i]>1500) {
					R.push_back(-(i+1));
					D[i]-=x;
					break;
				}
				if(D[i]<1000) {
					R.push_back((i+1));
					D[i]+=x;
					break;
				}
			}
			if(i==N) break;
		}
		FOR(i,N) {
			int tar=1250-(N/2)+i;
			while(D[i]<tar) {
				int d=sqrt(abs(tar-D[i]));
				D[i]+=d*d;
				FOR(x,d) R.push_back(-(i+1));
				FOR(x,d) R.push_back((i+1));
			}
			while(D[i]>tar) {
				int d=sqrt(abs(tar-D[i]));
				D[i]-=d*d;
				FOR(x,d) R.push_back((i+1));
				FOR(x,d) R.push_back(-(i+1));
			}
		}
		cerr<<R.size()<<endl;
		assert(ok(frogs,R));
		return R;
		
	}
}

まとめ

無駄に重いDPも発生しないし、これは賢いな。