yukicoder : No.3334 I hate Image Convolution

なんか最近yukicoderの問題供給が多くて、解く方が追い付いてないな。
https://yukicoder.me/problems/no/3334

問題

整数Nと、(N-1)^2個の整数が与えられる。
N*Nの整数行列Aに対し、2*2の部分列の総和を並べ替えたものが、入力となるようなAを1つ構築せよ。

解法

入力をソートする。
Aを以下のようにおき、"*"の部分について、偶数行目は左から右、奇数行目は右から左に、順に2*2の部分列の総和が入力の小さい順に一致するように定めて行けばよい。

0 0 0 0 0
0 * * * *
* * * * 0
0 * * * *
* * * * 0

int T,N,C[707*707];

int A[707][707];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,(N-1)*(N-1)) cin>>C[i];
		sort(C,C+(N-1)*(N-1));
		
		FOR(x,N) FOR(y,N) A[y][x]=0;
		int cur=0;
		for(y=1;y<N;y++) {
			if(y%2) {
				for(x=1;x<N;x++) {
					A[y][x]=C[cur++]-A[y-1][x-1]-A[y-1][x]-A[y][x-1];
				}
			}
			else {
				for(x=N-2;x>=0;x--) {
					A[y][x]=C[cur++]-A[y-1][x+1]-A[y-1][x]-A[y][x+1];
				}
			}
		}
		FOR(y,N) {
			FOR(x,N) cout<<A[y][x]<<" ";
			cout<<endl;
		}
		
		
	}
}

まとめ

これはすんなり思いつかなかった…。