Pythonで全都市を周遊できる出発地点の数を求めるプログラム

問題の概要

0からn-1までの番号が付けられたn個の都市と、n本の一方通行の道路があるとします。都市iからは必ず都市(i + 1) % nへ移動でき、全体としては「0 → 1 → 2 → ... → n-1 → 0」という環状のルートになります。ここで、燃料タンクの容量がcap単位である車を1台所有していると考えます。各都市iには到着時にfuel[i]単位の燃料を補給することができ、都市iから次の都市(i + 1) % nへ移動するにはcosts[i]単位の燃料を消費します。

このとき、「すべての都市を巡り、最終的に出発した都市へ戻ってこられる」ような出発地点となり得る都市がいくつあるかを求めるのがこの問題です。

具体例

たとえば、cap = 3、fuel = [3, 1, 2]、costs = [2, 2, 2]という入力が与えられた場合、答えは2になります。実際に2つの成功パターンが存在するからです。

• 都市0から出発する場合: まずタンクに3単位の燃料を補給し、2単位を消費して都市1へ移動します(残り1単位)。都市1で1単位を補給すれば合計2単位となり、それを使い切って都市2へ到着します。この時点でタンクは空ですが、都市2で2単位を補給すれば、2単位を消費して無事都市0へ戻れます。
• 都市2から出発する場合: 2単位の燃料を補給して都市0へ移動します。都市0で3単位を補給した後、都市1へ移動すると残り1単位です。そこでさらに1単位を補給して2単位にし、都市2へ戻ることができます。

一方、都市1からは出発できません。利用できる燃料は1単位のみですが、都市2へ移動するだけでも2単位が必要だからです。

解法のアプローチ

この問題は、各都市を出発点としたときに「追加でどれだけの燃料が必要か」を表す配列reqを計算することで解けます。手順は以下の通りです。

• n := fuel配列の長さとします。
• req := 長さnの配列を作成し、すべての要素を0で初期化します。
• 外側のループを2回回します(環状ルートのため、隣接都市の情報が一周分伝わるように2パス必要です)。
• 内側のループではiをn-1から0まで逆順に処理します。
  • nexti := (i + 1) mod n とします。
  • req[i] := max(0, req[nexti] + costs[i] - fuel[i]) と更新します。これは「都市iから旅を続けるために不足している燃料量」を意味します。
  • もし min(req[i] + fuel[i], cap) - costs[i] < req[nexti] が成立する場合は、タンク容量の制約により周遊が不可能なので、0を返します。
• 最後に、reqの中で値が0になっている要素の個数を返します。req[i]が0の都市は、追加燃料なしでそのまま旅を始められる出発地点です。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(cap, fuel, costs):
   n = len(fuel)
   req = [0] * n

   for k in range(2):
      for i in range(n-1, -1, -1):
         nexti = (i + 1) % n
         req[i] = max(0, req[nexti] + costs[i] - fuel[i])
         if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
            return 0
   return sum(1 for r in req if r == 0)

cap = 3
fuel = [3,1,2]
costs = [2,2,2]
print(solve(cap, fuel, costs))

入力

3, [3,1,2], [2,2,2]

出力

2