😺

AtCoder ABC194 個人的メモ

2 min read

所感

abc3完
終了後2分10秒でeがac
悲しい
abc194_score

A - I Scream

問題文通りに実装
最初,Aが乳固形成分だと思ってたけど,サンプルのおかげで気づけた
実際はAは無脂乳固形成分で,乳固形成分はA+B

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

if A + B >= 15 and B >= 8:
    print(1)
elif A + B >= 10 and B >= 3:
    print(2)
elif A + B >= 3:
    print(3)
else:
    print(4)

B - Job Assignment

全探索
2重のforループで全てのA_iB_jの組み合わせを試す

N = int(input())
work = [list(map(int, input().split())) for _ in range(N)]

ans = 10 ** 18
for i in range(N):
    for j in range(N):
        # 異なる人を使う場合
        if i != j:
            ans = min(ans, max(work[i][0], work[j][1]))
        # 同じ人を使う場合
        else:
            ans = min(ans, sum(work[i]))

print(ans)

C - Squared Error

式変形して計算量を減らす
問題文の式通りに実装するとO(N^2)となりTLEするので,なんとかしたい
以下の様に式変形して,なんとかした

\begin{aligned} \sum_{i=2}^{N}\sum_{j=1}^{i-1} (A_i-A_j)^2 &=\sum_{i=2}^{N}\sum_{j=1}^{i-1} (A_i^2+A_j^2-2A_iA_j)\\ &=\sum_{i=2}^{N}\left\{(i-1)A_i+\sum_{j=1}^{i-1}A_j^2-2A_i\sum_{j=1}^{i-1}A_j\right\} \end{aligned}

iについて,最後の式の第1項はO(1)で,第2項と第3項は事前に累積和を計算しておけばO(1)で求められる
よって,全体でO(N)となるので大丈夫そう

from itertools import accumulate

N = int(input())
A = [0] + list(map(int, input().split()))

# Ajの累積和
cumsum = list(accumulate(A))
# Aj^2の累積和
d_cum = list(accumulate(x ** 2 for x in A))

ans = 0
for i in range(2, N + 1):
    # 第1項
    ans += A[i] ** 2 * (i - 1)
    # 第2項
    ans += d_cum[i - 1]
    # 第3項
    ans -= 2 * A[i] * cumsum[i - 1]

print(ans)

E - Mex Min

iについて,0\leqq i\leqq N-Mの範囲でmexO(1)で求められれば良さそう

forループ最後の行でindex関数を使っているので,ワーストケースでO(N^2)になって,TLEするかと思ったがacできた

from collections import Counter

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

ans = 10 ** 18
# num[i]は数字iが使用可能かを示す
num = [True] * (N + 1)
# 範囲内に出現している数字の個数を示す
cnt = Counter()
for right in range(N):
    left = right - M
    cnt[A[right]] += 1
    num[A[right]] = False

    # leftが負の場合はmexはまだ計算できない
    if right < M - 1:
        continue

    # mexを計算
    # left = 0の時は範囲が動く前のleftを削除する必要は無い
    if right > M - 1:
        cnt[A[left]] -= 1
    # cnt=0ということは,範囲内からその数字が無くなった
    if cnt[A[left]] == 0:
        num[A[left]] = True
        ans = min(ans, A[left])

    if right == M - 1 or cnt[A[right]] == 0:
        ans = min(ans, num.index(True))

print(ans)

Discussion

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