KUPC 2024 N - Nonsymmetric Matrix (4D)

チーム戦で、hotman-san、アトリウムさんと一緒に解いて、協力ゲーという感じがして楽しかった！！

N の過程。協力ゲー感あってすごい楽しかった！！！

hotman さん：「巡回する感じで結構行けるね」

僕：「巡回でやってみたら、N が奇数の場合は、スコア 1 でできた」

僕：「N = 2 はそもそも不可能で、N = 4 もスコア 1 ではできないね。N が偶数だスコア 1 でできない？」

hotman さん：「N = 6…

— けんちょん (@drken1215) 2025年1月5日

• 問題へのリンク

問題概要

各成分が整数である 行列 であって、以下の条件を満たすものが存在するか判定し、存在する場合は、そのうち が最小となるものを 1 つ求めよ。

• どの行も、行和が 0 である
• どの列も、列和が 0 である
• のとき、 である

制約

• 

考えたこと

僕らのチームの思考過程は、上に示した Twitter 投稿の通りだが、 が偶数のときの構築を「 が 4 の倍数のとき」と「 が 4 で割れない偶数のとき」に分ける必要があって煩雑であった。

その後、よりよい構築方法が見出されたので、それを記す。

が奇数のとき

以下が条件を満たす。まず、0 行目を

 0  1  -1  1 -1  1 -1 ...

というように、最初に 0 を置いて、その後は 1 と -1 を繰り返すようにする。1 行目以降は、これを次のように巡回させていく。

 0  1 -1  1 -1  1 -1 ...
-1  0  1 -1  1 -1  1 ...
 1 -1  0  1 -1  1 -1 ...
-1  1 -1  0  1 -1  1 ...
...

たとえば、 のときは、次のようになる。

 0  1 -1  1 -1
-1  0  1 -1  1
 1 -1  0  1 -1
-1  1 -1  0  1
 1 -1  1 -1  0

のとき

条件を満たすものは明らかに存在しない。

のとき

この場合は全探索により、 の最大値を 1 以下に抑えられる解は存在しないことがわかった。 の最大値が 2 である解は次のものが見つかった。

 1 -1  1 -1
 1 -1  1 -1
-2  2 -2  2
 0  0  0  0

が 以上の偶数のとき

が 以上の偶数のとき、 は 3 以上の奇数である。よって、 については解を構築できる。

この の場合の解を用いて、 の場合の解を下の図のように構成できる。ここで、赤枠で囲ったものは、同じものを繰り返すことを意味する。

コード

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

// checker
bool check(int N, const vector<vector<int>> &res) {
    for (int i = 0; i < N; i++) {
        int sum = 0;
        for (int j = 0; j < N; j++) sum += res[i][j];
        if (sum != 0) return false;
    }
    for (int i = 0; i < N; i++) {
        int sum = 0;
        for (int j = 0; j < N; j++) sum += res[j][i];
        if (sum != 0) return false;
    }
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            if (res[i][j] == res[j][i]) {
                cout << i << ", " << j << endl;
                return false;
            }
        }
    }
    return true;
}

// N = 2 以外の場合を再帰的に求める
vector<vector<int>> func(int N) {
    vector<vector<int>> res(N, vector<int>(N, 0));

    if (N == 4) {
        res[0] = {1, -1, 1, -1};
        res[1] = {1, -1, 1, -1};
        res[2] = {-2, 2, -2, 2};
        res[3] = {0, 0, 0, 0};
        return res;
    } else if (N % 2 == 1) {
        // 奇数の場合は {0, 1, -1, 1, -1, ...} を各行で巡回させていく
        vector<int> base(N, 0);
        for (int i = 1; i < N; i++) {
            if (i % 2 == 1) base[i] = 1;
            else base[i] = -1;
        }
        vector<vector<int>> res(N, vector<int>(N, 0));
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
            res[i][j] = base[(j - i + N) % N];
        }
        return res;
    } else {
        // 偶数の場合は、N - 3 の場合を用いて構築する
        auto divN3 = func(N - 3);
        auto div3 = func(3);
        for (int i = 0; i < N - 3; i++) for (int j = 0; j < N - 3; j++) {
            res[i][j] = divN3[i][j];
        }
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
            res[i + N - 3][j + N - 3] = div3[i][j];
            res[i + N - 6][j + N - 3] = vector<int>({-1, 0, 1})[(j+3-i)%3];
            res[i + N - 3][j + N - 6] = vector<int>({1, 0, -1})[(j+3-i)%3];
        }
        for (int i = 0; i < N - 6; i++) {
            res[i][N - 3] = 0;
            if (i % 2 == 0) res[i][N - 2] = 1, res[i][N - 1] = -1;
            else res[i][N - 2] = -1, res[i][N - 1] = 1;
        }
        for (int j = 0; j < N - 6; j++) {
            res[N - 1][j] = 0;
            if (j % 2 == 0) res[N - 3][j] = 1, res[N - 2][j] = -1;
            else res[N - 3][j] = -1, res[N - 2][j] = 1;
        }
    }
    return res;
}

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

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

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