AtCoder ARC #018 : C - 席替え

微妙なひっかけに引っかかった問題。
http://arc018.contest.atcoder.jp/tasks/arc018_3

問題

NxMの2次元グリッド状に座席があり、初期状態で座っている人の成績が与えられる。
ここで、席替えをして(x座標を問わず)各人の後ろにより成績の低い人がいないように席替えをしたい。
もちろん席替え後は同じ席を2人で使うことはできない。

席移動のコストを移動前後の席のマンハッタン距離とし、席替えのコストは全員の移動コストの和としたとき、席替えコストを最小化せよ。

解法

まず、初期状態の成績がと簡単な式であらわされることに注意しよう。

a%p !=0の場合

a%p!=0の場合、pはNxM以上の素数なので、各人の成績x[0]～x[N*M-1]は必ず異なる。
ということは、成績順で先頭M人は1行目、次のM人は2行目…と行は簡単に確定する。
あとは行内の位置だが、これは同じ行に並べるM人をX座標順にソートし、もともと左側に近い人から左側の席を割り当てればよい。

a%p==0の場合

基本的には、全員の成績が同じになるので、コスト0で条件を満たす。
ただし、いやらしいことにx[0]>=pの場合だけはx[0]だけ他より数字が大きいので、x[0]を一番後ろに持っていこう。

int N,M;
pair<int,int> P[1000000];

void solve() {
	int i,j,k,x,y,l;
	
	cin>>N>>M;
	cin>>x>>y>>l;
	y%=l;
	if(y==0) {
		if(x>=l) return _P("%d\n",2*(N-1));
		return _P("0\n");
	}
	FOR(i,N*M) P[i]=make_pair(x,i),x=(x+y)%l;
	sort(P,P+N*M);
	ll f=0;
	FOR(y,N) {
		vector<int> V;
		FOR(x,M) {
			int sy=P[y*M+x].second/M,sx=P[y*M+x].second%M;
			f += abs(sy-y);
			V.push_back(sx);
		}
		sort(V.begin(),V.end());
		FOR(x,M) f+=abs(x-V[x]);
	}
	cout << f << endl;
	
}

まとめ

生成式の条件がいやらしいな。
x[0]＜pにすればよかったのに。