Car Fleet
車は1車線の道路を通り、マイル標識targetに向かって進みます。車iはマイル標識position[i]から出発し、時速speed[i]マイルで走ります。車はほかの車を追い越せません。遅い車に追いついた車はそのすぐ後ろにとどまり、それ以降は2台が1つの車列となって、遅いほうの速度で一緒に進みます。
1台の車も車列とみなされ、目的地にちょうど到着した時点で車列に追いついた車は、その車列に加わります。目的地に到着する車列の数を返してください。
関数
- targetinteger
- すべての車が向かっているマイル
- positioninteger-array
- 各車の出発時の走行距離
- speedinteger-array
- 各車の速度（マイル毎時）
- 戻り値integer
- 目的地に到着する艦隊の数
制約
n == position.length == speed.length1 ≤ n ≤ 1041 ≤ target ≤ 1060 ≤ position[i] < target1 ≤ speed[i] ≤ 106- すべての位置は異なります。
例
- 入力
- target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
- 出力
- 2
- 説明
- 単独では、マイル地点17、14、8、2にいる車はそれぞれ3時間、2時間、3時間、3時間必要なので、14の車が17の車に追いつき、残りの2台はマイル地点20で合流します。0地点の車は10時間必要で、単独で到着します。
- 入力
- target = 9position = [0, 4, 7]speed = [1, 2, 3]
- 出力
- 3
- 説明
- 7、4、0マイル地点にいる車は、それぞれ2/3時間、5/2時間、9時間必要です。どの車も前の車より後に到着するため、誰も追いつきません：
3つの隊列。
- 入力
- target = 10position = [3]speed = [5]
- 出力
- 1
- 説明
- 道路上の車1台が1つの車両群です。
発展問題
各位置はtarget未満の整数です。比較ソートを使わずに、O(n + target)時間で車隊の数を数えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
車の順序が変わることはありません。各車について、道路が空いていた場合に目的地へ到着する時刻を計算してください。前の車に追いつくかどうかを決めるのは何でしょうか？
目的地に最も近い車から始めて、後ろに向かって進みます。ある車の到着時刻が前方のフリートより遅くない場合、そのフリートに加わります。そうでなければ、新しいフリートを作ります。
位置で並べ替え、最大のものを先頭にし、艦隊は最新のものが一番上になるようスタックに保持します。時間
d1/s1とd2/s2を、64ビット整数でd1 × s2とd2 × s1として比較します。
解説
1車線では車の順序は決して変わらず、すべてを決めるのは各車が単独で到着する時間です：(target - position[i]) / speed[i]。目的地に最も近い車から逆順に確認します。車が前方の隊列より厳密に遅く到着する場合にのみ、新しい隊列を作ります。
前方の車をすべて確認する
正しいが、最大のテストでは終わらない
考え方
ある車が車列を先導するのは、その前方にいるすべての車が単独なら厳密に早く到着する場合です。前方の車のうち到着が同時か遅いものがあれば、目的地までに自分の車はその車、またはその車列に追いつきます。すべてが早く到着するなら、前方に自分の車を妨げるものはありません。車列は、車列内の車が単独で到着する時刻のうち最も遅い時刻に到着するためです。先頭の車の台数を数え、交差乗算で時刻を正確に比較します。
各車は n 台すべてを調べます。n = 10^4 の場合、チェック回数は 10^8 です。
アルゴリズム
fleets = 0に設定します。- 各車
iについて、position[j] > position[i]を満たすすべての車jを確認します。 - ある
jが(target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j]を満たす場合、車iは追いつかれるため、スキップします。 - それ以外の場合、車
iはフリートの先頭になります。fleetsに 1 を加えます。 fleetsを返します。
def carFleet(target, position, speed):
n = len(position)
fleets = 0
for i in range(n):
dist = target - position[i]
caught = False
for j in range(n):
# Car j is ahead and would not arrive before car i: car i catches it.
# (target - position[j]) / speed[j] >= dist / speed[i], without division.
if position[j] > position[i] and (target - position[j]) * speed[i] >= dist * speed[j]:
caught = True
break
if not caught:
fleets += 1
return fleets位置順に並べて艦隊を積み重ねる
考え方
目的地に近い順に並べると、現在の車より前方にいる車は、すでに確認済みで、すでに隊列に属している車だけです。各隊列の先頭車の距離と速度をスタックに保持します。先頭車が隊列の到着時刻を決めます。
重要なのはスタックの一番上だけです。追加する車の到着時刻は、下にある隊列より必ず遅くなるため、時刻は下から上へと増加します。一番上より遅ければ、前方のすべての車より遅いことになります。
例1の順序では、車は17、14、8、2、0の位置にあり、距離を速度で割った値は3/1, 6/3, 12/4, 18/6, 20/2です。(3, 1)を追加します。14の位置の車は合流します。6 × 1 > 3 × 3は偽だからです。8の位置の車は同着となり、12 × 1 = 3 × 4となるため合流します。2の位置の車も同様に合流します。0の位置の車では、20 × 1 > 3 × 2となるため、追加します。
アルゴリズム
- 車のインデックスを位置の大きい順に並べ替えます。
- 空の車群のスタックから始めます。
- 各車について、
dist = target - position[i]を計算します。 - スタックが空の場合、または
dist × topSpeed > topDist × speed[i]の場合は、(dist, speed[i])をプッシュします。そうでなければ、その車は一番上の車群に加わります。 - スタックのサイズを返します。
def carFleet(target, position, speed):
# Visit the cars from the one closest to the target backward.
order = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
# One entry per fleet: (distance, speed) of the car at its front, which sets its arrival time.
stack = []
for i in order:
dist, spd = target - position[i], speed[i]
# dist / spd > top_dist / top_spd, compared without division:
# this car arrives after the fleet ahead, so it never catches it.
if not stack or dist * stack[-1][1] > stack[-1][0] * spd:
stack.append((dist, spd))
return len(stack)
落とし穴と境界ケース
- 到着時刻が同じ車を新しい車両群として数える。例1の位置8と2の車は、位置20で車両群に合流する。時刻が厳密に遅い場合にのみ追加する。
- 外積のオーバーフロー。
10^6 × 10^6 = 10^12は32ビットに収まらないため、Java、C、C++、C#、Rustでは乗算の前に64ビットに拡張し、Rでは倍精度浮動小数点数を使う。 - 逆方向にソートする。目的地から最も遠い車から始めると、各車を後ろにいる車と比較することになり、その車を妨げることはできない。
positionだけをソートする。インデックス、または（位置、速度）のペアをソートして、各速度がその車と対応したままになるようにする。
よくある質問3
Car Fleet の時間計算量は何ですか？
位置でソートする処理には O(n log n) かかり、スタックを使った走査には O(n) かかるため、合計で時間計算量は O(n log n)、メモリ計算量は O(n) です。各車を前方にいるすべての車と比較すると O(n²) かかります。
Car Fleet でスタックを使うのはなぜですか？
浮動小数点数を使わずに到着時刻を比較するにはどうすればよいですか？
到着時刻はdist / speedです。速度は正なので、d1 / s1 > d2 / s2が成り立つのは、ちょうどd1 × s2 > d2 × s1が成り立つときです。両辺は最大で10^12の整数なので、64ビット型で計算すれば比較は正確で、丸めについて考える必要はありません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def carFleet(target, position, speed):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
target = 20 position = [14, 2, 8, 17, 0] speed = [3, 6, 4, 1, 2]
期待される出力
2