C++で0またはnだけで構成される3×3行列の最大行列式を求める方法

問題概要

正の整数 n が与えられたとき、各要素が 0 または n のいずれかで構成される 3×3 行列の中から、最大の行列式を持つ行列を見つけるのが本記事のテーマです。

例

n = 15 の場合、たとえば次のような行列が考えられます。

{{15, 15, 0}
{0, 15, 15}
{15, 0, 15}}

要素が 0 か n のみで構成される任意の 3×3 行列において、行列式の最大値は 2 × n³ であることが証明されています。したがって、この場合の答えは以下の通りです。

2 × 15³ = 6750

なぜ最大値が 2n³ になるのか

各要素が 0 または n の行列は、各行から n をくくり出すことで、0 と 1 だけの行列に変換できます。この操作により行列式は全体で n³ 倍されるため、元の問題は「0/1 行列の行列式の最大値 × n³」を求める問題に帰着できます。

そして、3×3 の 0/1 行列が取り得る行列式の最大値は 2 です。実際、次の行列の行列式を計算すると 2 になります。

{{1, 1, 0}
{0, 1, 1}
{1, 0, 1}}

よって、0 と n のみで構成される 3×3 行列の最大行列式は 2n³ であり、これが本問題の答えとなります。

アルゴリズム

1. 正の整数 n を入力として受け取ります。
2. 最大行列式の値を公式「2 × n × n × n」から計算します。
3. あわせて、最大行列式を実現する行列（(0,2)、(1,0)、(2,1) の位置に 0 を配置し、残りの要素にはすべて n を配置）を出力します。

計算は定数回の乗算のみで完了するため、時間計算量・空間計算量ともに O(1) という非常に効率的なアルゴリズムです。

C++ による実装例

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

int getMaxDeterminant(int n){
    return (2 * n * n * n);
}

void printMatrix(int n){
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if ((i == 0 && j == 2) ||
                (i == 1 && j == 0) ||
                (i == 2 && j == 1)) {
                printf("%-5d", 0);
            } else {
                printf("%-5d", n);
            }
        }
        printf("\n");
    }
}

int main() {
    int n = 15;
    cout << "Matrix is:\n";
    printMatrix(n);
    cout << "\nMaximum determinant = " << getMaxDeterminant(n) << endl;
    return 0;
}

出力

Matrix is:
15   15   0
0    15   15
15   0    15

Maximum determinant = 6750

まとめ

0 と n だけで構成される 3×3 行列の最大行列式は、数学的に 2n³ に等しいことが示せます。そのため、複雑な探索や全パターンの列挙を行う必要はなく、公式に n を代入するだけで O(1) で答えを求められます。競技プログラミングなどでも頻出のテクニックなので、0/1 行列の性質ごと覚えておくと役立ちます。