AtCoder Beginner Contest 356 解題紀錄 (A - F)

🔗 AtCoder Beginner Contest 356

tags: 模擬(Simulation) 狀態壓縮 計數(Counter) 前綴和(Prefix Sum) 貢獻法 縮點 有序容器(Sorted Container)

---

A - Subsegment Reverse (abc356 A)

題意

給定正整數 $N$、$L$ 和 $R$。
對於長度為 $N$ 的序列 $A = (1, 2, \dots, N)$，進行了一次反轉第 $L$ 到第 $R$ 個元素的操作。
請輸出進行此操作後的序列。

思路：模擬(Simulation)

根據題意可以將 $A$ 分為三部分：$[1, L)$、$[L, R]$ 和 $(R, N]$。對於 $[1, L)$ 和 $(R, N]$ 部分，不需要進行任何操作，直接輸出即可；而對於 $[L, R]$ 部分，需要倒序輸出。

複雜度分析

• 時間複雜度：$O(N)$
• 空間複雜度：$O(1)$

N, L, R = map(int, input().split())
for i in range(1, L):
    print(i, end=' ')
for i in range(R, L-1, -1): # 倒序輸出
    print(i, end=' ')
for i in range(R+1, N+1):
    print(i, end=' ' if i != N else '\n')

---

B - Nutrients (abc356 B)

題意

給定一個長度為 $N$ 的整數陣列 $A$，以及一個大小為 $M \times N$ 的二維整數陣列 $X$。

其中 $A$ 表示每種營養的目標攝取量，$X$ 表示每種食物中每種營養的攝取量。

檢查是否有辦法通過食用 $M$ 種食物，達到每種營養的目標攝取量。

思路：模擬(Simulation)

根據題意模擬，直接對 $A$ 陣列進行減法操作，若最終結果中所有元素都小於等於 0，則表示可以達到目標攝取量。

複雜度分析

• 時間複雜度：$O(N \cdot M)$
• 空間複雜度：$O(N)$

N, M = map(int, input().split())
A = list(map(int, input().split()))

for _ in range(N):
    for i, x in enumerate(list(map(int, input().split()))):
        A[i] -= x

print("Yes" if all(x <= 0 for x in A) else "No")

---

C - Keys (abc356 C)

題意

給定 $N$ 把鑰匙，編號為 $1, 2, \dots, N$，其中有一些是真正的鑰匙，而其他是假鑰匙。

有一扇門，你可以將任意數量的鑰匙插入其中，但只有當至少插入了 $K$ 把真正的鑰匙時，門才會打開。

進行 $M$ 次測試，每次測試會告訴你插入了哪些鑰匙，以及門是否打開。

在 $2^N$ 種可能的組合中，找出不與任何測試結果矛盾的組合數量。

約束條件

• $1 \le K \le N \le 15$
• $1 \le M \le 100$

思路：狀態壓縮

注意到 $N \le 15$，因此總共最多只會有 $2^{15}$ 種可能的組合，因此顯然可以枚舉所有組合。

使用狀態壓縮，將每種組合表示為一個整數：

• 對於 $2^{15}$ 種可能的組合，將其狀態表示為一個整數，其中第 $i$ 個位元為 $1$ 表示第 $i$ 把鑰匙是真正的鑰匙，為 $0$ 表示第 $i$ 把鑰匙是假鑰匙
• 對於 $M$ 次測試，將其狀態表示為一個整數，其中第 $i$ 個位元為 1 表示插入了第 $i$ 把鑰匙，為 0 表示沒有插入

令 $i$ 表示當前枚舉的組合狀態、 $\text{tests}[j]$ 表示第 $j$ 次測試的狀態、$\text{results}[j]$ 表示第 $j$ 次測試的結果，則 $(i \And \text{tests}[j])$ 中 $1$ 的位元數量表示插入的鑰匙中有多少是真正的鑰匙，若 $\geq K$ 則門需要打開，否則門不打開，檢查是否與 $\text{results}[j]$ 一致即可。

複雜度分析

