🌊

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

2 min read

所感

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

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,b2以上なので,2\leqq a\leqq\lceil\sqrt{N}\rceilの範囲で全探索すればおk
ba=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)