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_iA_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_iA_j + A_j^2 )$ ... Expansion
  • $= \frac{1}{2} \left( \sum\sum A_i^2 - 2 \sum\sum A_iA_j + \sum\sum A_j^2 \right)$ ... sum order
  • $= \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)

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) = \left( \frac{N-(x-1)}{N} f(x) + 1\right) \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) = \left( \frac{N-(x-1)}{N} f(x) + 1\right) \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.