• 時間複雜度：$O(M \cdot C \cdot 2^N)$，其中 $C$ 為每次測試插入的鑰匙數量。
• 空間複雜度：$O(M)$，存儲 $M$ 次測試的狀態和結果。

N, M, K = map(int, input().split())

tests = []
results = []
for _ in range(M):
    c, *keys, r = input().split()
    state = 0 # 狀態壓縮
    for key in map(int, keys):
        state |= 1 << (key - 1)
    tests.append(state)
    results.append(True if r == "o" else False)

ans = 0
for i in range(1 << N): # N <= 15
    for j in range(M):
        if ((i & tests[j]).bit_count() >= K) != results[j]: # 與測試結果不符
            break
    else:
        ans += 1
print(ans)

---

D - Masked Popcount (abc356 D)

題意

給定整數 $N$ 和 $M$，計算 $\displaystyle\sum_{k=0}^{N} \rm{popcount} (k \And M)$ 的和，對 $998244353$ 取模。

其中 $\rm{popcount}(x)$ 代表 $x$ 的二進位表示中 $1$ 的個數。

思路：拆位貢獻

分別考慮每個位元的貢獻，由於要求的是 $k \And M$ 的 $\rm{popcount}$ 和，因此可以對 $M$ 的每個位元 $i$ 進行考慮。由於 $\And$ 的性質，只有 $M$ 中的第 $i$ 位為 $1$ 時，該位才會有貢獻，此時可以計算 $[0, N]$ 中第 $i$ 位為 $1$ 的數字數量，並將其加入答案中。

若 $[0, N]$ 中第 $i$ 位為 $1$ 的最大數字為 $mx$，則 $[0, N]$ 中第 $i$ 位為 $1$ 的數字數量為 $mx$ 去除第 $i$ 位後的數字數量再加 $1$。

• 舉🌰來說，若 $M$ 的第 $2$ 位為 $1$，且 $mx = 14 = 01110$，則有以下數字第 $2$ 位為 $1$：$00100, 00101, 00110, 00111, 01100, 01101, 01110$ ，數量等同 $mx$ 去除第 $2$ 位後再加 $1$，$01{\underline{1}}10 \Rightarrow 0110 = 6 \Rightarrow 6 + 1 = 7$。
• 去除第 $i$ 位後的數字數量可以將 $mx$ 左移 $i+1$ 位後，再右移 $i$ 位，但此時後 $i$ 位會被清空，因此需要再加上 $mx$ 的後 $i$ 位。可以透過 $((mx \gg (i + 1)) \ll i) \mid (mx \And mask)$ 來計算，其中 $mask = (1 << i) - 1$。

再來考慮如何計算出 $mx$：

• 若 $N$ 的第 $i$ 位為 $1$，則 $mx = N$；
• 若 $N$ 的第 $i$ 位不是 $1$，則 $mx = (N - (1 << i)) \mid mask$。
  • 舉🌰來說，若 $N = 25 = \rm{0b11001}$，且當前考慮第 $2$ 位，則 $mx = \rm{0b11001} - \rm{0b100} = \rm{0b10101} \Rightarrow \rm{0b10101} \mid \rm{0b11} = 23$。

複雜度分析

• 時間複雜度：$O(\log M)$，需要考慮 $M$ 的每個位元。
• 空間複雜度：$O(1)$

N, M = map(int, input().split())
MOD = 998244353
ans = 0
for i in range(M.bit_length()):
    if M & (1 << i):
        mask = (1 << i) - 1
        mx = N if N & (1 << i) else (N - (1 << i)) | mask # [1, N] 中第 i 位為 1 的最大數字
        x = ((mx >> (i + 1)) << i) | (mx & mask) # 刪除 N 的第 i 位
        ans = (ans + x + 1) % MOD # x + 1 即為 [1, N] 中第 i 位為 1 的數字數量
print(ans)

---

E - Max/Min (abc356 E)

題意

給定長度為 $N$ 的數列 $A=(A_1,\ldots,A_N)$。

計算 $\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\left\lfloor\frac{\max(A_i, A_j)} {\min(A_i,A_j)}\right\rfloor$。

