区画制限を満たしながら家づくりの利益を最大化するC++コードの解説

問題の概要

2つの整数 n と h、さらに m 個の三つ組からなる配列 T（T[i] = (li, ri, xi)）が与えられます。

道路沿いには家を建てられる場所が n 箇所あり、それぞれ 1 から n までの番号が付けられています。各場所に建てる家の高さは 0 から h の範囲で自由に選べます。ある場所に高さ k の家を建てると、k² の利益が得られます。

一方、区域ごとの高さ制限が m 個設けられています。i 番目の制限は「地点 li から ri までの区間にある家のうち、最も高いものの高さは xi 以下でなければならない」というものです。

すべての制限を満たしながら利益を最大化するとき、達成可能な最大の利益を求めるのがこの問題です。

具体例

入力が n = 3、h = 3、T = [[1, 1, 1], [2, 2, 3], [3, 3, 2]] の場合を考えてみましょう。このときの出力は 14 になります。

家は全部で 3 軒分の建設候補地があり、最大高さは 3 です。各制限は次のように適用されます。

• 1番目の制限：地点 1〜1 の最高高さは 1 以下 → 高さ 1 の家を建築
• 2番目の制限：地点 2〜2 の最高高さは 3 以下 → 高さ 3 の家を建築
• 3番目の制限：地点 3〜3 の最高高さは 2 以下 → 高さ 2 の家を建築

したがって最適な高さの組み合わせは [1, 3, 2] となり、利益は 1² + 3² + 2² = 14 となります。

解法のアプローチ

この問題はシンプルな貪欲的な発想で解くことができます。基本的な方針は以下の通りです。

• まず、すべての地点の高さを上限値 h で初期化します（高さが高いほど利益が大きいため）。
• 次に、各区域制限について、その区間内の各地点の高さを「現在の高さ」と「制限値」のうち小さい方へ更新します。
• 最後に、すべての地点の高さの二乗和を計算し、答えとして返します。

この方法なら、各区間の制限を確実に満たしつつ、各地点で可能な限り高い家を建てられます。

アルゴリズムの手順

m := T のサイズ
heights をサイズ n・初期値 h の配列として定義
i := 0 から i < m まで 1 ずつ増やしながら繰り返す:
    l := T[i][0]
    r := T[i][1]
    x := T[i][2]
    j := l - 1 から j < r まで 1 ずつ増やしながら繰り返す:
        heights[j] := heights[j] と x の最小値
ans := 0
i := 0 から i < n まで 1 ずつ増やしながら繰り返す:
    ans := ans + heights[i] × heights[i]
ans を返す

C++での実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int n, int h, vector<vector<int>> T){
    int l, r;
    int m = T.size();
    vector<int> heights(n, h);
    for (int i = 0; i < m; i++){
        l = T[i][0];
        r = T[i][1];
        h = T[i][2];
        for (int i = l - 1; i < r; i++)
        heights[i] = min(heights[i], h);
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    ans += heights[i] * heights[i];
    return ans;
}
int main(){
    int n = 3;
    int h = 3;
    vector<vector<int>> T = { { 1, 1, 1 }, { 2, 2, 3 }, { 3, 3, 2 } };
    cout << solve(n, h, T) << endl;
}

入力

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

出力

14

計算量と補足

このアルゴリズムは、制限ごとに区間を走査するため計算量は O(m × n) です。n と m が十分に小さい場合は実用的ですが、入力規模が大きくなる場合は遅延伝播セグメント木（Lazy Segment Tree）による区間 chmin クエリなどを用いることで効率よく高速化できます。