yukicoder : No.839 Keep Distance and Nobody Explodes

とくめい先生を知っている程度の古参です。
https://yukicoder.me/problems/no/839

問題

正の偶数Nが与えられる。
N*Nのグリッドに、1～(N*N)の値を1個ずつ入れたい。
その際、差が1である値が入ったセル同士の距離の最小値が最大となるものを構築せよ。

解法

Nが偶数なので、なんか行列を半分にして往復するみたいなことをするんだろうな…と想像がつく。

証明はEditorialに譲るとして、自分は以下のように埋めた。
まず左上と右下を往復するように埋める。

 1  3  5  7 ** ** ** **
 9 11 13 15 ** ** ** **
17 19 21 23 ** ** ** **
25 27 29 31 ** ** ** **
** ** ** **  2  4  6  8
** ** ** ** 10 12 14 16
** ** ** ** 18 20 22 24
** ** ** ** 26 28 30 32

次に右上と左下を往復するように埋める。
折り返し時に距離が小さくならないよう、順番に気を付ける。

** ** ** ** 23 21 19 17
** ** ** ** 31 29 27 25
** ** ** ** 39 37 35 33
** ** ** ** 47 45 43 41
24 22 20 18 ** ** ** **
32 30 28 26 ** ** ** **
40 38 36 34 ** ** ** **
48 46 44 42 ** ** ** **

int N;
int A[303][303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int cur=1;
	FOR(y,N/2) FOR(x,N/2) {
		A[y][x]=cur++;
		A[y+N/2][x+N/2]=cur++;
	}
	FOR(y,N/2) FOR(x,N/2) {
		A[y][N-1-x]=cur++;
		A[y+N/2][N/2-1-x]=cur++;
	}
	
	FOR(y,N) {
		FOR(x,N) cout<<A[y][x]<<" ";
		cout<<endl;
	}
	
}

まとめ

こういうの難易度設定難しそう。