kmjp's blog

競技プログラミング参加記です

NJPC 2017 : D - NMパズル

これはすんなり。
http://njpc2017.contest.atcoder.jp/tasks/njpc2017_d

問題

整数N,M,Kが与えられる。
N*Mのグリッドの各セルに1~NMを1つずつ格納し、グリッドの各行における転倒数の総和と各列における転送数の総和がKとなるものを作れ。

解法

各行に1~M、(M+1)~(2M)、…と上の行からM個ずつ値が格納されているとする。
行単位で値を入れ替えると転倒数をM増減させることができるので、転倒数の総和がKを超えない範囲で行単位の入れ替えを行う。

あとは各行内において要素の入れ替えを行おう。
行内で要素を入れ替えても、列内の転倒数は増減しない。

int H,W,K;
vector<int> A[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	
	FOR(y,H) {
		FOR(x,W) A[y].push_back(y*W+x+1);
		int cur=y;
		while(cur && K>=W) {
			swap(A[cur],A[cur-1]);
			cur--;
			K-=W;
		}
	}
	
	FOR(y,H) {
		vector<int> R;
		FORR(r,A[y]) {
			R.push_back(r);
			int cur=R.size()-1;
			while(K && cur) {
				swap(R[cur],R[cur-1]);
				cur--;
				K--;
			}
		}
		A[y]=R;
	}
	
	FOR(y,H) FOR(x,W) _P("%d%c", A[y][x],(x==(W-1))?'\n':' ');
}

まとめ

Cで苦しんだあとだったのですんなり解けてよかった。