たまたま作れた！！！　個人的傑作の自作構築問題。

問題概要

正の整数 $N$ が与えられる。

$N \times N$ のマス目に 1 以上 $2N-1$ 以下の整数を入れる方法であって、次の条件を満たすものを構築せよ。

【条件】
$i = 1, 2, \dots, N$ について、 $i$ 行目または $i$ 列目のマスは $2N-1$ 個あるが、それらのマスに書かれた整数を小順に並べると $1, 2, \dots, 2N-1$ となる

制約

$1 \le N \le 500$

考えたこと

$N = 1$ と $N = 2$ は比較的容易に作れる。 $N = 3$ のときを試行錯誤すると、ダメそうだということがわかる。色々試すと、 $N$ が 3 以上の奇数の場合は上手く行かなそうだということがわかる。まずは、これを示そう。

$N$ が 3 以上の奇数のとき："No"

この場合は、 $v = 1, 2, \dots, 2N-1$ のいずれも、対角成分に登場する必要があることが言える。

$v$ の書かれたマスのうち、対角上にあるものの個数を $a$ 、それ以外のものの個数を $b$ とすると、

$a + 2b = N$

でなければならない。ここで、 $N$ は奇数なので、 $a$ も奇数である。よって、

$a \ge 1$

となる。

しかしながら、対角線上のマスは $N$ 個しかないので、 $N \ge 3$ のとき、 $2N-1$ 個の整数を配置することはできない。

$N$ が偶数のとき："Yes"

$N$ が偶数のときの構築方法はいろいろ考えられる。ここでは、まず、対角線上は同じ値であると決め打ちする（ここでは $2N-1$ とする）。

このとき、もし $i = 1, 2, \dots, N$ に対して、マス $(i, i)$ の左側と下側にある $N$ マス（下図に示す赤色の部分）に $1, 2, \dots, N$ を 1 個ずつ配置していく問題が解ければ、もとの問題も解けることがわかる。

ここから少し魔法のようなことをする。

まず、下の図の左側のように、規則的に $1, 2, \dots, N-1$ を並べる
そして、各列の最上段にあるものを最下段に持ってくる

たったこれだけで、 $N \times N$ グリッドの左下の部分を作ることができるのだ。

これで上手くいく理由は、このスライドで解説している。

あとは、対角成分に $2N-1$ を並べて、対角成分の右上のマスには、左下のマスを $2N-1$ から引いた値を入れていけば良い。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;

    if (N == 1) {
        cout << "Yes" << endl;
        cout << 1 << endl;
        return 0;
    }
    if (N % 2 == 1) {
        cout << "No" << endl;
        return 0;
    }

    vector<vector<int>> res(N, vector<int>(N, -1));

    for (int i = 0; i < N-1; i++) {
        int start = i;
        for (int j = 0; j < i; j++) {
            res[i][j] = start + 1;
            start = (start + 1) % (N-1);
        }
        res[N-1][i] = start + 1;
        start = (start + 1) % (N - 1);
        for (int k = i+1; k < N-1; k++) {
            res[k][i] = start + 1;
            start = (start + 1) % (N-1);
        }
    }

    for (int i = 0; i < N; i++) res[i][i] = N*2-1;
    for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) {
        res[i][j] = N*2-1 - res[j][i];
    }

    cout << "Yes" << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (j) cout << " ";
            cout << res[i][j];
        }
        cout << endl;
    }
}