C++で与えられた行列が「良い行列」かどうかを判定する方法

「良い行列」とは何か

n × n の行列を考えてみましょう。すべての要素のうち 1 以外の数値が、必ず「同じ行に含まれるある数」と「同じ列に含まれるある数」の和として表せるとき、その行列を良い行列（Good Matrix）と呼びます。本記事では、与えられた行列が良い行列かどうかを判定する C++ プログラムを解説します。

たとえば、次のような行列が入力されたとします。

このときの出力は True になります。左下の 6 は、すぐ上の 2 と右隣の 4 の和（2 + 4 = 6）で表せるためです。それ以外の 1 以外の数値も、すべて同じ条件を満たしています。

アルゴリズムの考え方

この問題は、全探索（総当たり）を使えばシンプルに解くことができます。手順は以下の通りです。

1. 行列 M のサイズを n とします。
2. すべてのセル (i, j) について次の処理を行います。
   • 判定用フラグ ok を 0（未発見）で初期化します。
   • M[i][j] が 1 でなければ、その値を c として記録します。
   • 同じ行 i の各要素 M[i][h] と、同じ列 j の各要素 M[k][j] のすべての組み合わせを調べ、c == M[i][h] + M[k][j] が成立すれば ok を 1 にします。
   • 最後まで ok が 0 のまま、かつ M[i][j] が 1 でない場合は、その時点で false を返します。
3. すべてのセルが条件を満たしていれば true を返します。

C++ による実装例

理解を深めるために、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<vector<int>> M){
   int n = M.size();
   int c;
   bool ok;
   for (int i = 0; i < n; i++){
      for (int j = 0; j < n; j++){
         ok = 0;
         if (M[i][j] != 1)
            c = M[i][j];
         for (int h = 0; h < n; h++){
            for (int k = 0; k < n; k++)
               if (c == M[i][h] + M[k][j])
                  ok = 1;
         }
         if (ok == 0 && M[i][j] != 1){
            return false;
         }
      }
   }
   return true;
}
int main(){
   vector<vector<int>> matrix = { { 1, 1, 2 }, { 2, 3, 1 }, { 6, 4, 1 } };
   cout << solve(matrix) << endl;
}

入力

{ { 1, 1, 2 }, { 2, 3, 1 }, { 6, 4, 1 } }

出力

1

計算量について

このアルゴリズムは 4 重のループを使用するため、時間計算量は O(n⁴) となります。一方で、追加のメモリは定数個の変数のみなので、空間計算量は O(1) です。小〜中規模の行列であれば十分実用的ですが、より大きな行列を扱う場合は、あらかじめ各行・各列の値の集合を構築しておくことで O(n³) まで高速化できるなど、効率的な手法を検討するとよいでしょう。