【AtCoder】ABC176の問題を初心者的書き方で解説する with Python

ここではAtCoderの問題を解説していきます。
分かりやすさ重視のため、コードの書き方も長く書いています。
そもそも自分がBeginnerなので、初心者の自分でもわかる必要最低限のスキルを使ってまとめていきたいと思います。

A問題 Takoyaki

高橋君はたこ焼きが好きです。
たこ焼き器を使うと、1度に最大で $X$ 個のたこ焼きを作ることができます。これにかかる時間は作る個数によらず $T$ 分です。
$N$ 個のたこ焼きを作るためにかかる時間の最小値を答えよ。
入力は $N\,\,X\,\,T$ の標準入力で与えられる。

具体例を考えてみましょう。
1度に10個のたこ焼きを作ることができるたこ焼き器に対して、20個のたこ焼きを焼きたい場合、2回焼けばいいことが分かると思います。
これはただ単に20÷10を計算しているだけですね。

一方、
1度に10個のたこ焼きを作ることができるたこ焼き器に対して、23個のたこ焼きを焼きたい場合、20個焼いた時点で3つ余りが出てきてしまいます。
この余りの分を焼くためにもう一度だけたこ焼き器を稼働させなければなりません。

つまりこの問題は、焼きたいたこ焼きの数 $N$ をたこ焼き器の容量 $X$ で割った時、余りがあるかないかで場合分けをする必要があります。

その後焼く回数が分かれば、あとは(焼く回数)×(1回焼くのにかかる時間)を計算すればよいです。

解答は以下の通り。

i = list(map(int, input().split())) 

N = i[0]
X = i[1]
T = i[2]
 
#焼く回数をkとします.
if N%X == 0:
    k = N/X
else:
    k = int(N/X)+1
print(int(T*k))

B問題 Multiple of 9

整数 $N$ が9の倍数であることと、 $N$ を十進法で表したときの各桁の数の和が 9の倍数であることは同値です。
$N$ が9の倍数であるか判定してください。
入力は $N$ の標準入力で与えられる。

例えば $N = 123456789$ であれば、各桁の総和が45となり、9の倍数であるため $N$ は9の倍数になります。
この問題の趣旨は、各桁の数字を計算できる形に直していくことになります。

そのため、一度 $N$ を文字列として受け取った後、大きい位から順に数字として
[1,2,3,4,5,6,7,8,9]
のようにリストに追加し、このリストの要素を全て足すことで、それが9の倍数かどうかを判定していきます。

N = input()

lists = []
for i in range(len(N)):
    lists.append(int(N[i]))
goukei = sum(lists)
if goukei%9 == 0:
    print("Yes")
else:
    print("No")

実はPythonではほかの言語とは異なり、多倍長整数という大きい桁の数でもそのまま扱うことが出来る性質があるため、
以下のコードでも倍数判定をすることが可能です。

N = int(input())

if N%9 == 0:
    print("Yes")
else:
    print("No")

C問題 Step

$N$ 人が1列に並んでおり、前から $i$ 番目の人の身長は $A_{i}$ です。
それぞれの人の足元に、高さが0以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。
条件：踏み台を込めて身長を比較したとき、自分より前に、自分より背の高い人が存在しない
この条件を満たす時の、踏み台の高さの合計の最小値を求めてください。
入力は以下の形式で標準入力から与えられる。
$N\\ A_{1},\cdots,A_{N}$

感覚としては、前から2番目の人が1番目の人より身長が高ければそのままにしておき、
2番目の人が1番目の人より身長が低ければ、
(1人目の身長)-(2人目の身長)
の差分を踏み台の高さとすることで、2人目の人は1人目の人の身長と同じ高さになります。
それを繰り返していけばいいことになります。

ここでは $i$ 番目の人よりも前にいる人の集合をBとし、 $i$ 番目以降の、これから比較する人の集合をAとしてリストにしていきます。

N = int(input())
A = list(map(int, input().split())) 
klists = []
B = [A[0]]
for i in range(N-1):
    if max(B) > A[i+1]:
        k = max(B)-A[i+1]
        klists.append(k)
        A[i+1] = A[i+1] + k
    B.append(A[i+1])
        
print(sum(klists))

しかし、このやり方でやるとTLEになってしまいます。
これはmax関数を用いたことにより、計算量が多くなってしまっているからです。
よくよく考えると、リストBの最後の要素はリストBの中で一番大きい値になっているため、max関数を使わずに表記することが可能です。

N = int(input())
A = list(map(int, input().split())) 
klists = []
B = [A[0]]
for i in range(N-1):
    if B[i] > A[i+1]:
        k = B[i]-A[i+1]
        klists.append(k)
        A[i+1] = A[i+1] + k
    B.append(A[i+1])
        
print(sum(klists))

これで計算量も抑えられ、ACすることができます。