着く時刻を前から比べて一本道でゴールに着く自転車の群れを数える

追い越しのできない一本道を走る自転車が、ゴールにいくつの群れで着くかを数えます。ゴールに近い順に並べ、前の群れより遅く着く自転車だけが新しい群れになる、と見抜く練習です。

海外で定番の問題リスト 4 本には入っていません

問題

追い越しのできない一本道で、自転車が同じ向きに走っています。ゴールはスタートから target メートルの所です。i 番目の自転車は、いま position[i] メートルの所にいて、毎秒 speed[i] メートルで走ります。

速い自転車が前の自転車に追いつくと、追い越さずに後ろについて、前の自転車と同じ速さで一緒に走ります。一緒に走る自転車の組を 1 つの群れと呼びます (1 台だけでも群れです)。ゴールにいくつの群れが着くかを返す関数を書いてください。

ちょうどゴールの地点で追いついたときも、同じ群れとして数えます
position と speed の長さは同じで、1 以上 100000 以下です
position[i] は 0 以上 target 未満で、同じ位置の自転車はいません。target は 1 以上 1000000 以下です
speed[i] は 1 以上 1000000 以下です

入力と出力の例

例 1

ゴールに近い順に、14 の自転車は 6 秒、8 の自転車は 3 秒、6 の自転車は 14 秒、2 の自転車は 6 秒で着く速さです。8 の自転車は 14 の自転車に追いつき、2 の自転車は 6 の自転車に追いつきます。群れは 2 つです。

target = 20 position = [2, 8, 14, 6] speed = [3, 4, 1, 1]

例 2

1 台だけでも 1 つの群れです。

target = 10 position = [3] speed = [5]

例 3

どちらも 5 秒でゴールに着く速さです。後ろの自転車は、ちょうどゴールで追いつくので、同じ群れです。

target = 10 position = [0, 5] speed = [2, 1]

面接での聞かれ方

面接では、車の言葉で渡されることがよくあります。

「同じ道を走る車が、目的地にいくつの集団で着くかを数えてください」
「ちょうど目的地で追いついたら、同じ集団ですか？」と、境目を自分から確かめるかを見られます
書き終えたあとに「着く時刻を小数で比べて大丈夫ですか？」と聞かれることもあります

追いつく時刻を自転車の組ごとに計算し始めると、組の数だけ手間がかかって迷います。「前にいる群れより先には着けない」に気づくと、1 本の並びをなめるだけになります。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「スタックとキュー」に、この型の要点を表とコードでまとめています。

スタックは後から入れた物を先に、キューは先に入れた物を先に取り出します。括弧の対応や、順番待ちの処理の形です。

まず考える手順

段 1

自転車ごとに、ほかの自転車がいなかったときにゴールに着く時刻を出します。残りの距離を速さで割った値です。追い越しができないので、後ろの自転車がゴールに着くのは、前の群れより早くはなりません。

段 2

ゴールに近い自転車から順に見ます。いちばん前の自転車は、誰にも邪魔されずに着くので 1 つ目の群れです。次の自転車の着く時刻が、前の群れの着く時刻以下なら、ゴールまでに (またはちょうどゴールで) 追いついて同じ群れになります。前の群れより遅ければ、追いつけないので新しい群れになり、この自転車の時刻が新しい群れの時刻です。

段 3

この見方は、群れの時刻をスタックに積む書き方とも言えます。新しい群れができたら時刻を積み、追いつく自転車は積みません。最後にスタックに積まれた数が答えです。ただ、比べるのはいつもいちばん上の 1 つだけなので、群れの数と最後の群れの時刻の 2 つを持てば足ります。

段 4

時刻は割り算なので小数になります。小数で比べると、例 3 のようにちょうど同じ時刻のとき、言語によって誤差で大小が入れ替わるおそれがあります。そこで、d1 ÷ s1 と d2 ÷ s2 の大小を、両辺に s1 と s2 を掛けた d1 × s2 と d2 × s1 の整数で比べます。積は多くて 1 兆ほどで、整数で正確に扱えます。

解答

Python

def count_fleets(
    target, position, speed
):
    cars = sorted(
        zip(position, speed),
        reverse=True,
    )
    fleets = 0
    fd, fs = 0, 1
    for p, s in cars:
        d = target - p
        if d * fs > fd * s:
            fleets += 1
            fd, fs = d, s
    return fleets

JavaScript

function countFleets(
  target,
  position,
  speed
) {
  const cars = position.map(
    (p, i) => [p, speed[i]]
  );
  cars.sort(
    (a, b) => b[0] - a[0]
  );
  let fleets = 0;
  let fd = 0;
  let fs = 1;
  for (const [p, s] of cars) {
    const d = target - p;
    if (d * fs > fd * s) {
      fleets++;
      fd = d;
      fs = s;
    }
  }
  return fleets;
}

Go

import "sort"

func countFleets(
	target int,
	position []int,
	speed []int,
) int {
	n := len(position)
	idx := make([]int, n)
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(
		a, b int,
	) bool {
		return position[idx[a]] >
			position[idx[b]]
	})
	fleets := 0
	fd, fs := 0, 1
	for _, i := range idx {
		d := target - position[i]
		s := speed[i]
		if d*fs > fd*s {
			fleets++
			fd, fs = d, s
		}
	}
	return fleets
}

自転車を位置の大きい順 (ゴールに近い順) に並べ替えています。fd と fs は、いちばん後ろの群れの先頭の自転車の、残りの距離と速さです。群れの着く時刻は fd ÷ fs で、d ÷ s がそれより大きいかを、掛け算の d * fs > fd * s で比べています。最初は「時刻 0 の群れ」として fd を 0、fs を 1 にしておくと、いちばん前の自転車が必ず 1 つ目の群れになります。

計算量

時間は O(n log n) です。並べ替えがいちばん重く、そのあとは 1 回なめるだけです
使う記憶は O(n) です。並べ替えた組か添字の並びを持ちます
自転車の組ごとに追いつくかを調べる書き方は、組の数だけ見るので O(n²) です

よくある間違い

入力の順のまま見る。入力はゴールに近い順とは限りません。例 1 の position もばらばらです。先に位置で並べ替えます
前の自転車 1 台とだけ比べる。比べる相手は、前の群れの着く時刻です。追いついた自転車のもとの時刻と比べると、その自転車よりは遅くても前の群れには追いつく後ろの自転車を、新しい群れと数え違えます。たとえば 6 秒の群れに 3 秒の自転車が追いついたあと、4 秒の自転車は 3 秒より遅くても 6 秒の群れに追いつきます
同じ時刻を別の群れにする。例 3 のように、ちょうどゴールで追いつくのは同じ群れです。新しい群れになるのは、時刻が真に大きいときだけです
時刻を小数の割り算で比べる。多くの場合は合いますが、ちょうど同じ時刻のときに誤差で食い違うおそれがあります。掛け算に直して整数で比べます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def count_fleets(target: int, position: list[int], speed: list[int]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(count_fleets(20, [2, 8, 14, 6], [3, 4, 1, 1]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します