C++で車のフリート（車隊）の数を求める方法

問題概要

同じ目的地に向かうN台の車が、片側1車線の道路を走行しているとします。目的地までは「target」マイル離れており、各車iは一定の速度speed[i]（マイル毎時）を持ち、出発時点での位置は目的地からposition[i]マイル手前にあります。

車は前方の車を追い越すことはできませんが、追いついてバンパー同士をくっつけたまま同じ速度で走ることは可能です。このとき2台の車間距離は無視され、同じ位置にいるものとみなされます。車のフリート（車隊）とは、同じ位置・同じ速度で走行する1台以上の車の集合のことです。仮にある車が目的地ちょうどの地点でフリートに追いついた場合も、その車はそのフリートに含まれるものとみなします。このとき、目的地に到着するフリートの総数を求めてください。

入力例

target = 12、position = [10,8,0,5,3]、speed = [2,4,1,1,3]の場合、出力は3になります。

• 位置10を出発する車と位置8を出発する車は、ちょうど目的地の12の地点で合流し、1つのフリートになります。
• 位置0を出発する車は他のどの車にも追いつけないため、単独で1つのフリートとなります。
• 位置5を出発する車と位置3を出発する車は、6の地点で合流し、1つのフリートになります。

解法のアプローチ

この問題は「目的地への到達時間」に注目することで、ソートとスタックを組み合わせて効率的に解くことができます。手順は以下の通りです。

1. (位置, 速度) のペアを格納する配列vを作成し、n を位置配列 p のサイズとします。
2. i を 0 ～ n-1 の範囲でループし、v に (p[i], s[i]) を挿入します。
3. ret := n として初期化します。
4. 配列 v を位置の昇順にソートします。
5. double型のスタック st を定義します。
6. i を 0 ～ n-1 の範囲で再度ループします。
   • temp := (t − v[i].first) / v[i].second を計算します。これは現在の車が目的地に到達するまでの時間です。
   • st が空でなく、かつスタックトップ ≤ temp の間、次を繰り返します。
     • ret を 1 減らす（後続の車が前方の車に追いつき、フリートに合流したことを意味します）。
     • スタックの先頭要素を削除します。
   • temp を st にプッシュします。
7. 最後に ret を返します。

ポイントは、目的地から遠い車から順に処理することです。現在処理している車の到達時間が、スタック内のより前方の車の到達時間以上であれば、その車は目的地に到達する前に（または到達時に）前方の車に追いつくため、両者は1つのフリートにまとめられます。

C++実装例

理解を深めるために、以下の実装をご覧ください。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int carFleet(int t, vector<int>& p, vector<int>& s) {
        vector < pair <double, double> > v;
        int n = p.size();
        for(int i = 0; i < n; i++){
            v.push_back({p[i], s[i]});
        }
        int ret = n;
        sort(v.begin(), v.end());
        stack <double> st;
        for(int i = 0; i < n; i++){
            double temp = (t - v[i].first) / v[i].second;
            while(!st.empty() && st.top() <= temp){
                ret--;
                st.pop();
            }
            st.push(temp);
        }
        return ret;
    }
};
main(){
    vector<int> v1 = {10, 8, 0, 5, 3};
    vector<int> v2 = {2,4,1,1,3};
    Solution ob;
    cout << (ob.carFleet(12, v1, v2));
}

入力

12
[10,8,0,5,3]
[2,4,1,1,3]

出力

3

計算量について

ソートに O(n log n)、スタック操作全体で各要素は高々1回のプッシュとポップしか行われないため O(n) の計算量となります。全体の時間計算量は O(n log n)、空間計算量は O(n) であり、非常に効率的な解法と言えます。