[HackerRank] Flipping the Matrixの解説

問題文

https://www.hackerrank.com/challenges/flipping-the-matrix/problem

はじめに

最近久しぶりにアルゴリズムの勉強を再開しました。
1年前ほどにAtcoderの緑まで到達したきり何もしていなかったので肩慣らし中です。
今回Flipping the Matrixが全然解けなかったので、復習した過程を備忘録として残しておきます。

解法

概要

列と行の反転を無制限に行える という制約の本質を見抜く必要がありました。
実は各セルの移動範囲には規則性があり、とても限定的な範囲のため、この点を見抜ければ後は単純なコードに落とすだけです。

可視化

まずは、先述した規則性を把握しやすくするために可視化してみます。
下図が $n=2$ と $n=3$ のパターンになります。
セルの値は$[行,列] = [i,j]$を表しており、色毎に移動先の範囲を表しています。
また、赤線の中にある値の合計が最大値になることがゴールです。
ポイントは$n$がどんな値でも、赤線に含まれる色は必ず1種類1つだけになる、ということです。

式化

$n = 3$を例に、各色の1点を基準にして、残りの3点の位置を考えてみます。
$[0,0] => [0,5],[5,0],[5,5]$
$[0,1] => [0,4],[5,1],[5,4]$
$[0,2] => [0,3],[5,2],[5,3]$

上記を$n$の変数を使って表現すると
$[0,0] => [0,2n-1],[2n-1,0],[2n-1,2n-1]$
$[0,1] => [0,2n-2],[2n-1,1],[2n-1,2n-2]$
$[0,2] => [0,2n-3],[2n-1,2],[2n-1,2n-3]$

式にすると
$[i,j] => [i,2n-1-j],[2n-1-i,j],[2n-1-i,2n-1-j]$

最終的なコードは下記になります。

flippingMatrix

function flippingMatrix(matrix: number[][]): number {
    const h = matrix.length;
    const w = matrix[0].length;
    const n = Math.floor(matrix.length/2);
    const l = 2*n-1
    let sum = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            sum += Math.max(matrix[i][j], matrix[i][l-j], matrix[l-i][j],matrix[l-i][l-j])
        }
    }
    return sum; 
}

参考

解説に出てくる図を見て、そうゆうことか！ってなりました
https://youtu.be/4rin1enhuQQ?t=60