AtCoder キャディプログラミングコンテスト2021 ABC193 個人的メモ

所感

abd3完
cは終了27秒後にacした
悲しい
と思ったけど予想してたほど冷えなかった

A - Discount

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

print(100 - A / B * 100)

B - Play Snuke

$(0.5分おきに在庫が1減る)=(1分おきに在庫が1減る)$
と考えれば楽

N = int(input())
INF = 10 ** 18
ans = INF
for _ in range(N):
    a, p, x = map(int, input().split())
    x -= a
    if x >= 1:
        ans = min(ans, p)

if ans == INF:
    print(-1)
else:
    print(ans)

C - Unexpressed

$a^b$を重複して数えている事に気づかなかった

$a,b$は$2$以上なので，$2\leqq a\leqq\lceil\sqrt{N}\rceil$の範囲で全探索すればおｋ
$b$は$a=2$の時でも$2^{34}\geqq 10^{10}$となるので$O(\sqrt{N})$
で，$\bf 2^6=8^2=64$というような時に重複して数えない様に$\bf a^b$の計算結果をメモしておく必要がある

N = int(input())

ans = N
seen = set()
for i in range(2, int(N ** 0.5) + 1):
    for j in range(2, N):
        cal = i ** j
        if cal > N:
            break
        if cal in seen:
            continue
        seen.add(cal)
        ans -= 1

print(ans)

D - Poker

以下の2つの理由より，裏向きのカードの組み合わせで全探索すれば良さそう

• 裏向きのカードの組み合わせは最大で$9\times 9$通りしかない
• 高橋君と青木君の得点は$O(10)で計算できる$

よって，全体の計算量は$O(10^3)$ぐらいになりそう

$(高橋君が勝つ場合)/(全ての場合)$を求める
各組み合わせで以下の処理を行う

• 裏向きのカードを含む全てのカード個数が$K$以下か確認
• 場合の数を計算し，分母に加算
• 高橋君が勝つなら，分子にも場合の数を加算

from collections import Counter

K = int(input())
S = Counter(input())
T = Counter(input())

win = 0
denominator = 0
for i in range(1, 10):
    i = str(i)
    for j in range(1, 10):
        j = str(j)
        # カードの枚数がK以下かを確認
        cnt = Counter()
        if i == j:
            cnt[i] += S[i] + T[i] + 2
        else:
            cnt[i] += S[i] + T[i] + 1
            cnt[j] += S[j] + T[j] + 1
        if any(x > K for x in cnt.values()):
            continue

        # 場合の数を計算
        if i == j:
            res = (K - (S[i] + T[i]))
            num_of_cases = res * (res - 1)
        else:
            num_of_cases = (K - (S[i] + T[i])) * (K - (S[j] + T[j]))
        denominator += num_of_cases

        # 高橋君の得点を計算
        lst_t = Counter(S)
        lst_t[i] += 1
        takahashi = sum(n * 10 ** lst_t[str(n)] for n in range(1, 10))

        # 青木君の得点を計算
        lst_a = Counter(T)
        lst_a[j] += 1
        aoki = sum(m * 10 ** lst_a[str(m)] for m in range(1, 10))

        if takahashi > aoki:
            win += num_of_cases

print(win / denominator)