貪欲で最後のマスに着けるかを判定する

すごろくのマスごとに進める歩数の上限が決まっているとき、最初のマスから最後のマスに着けるかを返す。「いままでに届く最も遠いマス」を 1 つ持ち歩き、前から 1 回なめるだけで判定できます。

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

問題

すごろくのマスが一列に並び、マス i からは 1 歩以上 steps[i] 歩以下の好きな歩数だけ前へ進めます (steps[i] が 0 のマスからは進めません)。最初のマス (番号 0) から始めて、最後のマス (番号 len(steps) - 1) に着けるなら true、着けないなら false を返す関数を書いてください。

後ろへ戻ることはできません
最後のマスを越える歩数を選ぶことはできませんが、上限が大きいマスから少ない歩数を選ぶことはできます
マスが 1 つだけなら、最初から最後のマスにいるので true です
steps の長さは 1 以上 100000 以下、値はどれも 0 以上 100000 以下です

入力と出力の例

例 1

マス 0 から 1 へ進み、マス 1 から 3 歩でマス 4 へ、マス 4 から 2 歩で最後のマス 6 に着きます。途中の 0 のマスは飛び越せます。

steps = [1, 3, 0, 0, 2, 0, 1]

true

例 2

マス 0、1、2 のどこからも、マス 3 より先へは届きません。マス 3 の値は 0 なので、そこで止まります。

steps = [2, 1, 0, 0, 5]

false

例 3

マスが 1 つだけなので、最初から着いています。

steps = [0]

true

面接での聞かれ方

面接では、短い一文で渡されることが多いです。

「各要素がそこから跳べる最大の距離を表す配列があります。最後まで行けますか」
最初に動的計画法で書き、「もっと速くできますか」と聞かれて貪欲に直す流れもあります
解けたら「最少で何回跳べば着きますか」と、次の問題へ広げられることもあります

値がちょうどの歩数なのか、上限なのかで問題が変わります。書く前に確かめておきます。

ヒント

まだ開いていません

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

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

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

素直に考えると、マスごとに「着けるか」の印を持ち、着けるマスから届くマスに全部印を付けていくことになります。マスごとに最大 steps[i] 個の印を付けるので、最悪 O(n²) かかります。

段 2

マス j に着けるなら、j より手前のマスにも全部着けます。j に着く途中の跳びを短くすれば、手前のどのマスにも止まれるからです。つまり、着けるマスはいつも先頭からひと続きで、その右端「いままでに届く最も遠いマス」だけを持てば足ります。

段 3

最も遠いマス far を 0 から始め、マスを前から見ます。いま見ているマスの番号が far より大きければ、そのマスには着けないので false です。着けるなら far を i + steps[i] との大きい方に広げます。far が最後のマスに届いた時点で true を返せます。

解答

Python

def can_reach_end(steps):
    last = len(steps) - 1
    far = 0
    for i, v in enumerate(steps):
        if i > far:
            return False
        far = max(far, i + v)
        if far >= last:
            return True
    return True

JavaScript

function canReachEnd(steps) {
  const last = steps.length - 1;
  let far = 0;
  for (
    let i = 0;
    i < steps.length;
    i++
  ) {
    if (i > far) {
      return false;
    }
    far = Math.max(
      far, i + steps[i],
    );
    if (far >= last) {
      return true;
    }
  }
  return true;
}

Go

func canReachEnd(
	steps []int,
) bool {
	last := len(steps) - 1
	far := 0
	for i, v := range steps {
		if i > far {
			return false
		}
		far = max(far, i+v)
		if far >= last {
			return true
		}
	}
	return true
}

最後の return true には、実際には来ません。マスが 1 つでも、最初の回で far が 0 以上になり、そこで true を返すからです。言語が戻り値を求めるので置いています。

計算量

時間は O(n) です。マスを前から 1 回なめ、1 マスごとの手間は一定です
使う記憶は O(1) です。持つのは far と last だけです
段 1 の印を付ける書き方は O(n²) かかり、印の並びに O(n) の記憶も要ります

よくある間違い

いつも最大の歩数で跳ぶ。 [2, 4, 0, 0, 1, 0] でマス 0 から最大の 2 歩を跳ぶと、値が 0 のマス 2 で止まります。1 歩でマス 1 へ行けば、4 歩で最後のマス 5 に着けます。1 本の道を選ぶのではなく、届く範囲をまとめて持ちます
far より後ろのマスでも広げてしまう。 i > far の確かめを忘れると、例 2 でマス 4 の値 5 を使い、最後のマスに着けると答えてしまいます
最後のマスの値を気にする。最後のマスの値が 0 でも、着けば済みです。例 1 の最後のマスの値は 1 ですが、0 でも答えは変わりません
マスが 1 つのときに false を返す。 例 3 のように、最初のマスが最後のマスなので true です

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

main.py

def can_reach_end(steps: list[int]) -> bool:
    """
    Goal: 何を返すか

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

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

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


# 「実行」を押すと、この行の結果が出ます
print(can_reach_end([1, 3, 0, 0, 2, 0, 1]))

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