AtCoder 캐디 프로그래밍 대회 2021 ABC 193 개인 노트

감상

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\leqa\leqlceil\sqrt{N}\rceil 범위 내에서 모두 검색하면 k
b는 a=2에서도 2^{34}\geq10^{10}이 되므로 O(\sqrt{N})
따라서\bf2^6=8^2=64의 경우 계수를 중복하지 않기 위해서는\bfa^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

다음 두 가지 이유에 따라 뒷면 카드의 조합으로 전체 탐색을 하는 것이 좋다

후면 카드의 조합은 최대 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)