😽

AtCoder ABC208 個人的メモ

2 min read

所感

abc3完
score

A - Rolling Dice

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

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

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

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

B - Factorial Yen Coin

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

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個ずつ配られる。
なので、国民番号の大きさで降順にソートすればおk。
その際、国民番号と何人目の国民かを対応できるようにしておく必要がある。

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)

Discussion

ログインするとコメントできます