C++で解く「範囲加算 II」問題 ― 最大値の個数を効率的に求める方法

問題の概要

m × n の行列 M があり、すべての要素が 0 で初期化されているとします。ここに、複数の更新操作が与えられます。操作は 2 次元配列として表され、各操作は 2 つの正の整数 a と b からなる配列 [a, b] です。これは「0 ≤ i < a かつ 0 ≤ j < b を満たすすべての M[i][j] に 1 を加算する」という意味になります。すべての操作を実行した後、行列内に存在する最大値の出現回数を求めてください。

入力例

m = 3、n = 3、operations = [[2,2],[3,3]] の場合、出力は 4 になります。

初期状態の行列は次のとおりです。

操作 [2,2] を実行すると、行列は次のようになります。

続けて操作 [3,3] を実行すると、次のようになります。

最終的な行列の最大値は 2 で、その出現回数は 4 回であるため、答えは 4 となります。

解法のアプローチ

この問題の鍵は、「最大値を持つセルは、すべての操作の影響を受けたセルである」という点に気づくことです。つまり、答えはすべての操作範囲の共通部分のサイズ、すなわち「各操作の a の最小値 × 各操作の b の最小値」で求められます。行列を実際に構築する必要はなく、非常に効率的に計算できます。

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

• minR := m、minC := n で初期化する

• ops 配列内の各操作 op に対して以下を実行する

  • minR := min(minR, op[0])

  • minC := min(minC, op[1])

• minR * minC を返す

C++ 実装例

以下の実装例で、具体的な動きを確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maxCount(int m, int n, const vector<vector<int>>& ops) {
        int minR = m;
        int minC = n;
        for (const auto& op : ops){
            minR = min(minR, op[0]);
            minC = min(minC, op[1]);
        }
        return minR * minC;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{2,2},{3,3}};
    cout << (ob.maxCount(3,3,v));
}

入力

3,3,{{2,2},{3,3}}

出力

4

計算量の評価

この解法の時間計算量は O(k)（k は操作の数）、空間計算量は O(1) です。行列を実際に生成して各操作をシミュレーションする方法（O(m × n × k)）と比べると、大幅に効率化されていることがわかります。