AtCoder ABC194 個人的メモ

所感

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

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_i$と$B_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$の範囲で$mex$を$O(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)