AtCoder ABC208 個人的メモ

所感

abc3完

A - Rolling Dice

A回サイコロを振った時、出る目の合計の最低値は$1\times A$、最大値は$6\times A$。
その間の数は全て実現可能なので、Bが最低値と最大値の間に含まれるか判定すればおｋ。

最低値を考えてなくて1wa

A, B = map(int, input().split())

if A <= B <= 6 * A:
    print("Yes")
else:
    print("No")

B - Factorial Yen Coin

貪欲法
金額の大きい硬貨をできるだけたくさん使えば良さそう。
なのでそうシミュレーションすればおｋ。

from math import factorial

P = int(input())

money = [factorial(i) for i in range(10, 0, -1)]
ans = 0
for m in money:
    while m <= P:
        P -= m
        ans += 1

print(ans)

C - Fair Candy Distribution

全員に1個ずつ配られるお菓子の数は$\lfloor \frac{K}{N}\rfloor$で求まる。
余ったお菓子$K'=K mod\ N$個は、国民番号が小さい人から1個ずつ配られる。
なので、国民番号の大きさで降順にソートすればおｋ。
その際、国民番号と何人目の国民かを対応できるようにしておく必要がある。

N, K = map(int, input().split())
A = list(map(int, input().split()))

id_and_i = [(a, i) for i, a in enumerate(A)]
id_and_i.sort()
plus_citizen = {i for _, i in id_and_i[:K % N]}

base = K // N
for i in range(N):
    if i in plus_citizen:
        print(base + 1)
    else:
        print(base)

D - Shortest Path Queries 2

解説ac
https://atcoder.jp/contests/abc208/editorial/2207

N, M = map(int, input().split())
INF = 10 ** 18
dp = [[INF] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    dp[a - 1][b - 1] = c
for i in range(N):
    dp[i][i] = 0

ans = 0
for k in range(N):
    for s in range(N):
        for t in range(N):
            dp[s][t] = min(dp[s][t], dp[s][k] + dp[k][t])
            if dp[s][t] < INF:
                ans += dp[s][t]

print(ans)