行と列の最大値が指定されている場合にPythonで元の行列を復元する方法

問題の概要

サイズNの配列AとサイズMの配列B、さらにN×Mの2値行列が与えられているとします。この2値行列では、「1」は元の行列の対応する位置に正の整数が存在していたことを示し、「0」はその位置が元の行列でも0であったことを示します。私たちの課題は、A[i]がi行目の最大要素となり、B[j]がj列目の最大要素となるような元の行列を復元することです。

例えば、入力が A = [4, 2, 3]、B = [3, 1, 0, 0, 4, 0, 5] の場合、復元される行列は以下の出力例のようになります。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• N を配列Aのサイズとします
• M を配列Bのサイズとします
• i を 0 から N-1 まで繰り返します
  • j を 0 から M-1 まで繰り返します
    • mat[i][j] が 1 と等しい場合
      • A[i] と B[j] の最小値を出力します
    • それ以外の場合
      • 0 を出力します

なぜ「最小値」を取るのか?

セル(i, j)に入る値は、行iの最大値A[i]を超えてはならず、同時に列jの最大値B[j]も超えてはなりません。したがって、その位置に設定できる最大の値は min(A[i], B[j]) となります。入力が妥当である(解が存在する)限り、この値を採用することで、すべての行と列について最大値の条件が満たされることが保証されます。

実装例

理解を深めるために、以下のPythonによる実装例をご覧ください。

def print_original_mat(A, B, mat):
    N = len(A)
    M = len(B)
    for i in range(N):
        for j in range(M):
            if mat[i][j] == 1:
                print(min(A[i], B[j]), end=" ")
            else:
                print(0, end=" ")
        print()

A = [4, 2, 3]
B = [3, 1, 0, 0, 4, 0, 5]
mat = [
    [1, 0, 0, 0, 1, 0, 1],
    [0, 0, 1, 0, 0, 1, 1],
    [1, 1, 0, 1, 1, 0, 0]]
print_original_mat(A, B, mat)

入力

[4, 2, 3],
[3, 1, 0, 0, 4, 0, 5],
[[1, 0, 0, 0, 1, 0, 1],
[0, 0, 1, 0, 0, 1, 1],
[1, 1, 0, 1, 1, 0, 0]]

出力

3 0 0 0 4 0 4
0 0 0 0 0 0 2
3 1 0 0 3 0 0

計算量

このアルゴリズムの時間計算量は O(N×M) です。行列の各セルを一度だけ訪問するためです。また、結果をそのまま出力するため、追加の記憶領域は不要で、空間計算量は O(1) となります。