Pythonで解く：パルクール選手が到達できる最も遠い建物を求めるアルゴリズム

問題の概要

さまざまな高さの n 棟の建物が一列に並んでおり、パルクール選手がレンガとはしごを使って隣の建物へ移動していく状況を考えてみましょう。各建物の高さは配列として与えられます。レンガ1枚の高さは1単位で、手持ちの枚数も決まっています。レンガとはしごはそれぞれ1回しか使用できません。このとき、パルクール選手が到達できる最も遠い建物のインデックスを求めるのが課題です。

例として、次の入力を見てみましょう。

• heights = [5, 8, 7, 6, 2, 3, 1, 4]
• bricks（レンガ） = 3
• ladders（はしご） = 2

この場合の出力は 7 となります。

移動の手順

• 選手はまず建物 0 からスタートします。
• レンガ3枚を使って、より高い建物 1 へ移動します。
• 建物 2・3・4 は前の建物よりも低いため、レンガやはしごを使わずにジャンプで進めます。
• 建物 4 から 5 へは、はしごを1本使って登ります。
• 建物 6 は建物 5 より低いので、ジャンプで移動できます。
• 最後のはしごを使って、建物 7 に到達します。

解き方のアプローチ

この問題は、優先度付きキュー（ヒープ）を使うことで効率的に解けます。基本的な考え方は「小さな上り坂にはレンガを使い、レンガが足りなくなった時点で、これまで消費した中で最大の差分をはしごに置き換える」というものです。

• 空のヒープ temp を用意する。
• i を 1 から heights のサイズまで繰り返す。
  • dist := heights[i] − heights[i−1]（隣接する建物の高さの差）を計算する。
  • dist > 0 の場合（次の建物が高い場合）：
    • bricks から dist を引く。
    • -dist をヒープ temp にプッシュする。
    • bricks < 0 になった場合：
      • ladders を1減らす。
      • ヒープ temp の先頭（最小値＝これまでの最大の差分）を取り出し、bricks に戻す。
      • それでも bricks < 0 または ladders < 0 の場合は、i − 1 を返す。
• ループが完了すれば、heights のサイズ − 1 を返す。

実装例

以下のPythonコードで実際の動作を確認してみましょう。

from heapq import heappush, heappop

def solve(heights, bricks, ladders):
   temp = []
   for i in range(1, len(heights)):
      dist = heights[i] - heights[i - 1]
      if dist > 0:
         bricks -= dist
         heappush(temp, -dist)
         if bricks < 0:
            ladders -= 1
            bricks -= heappop(temp)
            if bricks < 0 or ladders < 0:
               return i - 1
   return len(heights) - 1

print(solve([5, 8, 7, 6, 2, 3, 1, 4], 3, 2))

入力

[5, 8, 7, 6, 2, 3, 1, 4], 3, 2

出力

7

まとめ

このアルゴリズムでは、各移動を1回ずつ処理し、ヒープ操作のコストは O(log n) であるため、全体の計算量は O(n log n) となります。レンガの使いすぎをはしごで効率的に「巻き戻す」ことで、常に最適な資源配分を実現できるのがポイントです。