ABC 308 備忘録

概要

　今回はABC308（2023年7月1日21:00~22:40）のポイントと自分の実装、および感想について述べて行きたいと思う。

A問題

ポイント

• 条件に沿って場合分けをインデックス順に行い、条件を満たさなくなった瞬間に No と返してプログラムを終了させる

自分の実装

ABC_308_A.py

S = list(map(int, input().split()))

for i in range(len(S)):
    if i != 0:
        if S[i] >= S[i-1] and S[i] >= 100 and S[i] <=675 and S[i] % 25  == 0:
            continue
        else:
            print("No")
            exit()
    elif S[i] >= 100 and S[i] <=675 and S[i] % 25  == 0:
        continue
    else:
        print("No")
        exit()

print("Yes")

B問題

ポイント

• 皿の色に応じて金額をdictの辞書型配列で保持
• 辞書にない色の皿の場合はP_0を加算

自分の実装

ABC_308_B.py

N, M = map(int, input().split())

C = list(map(str, input().split()))

D = list(map(str, input().split()))

P = list(map(int, input().split()))

ans = 0

prices = {}

for i in range(M):
    prices[D[i]] = P[i+1]

for i in range(N):
    if C[i] in prices.keys():
        ans += prices[C[i]]
    else:
        ans += P[0]

print(ans)

C問題

ポイント

• 条件通りに人の番号とその人のあたりの確率を配列に保存
• float型で確率を保持すると、浮動小数の誤差で　WAとなる
• Decimal型で確率を10^(-10)未満の桁まで正確に確率を抑える

自分の実装

ABC_308_C.py

from decimal import Decimal, getcontext

N = int(input())
coins = []
for i in range(N):
    A, B = map(int, input().split())
    getcontext().prec = 20
    coin = [i, Decimal(str(A))/Decimal(str(A+B))]
    coins.append(coin)
    
coins = sorted(coins, reverse=True, key=lambda x:x[1])

print(*[coins[i][0]+1 for i in range(N)])

感想

　今回はC問題で詰まってしまった。浮動小数型の誤差問題については分かっていたが、Decimalで誤差をなくすことに関してコンテスト中には思いつかなかった。似たような問題があったら復習したい。