【ABC265】AtCoder Beginner Contest 265 A-D メモ【python】
A - Apple
解法1
x円を3回払ってりんごを3個買う代金(=x*3) とY円払ってりんご3個買う代金 (=y) を比較して場合分けする。
- もし、x円を3回払ってりんごを3個買う代金の方が安い場合、y円払ってりんご3個を買う必要がないので、必要個数分をx円1個のりんごで買う。
- もし、y円払ってりんごを3個買う代金の方が安い場合、このりんご3個セットをできるだけ多く買い、残った必要個数をx円1個で買う (ex: 20個の場合, y円3個セットを6セット買い、残り2個をx円で買う)
x, y, n = map(int, input().split())
if x * 3 <= y: # 全部x円1個で買う
print(n * x)
else: # 最大値までy円3個で買い、残った個数をx円1個で買う
y_count = n // 3
x_count = n % 3
print(y * y_count + x * x_count)
解法2
はじめにx円のりんごをn個買う代金を求める。次にx円のりんごの数を3つ減らし、y円のりんごのセット数を1つ増やしたときの代金を求める。この工程を繰り返した後、代金の最小値を求める。
この解法をおすすめしない理由は、解法1の計算量がO(1)であるのに対して、解法2の計算量がO(n)であるためである。今回は1 ≤ N ≤ 100
という条件があるため、計算時間内で正解できるが、Nの数が大きい場合はTLEになる可能性がある。
x, y, n = map(int, input().split())
x_n = n
y_n = 0
result_sum = 999999999999
while True:
calc_sum = x * x_n + y * y_n
result_sum = min(result_sum, calc_sum)
x_n -= 3
y_n += 1
if x_n < 0:
break
print(result_sum)
B - Explore
まずはTLEになった回答を紹介する。
n, m, t = map(int, input().split())
a = list(map(int, input().split()))
x_list = [list(map(int, input().split())) for i in range(m)]
bornas_room = [x[0] for x in x_list]
for i, value in enumerate(a):
t -= value
if t <= 0:
print("No")
exit()
if i + 2 in bornas_room:
b_i = bornas_room.index(i + 2)
t += x_list[b_i][1]
print("Yes")
この回答は一見良さそうに見えるがif i + 2 in bornas_room:
の部分で計算量O(n)があり、それをAのリストの数だけ繰り返しているため、全体の計算量が2<=N<10 ^5
と 1≤A_i≤10^9
であるため
解法1
ボーナス部屋のリストを作成する。部屋
この処理は事前にできるため、計算量はO(n)+O(n)→O(n)となる。そのため規定の計算時間に間に合う。
pythonの解法例 (公式解法)
解法2
ボーナス部屋のリストを
n, m, t = map(int, input().split())
a = list(map(int, input().split()))
x_list = [list(map(int, input().split())) for i in range(m)]
sort_x_list = sorted(x_list, reverse=False, key=lambda x: x[0])
bornus_index = 0
for i, value in enumerate(a):
t -= value
if t <= 0:
print("No")
exit()
if bornus_index < len(sort_x_list):
if i + 2 == sort_x_list[bornus_index][0]:
t += sort_x_list[bornus_index][1]
bornus_index += 1
print("Yes")
C - Belt Conveyor
ベルトコンベアー部分の実装は難しくはない。注意する部分は
この問題の要は無限に移動し続けるパターンを発見し、-1
を出力することにある。無限に移動する条件として、今までに通ったことのあるマスに再度移動することである。よって、移動履歴を作成し、今までに通ったことのあるマスがどうかを判断すれば良い。
h, w = map(int, input().split())
x = [list(map(str, input())) for i in range(h)]
pt_h = 0
pt_w = 0
exit_flag = [[False] * w for _ in range(h)]
while True:
if exit_flag[pt_h][pt_w]:
print("-1")
exit()
exit_flag[pt_h][pt_w] = True
if x[pt_h][pt_w] == "R":
pt_w += 1
if pt_w >= len(x[0]):
print(f"{pt_h+1} {pt_w}")
exit()
elif x[pt_h][pt_w] == "L":
pt_w -= 1
if pt_w <= -1:
print(f"{pt_h+1} {pt_w+2}")
exit()
elif x[pt_h][pt_w] == "D":
pt_h += 1
if pt_h >= len(x):
print(f"{pt_h} {pt_w+1}")
exit()
elif x[pt_h][pt_w] == "U":
pt_h -= 1
if pt_h <= -1:
print(f"{pt_h+2} {pt_w+1}")
exit()
D - Iroha and Haiku (New ABC Edition)
開始地点xを固定した場合、Aの数列の累積和の中にP,P+Q,P+Q+Rが含まれればOK。例えば、x=0, P=5, Q=7, R=5であれば数列に[5,7,5]
という並びがあり、累積和で求めた数列だと[5, 12(=5+7), 17(=5+7+5)]
が含まれる。このときの数列内の数字の検索はsetを用いることで計算時間を大幅に短縮できる。そして、開始地点xによる変化は累積和の条件を[A[x]+P, A[x]+P+Q, A[x]+P+Q+R]
とすることで対応可能である。
n, p, q, r = map(int, input().split())
a_list = [0] + list(map(int, input().split()))
for i in range(1, n + 1):
a_list[i] += a_list[i - 1]
a_set = set(a_list)
for a in a_list:
if a + p in a_set and a + p + q in a_set and a + p + q + r in a_set:
print("Yes")
exit()
print("No")
Discussion