問題概要

m × n のサイズの二次元行列 grid が与えられます。同じサイズの解答行列 answer を作成する必要があります。

行列 answer の各セル (r, c) の値は以下のように計算されます：

• topLeft[r][c] は行列 grid のセル (r, c) の左上対角線上にある異なる値の数です。
• bottomRight[r][c] は行列 grid のセル (r, c) の右下対角線上にある異なる値の数です。

そして answer[r][c] = |topLeft[r][c] - bottomRight[r][c]| となります。

行列の対角線とは、最上行または最左列のセルから始まり、右下方向へ行列の終わりまで向かう対角線を指します。

セル (r1, c1) とセル (r, c) が同じ対角線に属し、かつ r1 < r の場合、セル (r1, c1) はセル (r, c) の左上対角線に属します。同様に右下対角線も定義されます。

例1：

入力：grid = [[1,2,3],[3,1,5],[3,2,1]]
出力：[[1,1,0],[1,0,1],[0,1,1]]

説明：

• セル (0,0) の右下対角線には [1,1] が含まれ、左上対角線には [] が含まれます。答えは |1 - 0| = 1 です。
• セル (1,2) の右下対角線には [] が含まれ、左上対角線には [2] が含まれます。答えは |0 - 1| = 1 です。
• セル (1,1) の右下対角線には [1] が含まれ、左上対角線には [1] が含まれます。答えは |1 - 1| = 0 です。

例2：

入力：grid = [[1]]
出力：[[0]]

説明：セル (0,0) の右下対角線と左上対角線には [] が含まれます。答えは |0 - 0| = 0 です。

解法アプローチ

この問題では、行列の対角線は左上から右下方向の対角線のみを指します。現在位置が (i, j) の場合、左上対角線は (i-1, j-1)、(i-2, j-2)、(i-3, j-3)、... の位置の連なりを指し、右下対角線は (i+1, j+1)、(i+2, j+2)、(i+3, j+3)、... の位置の連なりを指します。左上対角線と右下対角線のどちらも現在のセルを含みません。

問題を理解したら、まず直接的なシミュレーションが考えられます。二次元配列の各位置を走査し、その位置の左上と右下の対角線上にある異なる値の数を計算します。異なる値の数を数える最も直感的な方法はSetを使うことですが、値の範囲が[1, 50]と小さいため、ビットマップの考え方を応用できます。Long型（64ビット）の値を使用し、値xが現れたら右からx番目のビットを1に設定します。最終的に異なる値の数はこのLong値のバイナリ表現における1の数となります。

最適化された解法

直接的なシミュレーション方法では、同じ対角線上の各位置を処理するたびに計算が行われるため、無駄が生じます。二次元配列を走査する際に、伝統的な行と列の順序ではなく、対角線ごとに走査することで最適化できます。同じ対角線上の位置では i - j の値が等しいことがわかります。したがって、i - j を使って1つの対角線を表すことができます。この対角線上の位置は1次元配列を形成し、前から後ろへと後ろから前へそれぞれ1回走査するだけで、各位置の左上と右下部分における異なる値の数を得ることができます。

最適化された実装コード

public int[][] calculateDiagonalDifference(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int[][] result = new int[rows][cols];
    
    // 左上対角線に現れる数値を記録
    long upperDiagonal = 0L;
    // 右下対角線に現れる数値を記録
    long lowerDiagonal = 0L;
    
    // 各対角線を i - j で表現し、対角線上の各数値で i - j は同じ値になる
    for (int k = 1 - cols; k <= rows - 1; k++) {
        // 左上部分に現れる数値を計算
        upperDiagonal = 0;
        // 各k値について、0 <= i < rows && 0 <= j < cols を満たす必要がある
        for (int i = 0; i < rows; i++) {
            int j = i - k;
            // 範囲外の場合を除外
            if (j < 0 || j >= cols) {
                continue;
            }
            result[i][j] = Long.bitCount(upperDiagonal);
            upperDiagonal |= 1L << matrix[i][j];
        }

        // 右下部分に現れる数値を計算
        lowerDiagonal = 0L;
        for (int i = rows - 1; i >= 0; i--) {
            int j = i - k;
            // 範囲外の場合を除外
            if (j < 0 || j >= cols) {
                continue;
            }
            result[i][j] = Math.abs(result[i][j] - Long.bitCount(lowerDiagonal));
            lowerDiagonal |= 1L << matrix[i][j];
        }
    }
    return result;
}

この最適化されたアプローチでは、各対角線を一度だけ処理するため、時間計算量が改善されます。ビット操作を使用して異なる値の数を効率的にカウントしている点も特徴です。