Pythonで同じ位置の値を交換して2つの行列を狭義単調増加にできるか判定する方法

問題の概要

サイズ n × m の2つの行列 mat1 と mat2 があるとします。同じ位置 (i, j) にある要素同士であれば、2つの行列の間で自由に入れ替えることができます。この操作だけを使って、両方の行列を「狭義単調増加」な行列（すべての行と列が、左から右へ、上から下へ向かって値が厳密に増加する状態）にできるかどうかを判定してください。

入力例

たとえば、次のような2つの行列が与えられたとします。

この場合の出力は True になります。実際、(7, 14) と (10, 17) のペアを入れ替えると、2つの行列は次のようにどちらも狭義単調増加になります。

解法のアプローチ

この問題は貪欲法（グリーディ法）で効率よく解くことができます。ポイントは「各位置において、小さい値を mat1 側に、大きい値を mat2 側に配置すればよい」ということです。ある位置で mat1[i][j] > mat2[i][j] となっている場合は入れ替えても不利になることはありません。後続の検証では各行・各列の隣接要素の大小関係しか見ないため、その位置に小さい値を置いておく方が常に有利だからです。

具体的な手順は以下の通りです。

• row に mat1 の行数、col に mat1 の列数を代入する
• すべての位置 (i, j) について、mat1[i][j] > mat2[i][j] であれば2つの値を入れ替える
• すべての行について、隣接する要素が厳密に増加しているか確認し、mat1[i][j] >= mat1[i][j+1] または mat2[i][j] >= mat2[i][j+1] となる箇所があれば False を返す
• すべての列についても同様に、mat1[i][j] >= mat1[i+1][j] または mat2[i][j] >= mat2[i+1][j] となる箇所があれば False を返す
• すべてのチェックを通過したら True を返す

計算量は行列の全要素を数回走査するだけなので O(n × m) となり、非常に効率的です。

Pythonコード例

それでは、実際の実装を見てみましょう。

def solve(mat1, mat2):
    row = len(mat1)
    col = len(mat1[0])
    # 各位置で小さい方の値を mat1 に配置する
    for i in range(row):
        for j in range(col):
            if mat1[i][j] > mat2[i][j]:
                mat1[i][j], mat2[i][j] = mat2[i][j], mat1[i][j]
    # 行方向の厳密な増加を確認
    for i in range(row):
        for j in range(col - 1):
            if mat1[i][j] >= mat1[i][j + 1] or mat2[i][j] >= mat2[i][j + 1]:
                return False
    # 列方向の厳密な増加を確認
    for i in range(row - 1):
        for j in range(col):
            if mat1[i][j] >= mat1[i + 1][j] or mat2[i][j] >= mat2[i + 1][j]:
                return False
    return True

mat1 = [[7, 15],
        [16, 10]]
mat2 = [[14, 9],
        [8, 17]]
print(solve(mat1, mat2))

入力

[[7, 15],
[16, 10]],
[[14, 9],
[8, 17]]

出力

True

まとめ

同じ位置の要素同士しか入れ替えられないという制約があるため、一見複雑に思えますが、「小さい値を mat1 に寄せる」という貪欲な戦略を取れば、あとは行・列方向の単調性を線形時間で検証するだけで答えが得られます。この手法は計算量 O(n × m)、追加メモリ O(1) で動作するため、大きな行列に対しても実用的です。