ABC194

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

一度間違えて $\sum\sum A_{i} A_{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_{i} A_{j} + A_{j}^{2})$ … 展開
- $= \frac{1}{2} (\sum\sum A_{i}^{2} - 2 \sum\sum A_{i} A_{j} + \sum\sum A_{j}^{2})$ … 和の順序
- $= \frac{1}{2} (2 N \sum A_{i}^{2} - 2 \sum\sum A_{i} A_{j})$
- $= N \sum A_{i}^{2} - \sum\sum A_{i} A_{j}$
- $= N \sum A_{i}^{2} - (\sum A_{i})^{2}$ py

def 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) = (\frac{N - ( x - 1 )}{N} f (x) + 1) \frac{N}{N - ( x - 1 )}$
- ここまで変形してコードに落とした py

def 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) = (\frac{N - ( x - 1 )}{N} f (x) + 1) \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は二分探索で求められて対数オーダー
  - これは自前ライブラリで実装済み py

def 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

🪴 Quartz 4.0

ABC194

Graph View

Backlinks