【C++】庭全体に水をやるために開くべき蛇口の最小本数を求める

x軸上に一次元の庭があるとします。庭の始点は位置0、終点は位置nです。庭には位置[0, 1, ..., n]に合計n + 1個の蛇口が設置されています。ここで、整数nと長さn + 1の整数配列rangesが与えられ、ranges[i]は「i番目の蛇口を開けると、範囲[i - ranges[i], i + ranges[i]]へ水をまける」ことを表します。

この問題の目的は、庭全体に水を行き渡らせるために開く必要のある蛇口の最小本数を求めることです。どのように組み合わせても全域をカバーできない場合は、-1を返します。

たとえば、入力がn = 5、ranges = [3, 4, 1, 1, 1, 0]である場合、出力は1になります。これは、2番目の蛇口（インデックス1）ひとつで[-3, 5]の範囲、すなわち庭全体をカバーできるためです。

解法のアプローチ

この問題は、「各区間の到達範囲をあらかじめ記録しておき、貪欲法（グリーディ法）でカバー範囲を限界まで伸ばしていく」という発想で効率よく解けます。「ジャンプゲームII」と同様に、現在カバーできている範囲の中から、最も遠くまで届く地点を順番に探していくイメージです。

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

• サイズ(n + 1)の配列vを宣言し、すべての要素を-1で初期化する
• iを0からnまで1ずつ増やしながら、以下を繰り返す
  • u := max(i - ranges[i], 0)（蛇口iが届く左端、ただし負にはしない）
  • e := min(n, i + ranges[i])（蛇口iが届く右端、ただしnを超えない）
  • v[u] := max(v[u], e)　… 位置uから最も遠くまで届く右端を記録する
• v[0]が-1の場合（位置0をカバーできる蛇口が存在しない場合）、-1を返す
• curr := v[0]（最初の蛇口でカバーできる範囲の右端）
• i := 0、next := 0、ret := 1 で初期化する
• curr < n の間、以下を繰り返す
  • i <= curr の間、next := max(next, v[i]) を更新しながら i を1ずつ増やす
  • next == curr の場合（これ以上先へ進めない＝隙間が埋められない場合）、-1を返す
  • curr := next として到達範囲を更新する
  • ret を1増やす（新たに蛇口を1本開いたことに相当）
• 最後にretを返す

実装例

以下のC++コードを見ると、処理の流れがより明確に理解できるでしょう。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minTaps(int n, vector<int>& ranges) {
        int ret = 1;
        vector<int> v(n + 1, -1);
        for (int i = 0; i <= n; i++) {
            int u = max(i - ranges[i], 0);
            int e = min(n, i + ranges[i]);
            v[u] = max(v[u], e);
        }
        if (v[0] == -1)
        return -1;
        int curr = v[0];
        int i = 0;
        int next = 0;
        while (curr < n) {
            while (i <= curr) {
                next = max(next, v[i]);
                i++;
            }
            if (next == curr)
            return -1;
            curr = next;
            ret++;
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {3,4,1,1,1,0};
    cout << (ob.minTaps(5, v));
}

入力

5, {3,4,1,1,1,0}

出力

1

計算量の目安

• 時間計算量：O(n) — 各位置を高々一定回しか走査しないため、線形時間で処理できます。
• 空間計算量：O(n) — 各位置からの最大到達範囲を記録する配列vが必要です。