⛳

【ABC265】AtCoder Beginner Contest 265 A-D メモ【python】

2022/08/22に公開

Python

AtCoder

tech

https://atcoder.jp/contests/abc265

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のリストの数だけ繰り返しているため、全体の計算量が $O(N^2)$ となる。 $n$ が2<=N<10 ^5 と 1≤A_i≤10^9であるため $O(N^2)$ だと計算時間内に終わらないためTLEになる。pythonにおけるリスト周りの計算量はこちらの記事がとても参考になる。

解法1

ボーナス部屋のリストを作成する。部屋 $i$ がボーナス部屋の場合、 $M[i]$ にボーナス $Y_i$ を入れる。このときリストの長さをMとし、ボーナス部屋ではない場所には0を入れる。
この処理は事前にできるため、計算量はO(n)+O(n)→O(n)となる。そのため規定の計算時間に間に合う。

pythonの解法例 (公式解法)

解法2

ボーナス部屋のリストを $bornus[i][j]$ で作成する。 $i$ がボーナス部屋の番号で $j$ が持ち時間が増えるボーナスの値である (XとYをそのままリストに入れるだけ)。条件より、ボーナス部屋の番号が重複することがないため、部屋の番号で2次元配列をソートすれば順番にボーナス部屋の判定と待ち時間の追加を行える。この処理も事前に行えるため、計算量は $O(n \log n) + O(n)$ → $O(n \log n)$ となる。そのため規定の計算時間に間に合う。

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

ベルトコンベアー部分の実装は難しくはない。注意する部分は $x[-1]$ を呼び出さない点と配列のインデックスを超えた値( $x[len(x)+1]$ )を呼び出さない点である。
この問題の要は無限に移動し続けるパターンを発見し、-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")