其中，$\lfloor x \rfloor$ 代表不超過 $x$ 的最大整數。例如，$\lfloor 3.14 \rfloor=3$，$\lfloor 2 \rfloor=2$。

思路：計數(Counter) + 前綴和(Prefix Sum) + 貢獻法

對於任兩個數 $x$ 和 $y$，假設 $x < y$ ，該組合對答案的貢獻為 $\lfloor \frac{y}{x} \rfloor$ ，因此在枚舉時可以從小到大枚舉 $x$ 和 $y$，並計算其貢獻。

由於已知值域為 $[1, 10^6]$，因此可以使用一個長度為 $10^6+1$ 的陣列 $cnt$ 來計算每個數字出現的次數。

對於每個 $x$，其與 $[x, 2x)$ 間的任何數字 $y$ 的貢獻均為 $1$、與 $[2x, 3x)$ 間的任何數字 $y$ 的貢獻均為 $2$、$\ldots$、與 $[kx, (k+1)x)$ 間的任何數字 $y$ 的貢獻均為 $k$。由於要計算區間內的數字個數，因此可以使用 前綴和(Prefix Sum) $s$ 來計算，區間 $[l, r]$ 的數字個數為 $s[r]-s[l-1]$。

對於每個數字 $i$ ，枚舉所有可能的區間 $[i, 2i), [2i, 3i), \ldots, [ki, (k+1)i)$，計算其貢獻並加入答案中。由於在計算區間內的數字個數時計算到自己本身會很麻煩，因此可以分開計算。

複雜度分析

• 時間複雜度：$O(M \log M)$，其中 $M$ 為 $A$ 中的最大值，最大為 $10^6$。
  • 計算 $cnt$ 的時間複雜度為 $O(N)$；
  • 計算 $s$ 的時間複雜度為 $O(M)$；
  • 計算答案的時間複雜度為 $\frac{M}{1} + \frac{M}{2} + \ldots + \frac{M}{M} = O(M \log M)$。(調和級數)
• 空間複雜度：$O(M)$

N = int(input())
A = list(map(int, input().split()))
mx = max(A) # 10**6

cnt, s = [0] * (mx + 1), [0] * (mx + 1)
for a in A:
    cnt[a] += 1
for i in range(1, mx + 1): # Prefix Sum
    s[i] = s[i - 1] + cnt[i]
