質問リンク

🟣 時間の複雑さ

コンシステンシテストの完全なナビゲーションを行う場合、行*列=10000のうち1マスあたりのskillの最大個数が100回であると判断した場合、1000000時間以内に更新を完了することができます.ただし、効率テストはタイムアウトします

🟢 使用するアルゴリズム:imos

で規定された区間において、開始と終了の部分集合を含む複数のコマンドが受信されると、演算を繰り返すと演算時間が非常に大きくなる.

imos法は、各コマンドに対して開始点と終了点のみを設定し、最後の反復計算値によって実現する.

1 Dアレイ上のIMOS

5プラス-2の原因は後でprefixSumを加える場合
0 2 2 2 0 0 0 0 0という結果が出てきて、5番目を0にして、同時に2の範囲を指定します.

最終的には以下のようになります

最後に前からPrefixSumを付けて結局終了

2 Dアレイ内のIMOS

矩形ごとに配列の値を更新すると、

が遅すぎます.

四角になっても基本的な考え方は同じです.「開始と終了のみを記録」

段の2次元では,次元の増加に伴って横からの開始と終了,縦からの開始と終了を2回記録し,シミュレーション時にも横から1回,縦からのprefixSumを1回求めることができる.

以下に示すように、開始と終了を記録する方法を見てみましょう.

要するに、以下の4つの点で注文することができます.

まず横からprefixSumを求める.

縦もprefixSumを求めます.

先ほど見た矩形にも適用してみましょう.

矩形ごとに1を照らすのではなく、4つの値を撮って2回巻いておけばいいのです.
矩形領域は全部で3つあります.矩形ごとに値を付けると、こうなります.

右にprefixSumを求めて、以下のようにします.

prefixSumを下に求め、結果を出します.

🟡 解答方法

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int[][] query;
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int n = board.length;
        int m = board[0].length;
        query = new int[n][m];
        for (int i = 0; i < skill.length; i++) {
            int r1 = skill[i][1];
            int c1 = skill[i][2];
            int r2 = skill[i][3];
            int c2 = skill[i][4];
            int val = skill[i][5];
            if (skill[i][0] == 1) { //적공격
                query[r1][c1] -= val;
                if(c2+1 < m) query[r1][c2 + 1] += val;
                if(r2+1 < n) query[r2 + 1][c1] += val;
                if(r2+1 < n && c2+1<m) query[r2 + 1][c2 + 1] -= val;
            } else {
                query[r1][c1] += val;
                if(c2+1 < m)query[r1][c2 + 1] -= val;
                if(r2+1 < n)query[r2 + 1][c1] -= val;
                if(r2+1 < n && c2+1<m)query[r2 + 1][c2 + 1] += val;
            }
        }

        //prefixSum
        for (int i = 0; i < query.length; i++) {
            for (int j = 1; j < query[i].length; j++) {
                query[i][j] += query[i][j - 1];
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                query[j][i] += query[j-1][i];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] += query[i][j];
                if(board[i][j] > 0) answer++;
            }
        }

        return answer;
    }


    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] board = {{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,5}};
        int[][] skill = {{1, 0, 0, 3, 4, 4}, {1, 2, 0, 2, 3, 2}, {2, 1, 0, 3, 1, 2}, {1, 0, 1, 3, 3, 1}};
        T.solution(board, skill);
    }
}

🧩 Reference

https://driip.me/65d9b58c-bf02-44bf-8fba-54d394ed21e0