ABC194
5問でした。Fは桁DPでしょ、と実装したが「16通りの数字が既に出てるかどうかを記録」で6万になり、Nが2×10^5だから厳しいよな…TLEが解決せずコンテスト終了
- 一度間違えて$\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$ 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)
- 期待値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)}$
- ここまで変形してコードに落とした 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)}$ になる
- 考えたこと
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)