Pythonで旅行を開始できる出発点の数を見つけるためのプログラム

0からn-1までの番号が付けられたn個の都市があり、n個の有向道路があるとします。都市iから都市（i + 1）％n[0から1から2から....からN-1から0]に移動できます。車があります。私たちの車の燃料タンクの容量はキャップユニットです。都市iの初めに使用できる燃料[i]単位があり、車は都市iから（i + 1）％nまで移動するのにコスト[i]単位の燃料を消費します。車を始動できる都市がいくつあるかを確認する必要があります。そうすれば、すべての都市を移動して、開始した同じ都市に到達できますか？

したがって、入力がキャップ=3燃料=[3,1,2]コスト=[2,2,2]のようである場合、2つの可能な解決策があるため、出力は2になります。

• 都市0から開始し、タンクに3ユニットの燃料を充填し、2ユニットの燃料を使用して都市1に移動できます。タンクには1ユニットが残っています。都市1で1単位の燃料を摂取した後、車には2単位の燃料があり、2単位の燃料を使用して都市2に移動できます。燃料タンクは空になりました。都市2で2ガロンの燃料を補給した後、2ガロンの燃料を使用して都市0に戻ります。

• 都市2から開始して、車に2単位の燃料を充填し、都市0に移動します。次に、都市0から3ガロンの燃料を補給した後、都市1に移動し、1単位の燃料を取得します。その後、City 1で1ユニットの燃料を補給し、2ユニットの燃料を用意して、City2に移動できます。

ただし、都市1から開始することはできません。燃料は1単位しかありませんが、都市2に移動するには2ガロンが必要です。

これを解決するには、次の手順に従います-

• n：=燃料のサイズ
• req：=サイズnの配列で、0で埋めます
• 0から1の範囲のkについては、
  • n-1から0の範囲のiの場合、1ずつ減らします。
    • nexti：=（i + 1）mod n
    • req [i]：=最大0およびreq[nexti]+コスト[i]-燃料[i]
    • （req [i] +fuel [i]およびcap）の最小値-コスト[i]
    • 0を返す

例

理解を深めるために、次の実装を見てみましょう-

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