ABC194

It was 5 questions…F is the digit DP, right? and I implemented it, but “record if 16 different numbers are already available” got me to 60,000, and N is 2 x 10^5, so it’s tough…TLE didn’t solve it, contest ended…

C - Squared Error

I made a mistake once and asked for $\sum\sum A_{i} A_{j} [i < j$ ] and realized the sample didn’t match at all.
This time the problem is $\sum\sum (A_{i} - A_{j})^{2} [j < i$ ]
I tried to interpret it graphically and it didn’t work, so I calmly and naively transformed the equation
- $\sum\sum (A_{i} - A_{j})^{2} [j < i]$
- $= \frac{1}{2} \sum\sum (A_{i} - A_{j})^{2}$ … Half of the queue
- $= \frac{1}{2} \sum\sum (A_{i}^{2} - 2 A_{i} A_{j} + A_{j}^{2})$ … Expansion
- $= \frac{1}{2} (\sum\sum A_{i}^{2} - 2 \sum\sum A_{i} A_{j} + \sum\sum A_{j}^{2})$ … sum order
- $= \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 - Expected DP DP J

Let f(x) be the expected number of operations until the size of the connected component goes from x to N. f(N) = 0. We want to find f(1)
Given f(x), find f(x-1)
- Consider one step after the size of the connected component is x-1
- (x-1) / N probability that an already connected vertex is chosen and the remaining expected value is f(x-1)
- (N - (x-1)) / N probability that a new vertex is chosen and the remaining expected value is 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 )}$
- Transformed to this point and dropped into 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)

Official Explanation
- $f (x - 1) = (\frac{N - ( x - 1 )}{N} f (x) + 1) \frac{N}{N - ( x - 1 )}$ to organize one more step
- [$ f(x-1) = f(x) + \frac{N }{N - (x-1)}

E - Mex Min

Thoughts.
- I want to find the smallest number that does not appear in a sequence of m
- But a naive loop would check the sequence 10^6 times 10^6 lengths, so there’s no way to get there in time.
  - If you create a frequency table, you only need to increase one place and decrease one place, so you know what and how many are in constant order.
- The smallest number that does not appear is the leftmost number that is zero in the frequency table. If you look for this in a loop, you still won’t find it in time.
- Speaking of finding the left-most one that is a specific value Fennic tree.
  - When the frequency table is 0, the corresponding position in the phoenix tree should be 1. The leftmost 1 is obtained by a binary search and is of logarithmic order
  - This is already implemented in our own library 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

This page is auto-translated from /nishio/ABC194 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.

🪴 Quartz 4.0

ABC194

Graph View

Backlinks