C++で解く「人々を救うためのボート」問題 ― 最小ボート数を求める貪欲法アルゴリズム

問題の概要

people という配列が与えられ、i 番目の人の体重が people[i] で表されるとします。各ボートには同時に最大2人まで乗せることができ、ただし搭乗者の体重の合計は limit 以下でなければなりません。この条件のもと、すべての人を運ぶために必要な最小のボート数を求めるのがこの問題のゴールです。

たとえば、入力が [3, 2, 1, 2]、limit が 3 の場合、答えは 3 となります。具体的な割り当ては [(1, 2), (2), (3)] のようになります。

解法のアプローチ：ソート＋両端ポインタ

この問題は、貪欲法（グリーディ法）と両端ポインタ（Two Pointers）を組み合わせることで効率的に解けます。基本的な発想は、「最も重い人は必ずどこかのボートに乗らなければならない。乗れるなら最も軽い人とペアを組ませ、無理なら単独で乗せる」というものです。

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

• people 配列を昇順にソートします。

• i := 0、j := 配列サイズ − 1、ret := 0 として初期化します。

• i ≤ j の間、次の処理を繰り返します。

  • people[i] + people[j] ≤ limit であれば、i を +1、j を −1 します（2人乗せ）。そうでなければ j のみ −1 します（最も重い人が単独で乗船）。

  • ret を +1 します（使用したボートをカウント）。

• 最後に ret を返します。

なぜこの手法が最適なのかというと、最も重い人 j について、仮に最も軽い人 i とのペアでも limit を超えてしまうなら、他の誰とも組むことができず、必ず単独のボートが必要になるからです。逆に、最も軽い人と組めるのであれば、それ以上良いパートナーは存在しないため、この選択が常に最適な結果をもたらします。

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int numRescueBoats(vector<int>& people, int limit) {
      sort(people.begin(), people.end());
      int i = 0;
      int j = people.size() - 1;
      int ret = 0;
      while(i <= j){
         if(people[i] + people[j] <= limit){
               i++, j--;
         }else{
            j--;
         }  
         ret++;
      }
      return ret;
   }
};
main(){
   vector<int> v = {3,2,1,2};
   Solution ob;
   cout << (ob.numRescueBoats(v, 3));
}

入力

[3,2,1,2]
3

出力

3

計算量の評価

• 時間計算量： O(n log n)。ソート処理が支配的であり、その後のポインタ操作は線形時間 O(n) で完了します。

• 空間計算量： O(1)。追加のデータ構造を使わず、ポインタとカウンタのみで処理できるため、メモリ効率に優れています。