C++で2つの行列を等しくするために必要な変換の回数を求める方法

この記事では、同じサイズの2つの行列 mat1 と mat2 が与えられたとき、一方の行列を操作してもう一方と等しくするために必要な変換の回数を求める方法を解説します。

問題の概要

許可されている変換操作は以下の3ステップです。

• 2つの行列のどちらか一方を選ぶ
• 選んだ行列から1つの行または列を選ぶ
• 選んだ行または列のすべての要素に1を加える

入力例

mat1[][] = {{1, 2},
            {2, 1}}
mat2[][] = {{2, 3},
            {4, 3}}

出力例

3

解説

以下のように3回の操作で2つの行列を一致させることができます。

1 2 => 2 2 => 2 3 => 2 3
2 1 => 3 1 => 3 2 => 4 3

解法アプローチ

まず、そもそも変換によって2つの行列を等しくできるかどうかを判定します。そのために、2つの行列の差分を取り、以下の条件をチェックします。

if (mat[i][j] - mat[i][0] - mat[0][j] + mat[0][0] != 0)

この条件が1つでも成り立つ場合は、どれだけ操作を繰り返しても2つの行列を一致させることができないため、解は存在しません（-1を返します）。

変換が可能な場合は、0行目と0列目の値を基準にして、行と列それぞれに必要な変換の回数を数えます。

実装例

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;

int countTransformationReq(int mat1[][MAX], int mat2[][MAX],
                           int m, int n) {
    // 差分行列を求める
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            mat1[i][j] -= mat2[i][j];

    // 変換が可能かどうかを判定
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            if (mat1[i][j] - mat1[i][0] - mat1[0][j] +
                mat1[0][0] != 0)
                return -1;

    // 行と列の変換回数をカウント
    int trxCount = 0;
    for (int i = 0; i < n; i++)
        trxCount += abs(mat1[i][0]);
    for (int j = 0; j < m; j++)
        trxCount += abs(mat1[0][j] - mat1[0][0]);
    return trxCount;
}

int main() {
    int mat1[MAX][MAX] = {{1, 2}, {2, 1}};
    int mat2[MAX][MAX] = {{2, 3}, {4, 3}};
    cout << "2つの行列を等しくするために必要な変換の回数: "
         << countTransformationReq(mat1, mat2, 2, 2);
    return 0;
}

出力

2つの行列を等しくするために必要な変換の回数: 3

効率的なアプローチのポイント

この問題で重要なのは、行や列への加算が複数の要素に同時に影響するという点です。すべての要素を個別に扱うと変換回数を二重に数えてしまうため、0行目と0列目を基準として各変換をちょうど1回ずつ数えることが鍵になります。これは「握手の公式（handshake formula）」の考え方に似ており、重複のないカウントによって正確な回数を求められます。

最適化された実装例

#include <iostream>
#include <cstdlib>
using namespace std;
const int MAX = 100;

int countTransformations(int mat1[][MAX], int mat2[][MAX],
                         int m, int n) {
    int diff[MAX][MAX];

    // 差分行列を計算
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            diff[i][j] = mat1[i][j] - mat2[i][j];

    // 変換不可能な場合は -1 を返す
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            if (diff[i][j] - diff[i][0] - diff[0][j] +
                diff[0][0] != 0)
                return -1;

    // 行変換の回数（0列目の絶対値の合計）
    int rowCount = 0;
    for (int i = 0; i < n; i++)
        rowCount += abs(diff[i][0]);

    // 列変換の回数（0行目の絶対値の合計）
    int colCount = 0;
    for (int j = 0; j < m; j++)
        colCount += abs(diff[0][j] - diff[0][0]);

    return rowCount + colCount;
}

int main() {
    int mat1[MAX][MAX] = {{1, 2}, {2, 1}};
    int mat2[MAX][MAX] = {{2, 3}, {4, 3}};
    cout << "2つの行列を等しくするために必要な変換の回数: "
         << countTransformations(mat1, mat2, 2, 2) << endl;
    return 0;
}

出力

2つの行列を等しくするために必要な変換の回数: 3

計算量とまとめ

このアルゴリズムの時間計算量は O(m×n) で、差分行列を数回走査するだけで答えが求まります。補助的に使うのは固定サイズの配列のみなので、空間計算量も O(m×n)（入力行列をそのまま差分として再利用すれば O(1) 追加）に抑えられます。

2つの行列を等しくするために必要な変換の回数を求める問題は、差分行列を作成し、その0行目・0列目の値を基準にカウントすることで、シンプルかつ効率的に解くことができます。まず変換の可否を判定し、可能な場合のみ回数を数えるという流れを押さえておきましょう。