2019-06-14に投稿

# AtCoder Beginner Contest 123CをPythonで解く

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!!

🐍でけたで!

Originally published at www.coderecipe.org

view_list Pythonで競プロ
第9回 AtCoder Beginner Contest 090BをPythonで解く
第10回 AtCoder Beginner Contest 129DをPythonで解く
第11回 AtCoder Beginner Contest 122cをPythonで解く
第12回 AtCoder Beginner Contest 063bをPythonで解く
第13回 # AtCoder Beginner Contest 123CをPythonで解く

aocory

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

関連記事

コメント