AtCoder ABC 123 参戦記 - アールグレー特売所

きちんと全完できました。以下ABCDの提出コードとコメント。

A問題 (Five Antennas)

pos = [int(input()) for i in range(5)]
k = int(input())
if pos[4] - pos[0] > k: print(":(")
else: print("Yay!")

2点間の距離がkを超えるものがあるか無いかという問題です。問題の条件からアンテナAとアンテナE間の距離が最長になります。

B問題 (Five Dishes)

from math import ceil
time = [int(input()) for i in range(5)]
mod = []
for t in time:
    if t % 10 == 0: mod.append(10)
    else: mod.append(t % 10)
 
total = 0
for i in range(5):
    total += 10 * ceil(time[i]/10)
total -= (10 - min(mod))
print(total)

どんなに頑張って並び方を変えても、最後以外は1の位が0ではない場合繰り上がってしまいます。ということで最後に注文するものの時間のみ考えれば良いです。1の位が0のものに気を付けてください。

C問題 (Five Transportation)

from math import ceil
N = int(input())
cap = [int(input()) for i in range(5)]
maxcap = min(cap)
group = ceil(N/maxcap)
print(4 + group)

実験をすると輸送人数が最も小さいところに支配されることがわかります。輸送可能人数の最小値をminとすると、min人のグループを1分ずつずらして出発させると最適解となります。ひとつのグループが都市6に到着するのに５分、それがceil(N/min)グループあります。

D問題 (Cake 123)

import heapq
X, Y, Z, K = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
A.sort(reverse = True)
A.append(-10**20)
B.sort(reverse = True)
B.append(-10**20)
C.sort(reverse = True)
C.append(-10**20)
 
Q = []
heapq.heapify(Q)
heapq.heappush(Q, (-(A[0]+B[0]+C[0]), 0, 0, 0))
count = 0
fin = {}
while count < K:
    value, a, b, c = heapq.heappop(Q)
    if (a, b, c) not in fin:
        fin[(a, b, c)] = 1
        print(-value)
        heapq.heappush(Q, (-(A[a+1]+B[b]+C[c]), a+1, b, c))
        heapq.heappush(Q, (-(A[a]+B[b+1]+C[c]), a, b+1, c))
        heapq.heappush(Q, (-(A[a]+B[b]+C[c+1]), a, b, c+1))
        count += 1

Python3の場合N = 1000の場合でもO(N²)のアルゴリズムは避けたいところです(TLEが怖いため)。そのため優先度付きキューを使う解法にまっしぐらに突き進みました。-1倍した値をキューに突っ込むと、優先度付きキューから総和の大きい順に取り出すことが出来ます。また門番として十分に小さい負の値をA, B, Cに入れておくと、それらを使った総和がキューから取り出される前に間違いなくK回の出力が終わるため境界条件を考えなくてもよくなり処理が楽になります。

今回使った優先度付きキューの解法が理解できると、最短経路問題で用いるダイクストラ法が理解できるようになるのでおすすめです。