TopCoder SRM 795 : Div1 Medium NRooksPosition

いや途中で嫌な予感したんだよね。
https://community.topcoder.com/stat?c=problem_statement&pm=16705&rd=18429

問題

無限に広いグリッド上にN個の駒がある。
これらの駒を、以下の条件を満たすように動かしたい。

• グリッド上のどこかN*Nの領域に収まる。
• 同じ列・同じ行に2個以上の駒がない

駒のマンハッタン距離における移動量の総和の最小値を求めよ。

解法

駒の列と行をそれぞれ個別に対応し、和を取ろう。以下列のケースを考える。
元々左寄りにある駒は、最終的に左寄りにある方が総移動量が減りそうである。
そこで、列番号を昇順にソートしよう。

各駒は1ずつずれた列に配置されることになるので、各列番号を、添え字の番号分引いておく。
そうするとあとは、この配列の全要素が一致するよう値の増減を行う問題となる。
この問題は典型であり、中央値に合わせればよい。

class NRooksPosition {
	public:
	long long minSteps(int N, vector <int> X, vector <int> Y, int A, int B, int C) {
		int L=X.size();
		int i;
		for(i=L;i<N;i++) {
			X.push_back((1LL*A*X[i-1]+1LL*B*X[i-2])%C);
			Y.push_back((1LL*A*Y[i-1]+1LL*B*Y[i-2])%C);
		}
		sort(ALL(X));
		sort(ALL(Y));
		FOR(i,N) X[i]-=i,Y[i]-=i;
		sort(ALL(X));
		sort(ALL(Y));
		int XM=X[N/2];
		int YM=Y[N/2];
		ll ret=0;
		FOR(i,N) {
			ret+=abs(X[i]-XM)+abs(Y[i]-YM);
		}
		return ret;
	}
}

まとめ

添え字番号分引くのをサボった…。