ABC376をPythonで（A～E）

AtCoder Beginner Contest 376（Promotion of AtCoder Career Design DAY）の解答等の速報的まとめ

https://atcoder.jp/contests/abc376



# A問題
https://atcoder.jp/contests/abc376/tasks/abc376_a

最後にもらってからの時間を計算する
時間が十分に経っていたら$+1$

```python:A
n, c = map(int, input().split())
t = list(map(int, input().split()))

last = -10000
ans = 0
for t_i in t:
    if t_i - last >= c:
        ans += 1
        last = t_i

print(ans)
```


# B問題
https://atcoder.jp/contests/abc376/tasks/abc376_b

現在地と目的地が一緒ならばそのまま
そうでないなら実際に動かして試す
（コードは改良の余地あり）
```python:B
def move(now, to, arr, other):
    res = 0
    while True:
        res += 1
        now += arr
        if now == n + 1:
            now = 1
        if now == 0:
            now = n

        if now == to:
            return res
        if now == other:
            return -1


n, q = map(int, input().split())

ans = 0
l, r = 1, 2
for _ in range(q):
    h, t_ = input().split()
    t = int(t_)
    if h == "R":
        if r == t:
            continue
        d_i = move(r, t, 1, l)
        if d_i >= 0:
            ans += d_i
        else:
            d_j = move(r, t, -1, l)
            ans += d_j
        r = t
    else:
        if l == t:
            continue
        d_i = move(l, t, 1, r)
        if d_i >= 0:
            ans += d_i
        else:
            d_j = move(l, t, -1, r)
            ans += d_j
        l = t

print(ans)
```

# C問題
https://atcoder.jp/contests/abc376/tasks/abc376_c

大きいほうから見て行って入らないおもちゃが１つだけあったらそれが答え
```python:C
n = int(input())
a = sorted(map(int, input().split()), reverse=True)
b = sorted(map(int, input().split()), reverse=True)

ans = 0
j = 0
for i, a_i in enumerate(a):
    if j >= len(b):
        ans = a_i if i == j else -1
    elif a_i <= b[j]:
        j += 1
    elif i == j:
        ans = a_i
    else:
        exit(print(-1))

print(ans)
```

# D問題
https://atcoder.jp/contests/abc376/tasks/abc376_d

bfsをしてスタート地点に戻ってくる最短距離を出力
```python:D
from collections import deque

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(lambda x:int(x) - 1, input().split())
    edge[u].append(v)

INF = float("inf")
dist = [INF] * n
q = deque()
q.append(0)
while q:
    now = q.popleft()
    if now == 0:
        d = 1
    else:
        d = dist[now] + 1
    for to in edge[now]:
        if dist[to] > d:
            dist[to] = d
            q.append(to)

print(-1 if dist[0] >= INF else dist[0])
```

# E問題
https://atcoder.jp/contests/abc376/tasks/abc376_e

$a$が小さいほうから見ていく。
$a$を固定して$b$の$k$個の総和が最小になるように要素を取捨選択する

（ひらめくのに時間がかかりすぎて実装完了したのが終了3分後だった）
```python:E
from heapq import heappop, heappush
from sortedcontainers import SortedList


for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    data = [(a_i, b_i) for a_i, b_i in zip(a, b)]
    data.sort()
    lst = []
    max_a = SortedList([])
    sum_b = 0
    ans = float("inf")

    for a_i, b_i in data:
        sum_b += b_i
        max_a.add(a_i)
        heappush(lst, (-b_i, -a_i))
        if len(lst) > k:
            x = heappop(lst)
            sum_b += x[0]
            max_a.discard(-x[1])

        if len(lst) == k:
            ans = min(ans, max_a[-1] * sum_b)
    print(ans)

```