AtCoder Beginner Contest 123
今週から、コンテストで解いた問題と解説を聞いて理解できた問題を記録していきたいと思います。
今週のABC123、ABC問の三完でした。
AtCoder Beginner Contest 123 - AtCoder
A - Five Antennas
- 入力は5つのアンテナの座標と、通信できる距離kだった。
- 各アンテナが相互に直接通信できるか否かを判定する。
解法
2重for文で全てのアンテナの組み合わせに対して、距離がkより大きかったら答えをFalseにするようにした。
iとjが同じ時は比較しなくてよいが、答えに関係なかったのでそのままにした。
ソースコード(python)
# A
a = []
for i in range(5):
a.append(int(input()))
k = int(input())
ans = True
for i in range(5):
for j in range(5):
if abs(a[i] - a[j]) > k:
ans = False
if ans:
print('Yay!')
else:
print(':(')
B - Five Dishes
- 入力はA問とほぼ同じで、5つの整数入力だった。
- 各入力は料理の調理時間で、時刻10nの時にのみ注文ができるという制約があった。
- 最後の料理が届く最も早い時刻を出力する。
解法
この問題で重要なのは、調理時間ではなく、調理時間の1の位のみであることがわかる。
調理時間がXX1の料理は、料理が届いてから次の注文をするまでに9分の時間が必要である。
よって、XX1, XX2,..,XX9,XX0の順でソートして先頭の時間とその他の時間の1の位を切り上げた和を出力すればよい。
別解
よくよく考えてみると、入力が5しかないので、ソートしなくても入力値の一つをそのまま、他を切り上げ等で全探索すれば簡単に書ける。
ソースコード(python)
# B
import math
a = [[] for i in range(5)]
min_inp = 0
for i in range(5):
inp = int(input())
inp_ceil = math.ceil(inp/10)*10
first = inp - int(inp/10) * 10
if first == 0:
first = 10
a[i].append(inp)
a[i].append(inp_ceil)
a[i].append(first)
a = sorted(a, key=lambda x: x[2])
ans = a[0][0]
for i in range(4):
ans += a[i+1][1]
print(ans)
C - Five Transportations
- 入力は人数nと5つの整数値。
- 5つの整数値は目的地に着く為に利用する乗り物の定員数。
- 全ての乗り物が1分で目的地に到着する場合、全ての人が出発地から目的地に着くまでにかかる時間を出力する。
解法
この問題では、人数がどれだけ多くても、5つの交通機関のなかで定員が最も少ないものがボトルネックになり、それ以降の移動人数はその交通機関の定員となる。
簡単に書けたが、切り上げを間違えて1WA出してしまった。
ソースコード(python)
# C
import math
n = int(input())
a = []
for i in range(5):
a.append(int(input()))
ans = math.ceil((n/min(a) + 5) - 1)
print(ans)
D - Cake 123
- 1、2、3のキャンドルが付いたケーキにそれぞれ、美味しさが割り当てられている。
- 美味しさの合計が大きくなるような123のケーキの組み合わせを見つけ、美味しさの和を1~k番目まで出力する。
考えたこと
3種類のケーキの中でa,b,cの組み合わせ数が3000を超えるようにそれぞれのケーキを上からとっていけば良いと思った。
解法
a,b,cの全探索で、cのループでa,b,cの個数が3000を超えたらループを抜けるようにすれば、109程の計算をせずに解くことができる。
他にも色々な解法がある。
ソースコード(python)
# D
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans = []
for index_i, i in enumerate(a):
for index_j, j in enumerate(b):
for index_l, l in enumerate(c):
if ((index_i+1)*(index_j+1)*(index_l+1) <= k):
ans.append(i+j+l)
else:
break
ans.sort(reverse=True)
for i in range(k):
print(ans[i])
レート変化
反省
今回はAとBの入力がめんどくさかったり、難しく考えてしまったりで時間をとられてしまった。
Cはボトルネックに気づいたことで、すぐに解くことができた。
Dはとてもシンプルな解法だったので、残念だった。
次は4月13日にABC122があるので頑張りたい。
