ABC194
5問でした。Fは桁DPでしょ、と実装したが「16通りの数字が既に出てるかどうかを記録」で6万になり、Nが2×10^5だから厳しいよな…TLEが解決せずコンテスト終了
https://gyazo.com/60d03daf198fba56b1a72463113643a4
C - Squared Error
https://gyazo.com/75ae6711a0784a14cd1e2aada2b3a514
一度間違えて$ \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
code: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
https://gyazo.com/b7fb1c291a8f309086e785be3c2ceac1
期待値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)}
ここまで変形してコードに落とした
code: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) = \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
https://gyazo.com/30b4c6898261c7affd5dc6dd32589442
考えたこと
M個の並びの中に出現しない最小の数を見つけたい
だけど素朴にループすると10^6回10^6の長さの列をチェックするので間に合うはずがない
頻度表を作れば、1箇所増やして1箇所減らすだけなので定数オーダーで何が何個あるかはわかる
出現しない最小の数は、頻度表で0になる最も左の数。これをループで探したらやっぱり間に合わない
特定の値である最も左のものを見つけるといえばフェニック木
頻度表が0である時にフェニック木の対応する位置が1になるようにする。最も左にある1は二分探索で求められて対数オーダー
これは自前ライブラリで実装済み
code: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 = ASi
countv += 1
ft.set(v, 0)
ret = ft.find_next(-1)
for i in range(M, N):
v = ASi
countv += 1
ft.set(v, 0)
v = ASi - M
countv -= 1
if countv == 0:
ft.set(v, 1)
ret = min(ret, ft.find_next(-1))
print(ret)
ABC194F
AtCoder202103