Five Transportations

1. Five Transportations

問題

AtCoder社は成長し、2028 年になってついに6つの都市 (都市1,2,3,4,5,6) からなる AtCoder 帝国を作りました！
AtCoder帝国には5つの交通機関があります。
電車：都市1から2まで1分で移動する。1つの電車にはA人まで乗ることができる。
バス：都市2から3まで1分で移動する。1つのバスには B人まで乗ることができる。
タクシー：都市3から4まで1分で移動する。1つのタクシーにはC人まで乗ることができる。
飛行機：都市4から5まで1分で移動する。1つの飛行機にはD人まで乗ることができる。
船：都市5から6までを1分で移動する。1つの船にはE人まで乗ることができる。
それぞれの交通機関は、各整数時刻 (0,1,2,3,...) に、都市から出発します。
いま、N人のグループが都市1におり、全員都市6まで移動したいです。全員が都市
6に到着するまでに最短で何分かかるでしょうか？
なお、乗り継ぎにかかる時間を考える必要はありません。

こう考えた

• 詰まるポイントのA1>A2はA1/A2の切り上げ分時間がかかる。
• Forループでそれぞれの時間を計算して追加する。

🐍これでいけんちゃうかな？入力のところは改善できるはず。

書いたコード

import math
L=[int(input()) for i in range(6)]
Step=0
min=L[0]
for i in range(5):
  if min > L[i+1]:
    Step=Step+math.ceil(min/L[i+1])
    min=L[i+1]
  else:
    Step=Step+1
print(Step)

🐍これならループも5回やしTLEにはならへんやろ。。

結果

WA！！

🐍WA！！

解説読む

最も通りにくい、つまり容量が最も小さい交通機関を考えます。直感的には、最短時間で移動する場合でも、1 分でたどり着けるのは 𝑋 人 (交通機関の容量の最小を 𝑋 とする) になります。これは、「1秒に 15 L のペースで水を送れるポンプと、1 秒に 12 L のペースで水を送れるポンプをつなげたときに、1 秒に送れる水の量は小さい方を取って 12 L」 になるのと同じ原理です。つまり、先ほどの貪欲的な方法ではなくて、1 分に 𝑋 人ずつ 1 つ先に進めてやっても、直感的には
かかる時間は変わらなさそうです。また、移動時間は 「(𝑁 ÷ 𝑋 を切り上げた値) + 4 分」 と、簡単に計算できるようになります。

🐍WA！！

解説を読んで実装したコード

import math
N=int(input())
L=[int(input()) for i in range(5)]
m=math.ceil(N/min(L))
print(m+4)

結果

AC！！

🐍でけたで！