ans = 0
for i in range(1, mx + 1):
    ans += cnt[i] * (cnt[i] - 1) // 2 # 和自己本身對答案的貢獻
    for j in range(i, mx + 1, i):
        l = i + 1 if j == i else j # 排除自己本身
        r = min(mx, j + i - 1)
        ans += cnt[i] * (j // i) * (s[r] - s[l - 1])
print(ans)

---

F - Distance Component Size Query (abc356 F)

題意

給定一個整數 $K$。對於一個最初為空的集合 $S$，按照以下兩種查詢類型的順序處理 $Q$ 個查詢：

• 1 x：給定一個整數 $x$。如果 $x$ 在 $S$ 中，則從 $S$ 中移除 $x$；否則，將 $x$ 加入 $S$。
• 2 x：給定一個在 $S$ 中的整數 $x$。考慮一個圖，其中頂點是 $S$ 中的數字，如果它們之間的絕對差不超過 $K$，則兩個數字之間存在一條邊。請印出包含 $x$ 的連通分量中頂點的數量。

思路：縮點 + 有序容器(Sorted Container)

令 $s_1$ 為所有點的集合，$s_2$ 為會把一個連通塊的點縮成最大那個點的集合，即 縮點 。

• 舉🌰來說，若 $K = 10$ ，$s_1 = \{1, 9, 15, 30, 35, 40, 60\}$，則 $s_2 = \{15, 40, 60\}$。

可以在 $s_1$ 和 $s_2$ 中加入 $-\infty$ 和 $\infty$，這樣就不需要特別處理邊界情況。

對於查詢操作，即求 $x$ 所屬的連通塊大小：

• 可以用在 $s_2$ 中 bisect_left 找到 $x$ 所屬的連通塊的最大值索引 $idx$ 。
• 根據 $idx$ 可以求出當前連通塊的最大值 $cur$ 和前一個連通塊的最大值 $pre$ 。
• $x$ 所屬的連通塊大小即為 $cur$ 和 $pre$ 在 $s_1$ 中的索引差。

對於插入操作：

• 在 $s_1$ 中插入 $x$ 後，取得 $x$ 的索引 $i$，並根據 $x$ 的左右兩個點 $w_1$ 和 $w_2$ 進行操作。
• 若 $w_2 - w_1 > K$，代表原本 $w_1$ 和 $w_2$ 不在同一連通塊中，故 $w_1$ 必在 $s_2$ 中；若同時滿足 $x - w_1 \leq K$，則代表 $x$ 和 $w_1$ 在同一連通塊中，故 $w_1$ 不再是一個連通塊的最大值，因此需要將其從 $s_2$ 中刪除。
• 若 $w_2 - x > K$，代表 $x$ 需要成為一個新的連通塊的最大值，因此需要將其加入 $s_2$。

對於刪除操作：

• 取得 $x$ 的索引 $i$，並根據 $x$ 的左右兩個點 $w_1$ 和 $w_2$ 進行操作。
• 若 $x$ 在 $s_2$ 中，則代表 $x$ 是一個連通塊的最大值，因此需要將其從 $s_2$ 中刪除。
• 若 $x - w_1 \leq K$，則表示原本 $w_1$ 和 $x$ 在同一連通塊中，若同時滿足 $w_2 - w_1 > K$，則代表 $w_1$ 在操作後會是一個連通塊的最大值，因此需要將 $w_1$ 加入 $s_2$ 。

最後也是最重要的，為了避免用時過長，我們需要使用一個良好的資料結構來處理這個問題，這裡使用了 sortedcontainers 中的 SortedSet 來處理，其底層是一個類似於 B+ Tree 的資料結構，可以在 $O(\log N)$ 的時間內進行插入、刪除和查詢操作。

複雜度分析

• 時間複雜度：$O(Q \log N)$，其中 $Q$ 為查詢數量。
• 空間複雜度：$O(N)$

from sortedcontainers import SortedSet

Q, K = map(int, input().split())
queries = [list(map(int, input().split())) for _ in range(Q)]

# s1 是所有點的集合；s2 會把一個連通塊的點縮成最大那個點 (縮點)
s1, s2 = SortedSet([-10**19, 10**19]), SortedSet([-10**19, 10**19])

for op, x in queries:
    if op == 1:
        if x in s1: # 刪除操作
            i = s1.index(x)
            w_1, w_2 = s1[i - 1], s1[i + 1] # x 左右兩個點
            s1.remove(x)
            if x in s2:
                s2.remove(x)
            if (x - w_1 <= K) and (w_2 - w_1 > K): # 讓 w_1 重新出現在 s2 中
                s2.add(w_1)
        else: #  插入操作
            s1.add(x)
            i = s1.index(x)
            w_1, w_2 = s1[i - 1], s1[i + 1] # x 左右兩個點
            if (x - w_1 <= K) and (w_2 - w_1 > K): # 不需要 w_1 ，且原本 w_1 在 s2 中
                s2.remove(w_1)
            if w_2 - x > K: # 需要 x
                s2.add(x)
    else:
        idx = s2.bisect_left(x) # x 所屬連通塊中的最大值的索引
        pre, cur = s2[idx - 1], s2[idx] # 所屬連通塊中的最大值、前一個連通塊的最大值
        print(s1.index(cur) - s1.index(pre)) # 連通塊大小

---

參考資料

• AtCoder Beginner Contest 356 CDEF 讲解 by 幻想家协会会长
• AtCoder Beginner Contest 356 A 至 F 題讲解 by dreamoon

寫在最後

Cover photo is generated by @おにぎらずまる, thanks for their work!

I did not find any copyright declaration on the author’s personal page regarding permission or prohibition of use. Because of this, I used Pixiv.Cat to proxy the cover image. I actually do not save that image.

If the content of the article infringes on your copyright, please contact me through email or leave a comment to let me know, and I will promptly remove the relevant content.