abc194

NISHIO Hirokazu [Translate]
ABC194
5問でした。Fは桁DPでしょ、と実装したが「16通りの数字が既に出てるかどうかを記録」で6万になり、Nが2×10^5だから厳しいよな…TLEが解決せずコンテスト終了


C - Squared Error
一度間違えて\sum\sum A_iA_j [i<j]を求めてしまい、サンプルが全然合わなくて気づいた
今回の問題は \sum\sum (A_i-A_j)^2 [j < i]
図形的に解釈しようとしてうまくいかなかったので落ち着いて素朴に式変形
\sum\sum (A_i-A_j)^2 [j < i] 
= \frac{1}{2} \sum\sum (A_i-A_j)^2 ... 行列の半分
= \frac{1}{2} \sum\sum ( A_i^2 - 2 A_iA_j  + A_j^2 ) ... 展開
= \frac{1}{2} \left( \sum\sum  A_i^2 - 2 \sum\sum A_iA_j  + \sum\sum A_j^2 \right) ... 和の順序
= \frac{1}{2} \left( 2N \sum A_i^2 - 2 \sum\sum A_iA_j \right) 
= N \sum A_i^2 -  \sum\sum A_iA_j 
= N \sum A_i^2 -  (\sum A_i)^2 
pydef main():
    N = int(input())
    AS = list(map(int, input().split()))
    sumAS = sum(AS)
    sumSq = sum(a * a for a in AS)
    print(N * sumSq - sumAS * sumAS)

D - Journey
期待値DP DP J
f(x)を連結成分のサイズがxの状態からNになるまでの操作の回数の期待値とする。f(N) = 0。f(1)を求めたい
f(x)が与えられたとしてf(x-1)を求める
連結成分のサイズがx-1の状態から1ステップ後を考える
(x-1) / N の確率で既に連結してる頂点が選ばれて、残りの期待値はf(x-1)
(N - (x-1)) / Nの確率で新しい頂点が選ばれて、残りの期待値はf(x)
f(x-1) - 1 = \frac{x-1}{N} f(x-1) + \frac{N-(x-1)}{N} f(x) 
\frac{N - (x-1)}{N} f(x-1)   =  \frac{N-(x-1)}{N} f(x) + 1 
 f(x-1)   = \left( \frac{N-(x-1)}{N} f(x) + 1\right) \frac{N }{N - (x-1)} 
ここまで変形してコードに落とした
pydef main():
    N = int(input())
    ret = 0
    for i in range(1, N):
        ret = (ret * (N - i) / N + 1) * N / (N - i)
    print(ret)
公式解説
 f(x-1)   = \left( \frac{N-(x-1)}{N} f(x) + 1\right) \frac{N }{N - (x-1)} をもう一歩整理すると
 f(x-1)   = f(x) +  \frac{N }{N - (x-1)} になる

E - Mex Min
考えたこと
M個の並びの中に出現しない最小の数を見つけたい
だけど素朴にループすると10^6回10^6の長さの列をチェックするので間に合うはずがない
頻度表を作れば、1箇所増やして1箇所減らすだけなので定数オーダーで何が何個あるかはわかる
出現しない最小の数は、頻度表で0になる最も左の数。これをループで探したらやっぱり間に合わない
特定の値である最も左のものを見つけるといえばフェニック木
頻度表が0である時にフェニック木の対応する位置が1になるようにする。最も左にある1は二分探索で求められて対数オーダー
これは自前ライブラリで実装済み
pydef main():
    N, M = map(int, input().split())
    AS = list(map(int, input().split()))
    ft = FenwickTree(N)
    for i in range(N):
        ft.set(i, 1)
    count = [0] * N
    ret = INF = 9223372036854775807
    for i in range(M):
        v = AS[i]
        count[v] += 1
        ft.set(v, 0)
    ret = ft.find_next(-1)
    for i in range(M, N):
        v = AS[i]
        count[v] += 1
        ft.set(v, 0)
        v = AS[i - M]
        count[v] -= 1
        if count[v] == 0:
            ft.set(v, 1)
        ret = min(ret, ft.find_next(-1))

    print(ret)

ABC194F

AtCoder202103