スパークリング黒ココア/ABC204まとめ

Created Sun, 17 Sep 2023 Modified Tue, 26 Sep 2023 09:13:30 +0000
599 Words
ABC ABC204

A - Rock-paper-scissors

https://atcoder.jp/contests/abc204/tasks/abc204_a

  • たまに問われる #じゃんけん の話
  • 3人あいこ
    • xとyが一緒？→zも一緒
    • xとyが違う？→zも違う
  • 全体の合計から求め方が中々渋い気がするのですが…。
    • 3人の手が違う時：
      • 0と1と2を合わせたら3になる
        • →3からxとy引いたらzの手がわかる！
    • 3人の手が同じ時：
      • 0+0+0も1+1+1も2+2+2も、3の倍数
        • →mod…3…？
  • なんか、うまく、表現、できない…
    • とりあえずAだし、素直に場合分けして飛ばしそう
x, y = map(int, input().split())  
if x == y:  
    print(x)  
else:  
    print(3 - (x + y))

 B - Nuts

https://atcoder.jp/contests/abc204/tasks/abc204_b

  • 木を1本ずつ見て行って、収穫できる数を数えていったら終わり！
N = int(input())  
A_L = list(map(int, input().split()))  
ans = 0  
for a in A_L:  
    if a > 10:  
        ans += a - 10  
print(ans)

C - Tour

https://atcoder.jp/contests/abc204/tasks/abc204_c

  • #BFS するだけ問題
    • $O(N+M)$で、「1つの頂点から、到達可能な都市」が出てくるので。
    • 全頂点から確認してあげればOK
from collections import deque  
  
N, M = map(int, input().split())  
edge_L = [[] for i in range(N)]  
  
for i in range(M):  
    A, B = map(int, input().split())  
  
    A -= 1  
    B -= 1  
    edge_L[A].append(B)  
  
  
def bfs(s):  
    que = deque([s])  
    is_checked = [False] * N  
    is_checked[s] = True  
  
    while que:  
        now = que.popleft()  
        for nex in edge_L[now]:  
            if is_checked[nex]: continue  
            is_checked[nex] = True  
            que.append(nex)  
  
    return is_checked.count(True)  
  
  
ans = 0  
for i in range(N):  
    ans += bfs(i)  
print(ans)

D - Cooking

https://atcoder.jp/contests/abc204/tasks/abc204_d

  • ぱっと見 #にぶたん したくなる顔してる…（ミスリード）
  • N個の商品のうち、a個をオーブン1号で。残りの(N-a)個を、オーブン2号で焼く話
    • 商品は絶対オーブン1号かオーブン2号で焼かなければいけない…
    • i個目の商品を、オーブン1号で焼く/オーブン2号で焼く、の #ナップザックDP っぽいやつ
N = int(input())
T_L = list(map(int, input().split()))

prev_dp = set()
prev_dp.add((0, 0))

for t in T_L:
    next_dp = set()

    for a, b in prev_dp:
        next_dp.add((a + t, b))
        next_dp.add((a, b + t))
    prev_dp = next_dp

ans = 10 ** 18
for a, b in prev_dp:
    ans = min(ans, max(a, b))
print(ans)