🔗 A - 9x9 (abc389 A)

題意

給定一個長度為 $3$ 的字串 $axb$ ，輸出 $a \times b$ 。

思路

將字串轉為整數後相乘即可。

1 2	x, y = map(int, input().split("x")) print(x * y)

🔗 B - tcaF (abc389 B)

tags: `模擬(Simulation)` `二分搜尋(Binary Search)`

題意

給定一個不小於 $2$ 的整數 $X$ ，找出正整數 $N$ 使得 $N! = X$ 。

約束條件

$2 \leq X \leq 3 \times 10^{18}$

思路：模擬(Simulation) / 二分搜尋(Binary Search)

由於只有一個詢問，因此可以從 $1$ 開始枚舉 $N$ ，直到 $N! = X$ 為止。

如果有多個詢問的話，可以考慮預處理後使用二分搜尋。

X = int(input())
ans = f = 1
while f != X:
    ans += 1
    f *= (ans)
print(ans)

🔗 C - Snake Queue (abc389 C)

tags: `佇列(Queue)` `模擬(Simulation)`

題意

原本的題目敘述是以下問題的數學化：

有一群蛇在排隊，而每條蛇會佔據一個座標區間 $[x, x + l]$ ，其中 $x$ 為蛇的頭部座標， $l$ 為蛇的長度，且隊伍中第一條蛇的頭部座標為 $0$ 。

現在有 $Q$ 個操作，而每個操作有以下三種：

操作 $1$ ：1 l。將一條長度為 $l$ 的蛇加入到隊伍的末尾，注意其必須緊跟在最後一條蛇的尾巴後面。
操作 $2$ ：2。隊伍最前面的蛇離開隊伍，則後續的蛇往前移動，直到隊伍中第一條蛇的頭部座標為 $0$ 為止。
操作 $3$ ：3 k。輸出隊伍中從前面數第 $k$ 條蛇的頭部座標。

    gantt
    dateFormat x
    axisFormat %Q
    
    Snake1    : 0, 2
    Snake2    : 2, 3
    Snake3    : 3, 6
    Snake4    : 6, 10

約束條件

$1 \leq Q \leq 3 \times 10^{5}$
對於操作 $1$ ， $1 \leq l \leq 10^{9}$
對於操作 $2$ ，保證佇列不為空。
對於操作 $3$ ，令 $n$ 為佇列中的蛇的數量，則 $1 \leq k \leq n$ 。

思路：模擬(Simulation)

由於題目已經給出清晰的操作定義，且題目名稱也已經暗示了這是一道佇列問題，我們可以使用佇列（Queue）來處理這些操作，維護隊伍中的蛇的頭部座標即可。

然而，特別需要注意的是，當執行第二種操作（移除最前面的蛇）時，後續的蛇會因為需要向左平移而改變其座標。但顯然不能真正的將所有蛇的頭部座標減少。

為此可以維護一個變數 $s$ ，代表所有蛇的總平移量，每當執行移除操作時，將最前面的蛇的長度加到這個變數 $s$ 中。對於查詢操作，我們僅需借助這個變數 $s$ 去計算實際的頭部座標即可。如此我們便可以保存未平移的頭部座標，只要在輸出時減去 $s$ 即可。

例如以下狀況，此時 $s = 3$ ，因此第 $2$ 條蛇的頭部座標為 $6 - s = 3$ 。

    gantt
    dateFormat x
    axisFormat %Q
    
    Snake3    : 3, 6
    Snake4    : 6, 10

複雜度分析

時間複雜度： $\mathcal{O}(Q)$
空間複雜度： $\mathcal{O}(Q)$

from collections import deque

Q = int(input())
snakes = deque()
s = 0  # 減少的長度總和
for _ in range(Q):
    op, *args = map(int, input().split())
    if op == 1:
        h = snakes[-1][0] + snakes[-1][1] if snakes else 0
        l = args[0]
        snakes.append((h, l))
    elif op == 2:
        _, m = snakes.popleft()
        s += m
    else:
        k = args[0] - 1  # 0-based
        print(snakes[k][0] - s)

🔗 D - Squares in Circle (abc389 D)

tags: `幾何(Geometry)` `雙指標(Two Pointers)`

題意

在二維座標平面上，存在一個無限延伸的 $1 \times 1$ 正方形棋盤。

考慮在這些正方形的中心畫一個半徑為 $R$ 的圓。這些正方形中有多少個完全包含在圓內？

更準確地說，找出符合條件的整數對 $(i,j)$ 的數量，使得所有四個點 $(i+0.5,j+0.5)$ 、 $(i+0.5,j-0.5)$ 、 $(i-0.5,j+0.5)$ 和 $(i-0.5,j-0.5)$ 與原點的距離均不超過 $R$ 。

約束條件

$1 \leq R \leq 10^{6}$

思路：幾何(Geometry) + 雙指標(Two Pointers)

根據上圖，可以將問題分為以下 3 種情況：

正方形中心在圓心，由於 $R \geq 1$ ，因此固定是 $1$ 個
正方形中心在 $X$ $X$ 軸或 $Y$ $Y$ 軸上
- 在正 $X$ 軸上有 $R - 1$ 個，因此總共有 $4 \times (R - 1)$ 個
正方形中心在象限內
- 由於在二維平面上，圓與坐標軸具有對稱性。也就是說，若一個正方形位於第一象限內符合條件，則其在其他三個象限的對應位置的正方形也同樣符合條件。因此，我們只需計算第一象限內的符合條件的正方形數量，並將結果乘以 $4$ ，即可得到所有象限內的總數。
- 在第一象限中，判斷中心點座標為 $(i, j)$ 的正方形是否在圓內，等同於檢查 $(i + 0.5, j + 0.5)$ 到圓心的距離是否 $\leq R$
- 由於在第一象限中，當 $i$ 增加時， $j$ 只可能不變或減少，因此可以使用雙指標，從 $i = 1, j = R$ 開始，枚舉 $i$ 並維護最大的 $j$

複雜度分析

時間複雜度： $\mathcal{O}(R)$ $O (R)$
- 枚舉 $i$ 需要 $\mathcal{O}(R)$ ，而雖然內層迴圈看似也需要 $\mathcal{O}(R)$ ，但由於 $j$ 只會減少，因此 $i$ 和 $j$ 實際上都只會最多減少 $\mathcal{O}(R)$ 次。
空間複雜度： $\mathcal{O}(1)$

R = int(input())

ans = 1 + 4 * (R - 1)  # 中心位於原點和座標軸上
j = R
for i in range(1, R + 1):
    # 檢查中心點座標為 (i, j) 的正方形其是否在圓內
    while j > 0 and (i + 0.5) * (i + 0.5) + (j + 0.5) * (j + 0.5) > R * R:
        j -= 1
    # 此時左下角為 (i, j), (i, j-1), ... (i, 1) 的正方形都在圓內
    ans += 4 * j  # 四個象限
print(ans)

🔗 E - Square Price (abc389 E)

tags: `二分搜尋(Binary Search)`

題意

有 $N$ 種產品，每種產品的庫存量均為 $10^{100}$ 單位。

你可以購買每種產品的任意非負數量的單位。若要購買 $k$ 單位的第 $i$ 種產品，則需要花費 $k^2 \times P_i$ 日元。

如果你的總購買成本最多為 $M$ 日元，那麼你最多可以購買多少單位的產品總數？

約束條件

$1 \leq N \leq 2 \times 10^{5}$
$1 \leq M \leq 10^{18}$
$1 \leq P_i \leq 2 \times 10^{9}$

思路

由於購買 $k$ 件商品的總花費為 $p \cdot k^2$ ，故可以計算出購買第 $j$ 件商品的價格為 $p \cdot (j^2 - (j-1)^2) = p \cdot (2 \times j - 1)$ ，故我們可以知道所有 $N \times 10^{100}$ 件商品的價格。但顯然不可能列舉出所有商品的價格，而維護一個大小為 $N$ 的 Heap 也是不可行的，推導如下：

若所有商品的價格均為 $1$ ，且每種商品均購買 $k$ 件，則總價格為 $N \cdot k^2 \leq M$ ，得 $k \leq \sqrt{\frac{M}{N}}$
而我們需要對 Heap 操作 $k \cdot N$ 次，因此需要 $\mathcal{O}(k \cdot N \log N) = \mathcal{O}(\sqrt{M \cdot N} \log N)$ 的時間複雜度，顯然不可行。

因此考慮二分搜尋(Binary Search) ，找到一個整數 $x$ ，使得我們可以購買所有價格不超過 x 的商品。對於價格為 $p$ 的商品，若購買 $k$ 件，則需滿足 $p \cdot (2k-1) \leq x$ ，此時總價格為 $p \cdot k^2$ 。

二分找到最大的 $x$ 後，由於此時可能還可以購買部分價格為 $x+1$ 的商品，因此先用 $x+1$ 計算總價格，若總價格超過 $M$ ，則代表超過部分的商品價格都是 $x+1$ ，此時將超過的商品數量減去，即可得到答案。

複雜度分析

時間複雜度： $\mathcal{O}(N \log M)$ $O (N lo g M)$
- 二分搜尋可以購買的商品最大價格 $x$ 需要 $\mathcal{O}(\log M)$ 的時間
- 檢查函數需要遍歷所有商品，因此需要 $\mathcal{O}(N)$ 的時間
空間複雜度： $\mathcal{O}(N)$

from math import *

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

# 檢查當購買所有價格 <= x 的商品時，總價格會不會超過 M
def check(x):
    cost = 0
    for p in P:
        # (2 * k - 1) * p <= x
        k = (x + p) // (2 * p)
        cost += k * k * p
    return cost <= M

left, right = 0, 1 << 60
while left <= right:
    mid = (left + right) // 2
    if check(mid):
        left = mid + 1
    else:
        right = mid - 1

x = right
ans = cost = 0
for p in P:
    # 改成盡可能購買價格為 x+1 的商品
    k = ((x + 1) + p) // (2 * p)
    cost += k * k * p
    ans += k

# 已知買所有價格 <= x 的商品，總價格不會超過 M，
# 但若買價格為 x+1 的商品，總價格會超過 M，則代表超過的商品價格都是 x + 1
more = cost - M
ans -= ceil(more / (x + 1))
print(ans)

🔗 F - Rated Range (abc389 F)

tags: `線段樹(Segment Tree)` `懶標記線段樹(Lazy Segment Tree)` `二分搜尋(Binary Search)` `動態規劃(Dynamic Programming)`

題意

有 $N$ 場比賽，在第 $i$ 場比賽中（ $1 \leq i \leq N$ ），如果參賽選手的 rating 在 $L_i$ 和 $R_i$ 之間（包含邊界），則他的 rating 增加 $1$ ，每個選手都會參加所有比賽。

給定 $Q$ 個查詢，每個查詢提供一個整數 $X$ ，表示某選手的初始 rating，請計算選手參加完所有比賽後的最終 rating。

約束條件

$1 \leq N \leq 2 \times 10^5$
$1 \leq L_i \leq R_i \leq 5 \times 10^5$ $(1 \leq i \leq N)$
$1 \leq Q \leq 3 \times 10^5$
$1 \leq X \leq 5 \times 10^5$

思路：線段樹(Segment Tree) + 二分搜尋(Binary Search)

首先考慮最暴力的情況，對於每一個詢問，我們都模擬一遍該選手參加所有比賽的過程，這樣的時間複雜度是 $O(NQ)$ 的，這種複雜度是不可接受的。

但可以注意到，每次更新 rating 時，我們只會對一個區間進行操作，而這樣的操作是可以進行合併的。我們可以令 $f[j][i]$ 表示當初始分數為 $j$ 時，參加完第 $i$ 場比賽後的分數，則有：

$f[j][i] = \begin{cases} f[j][i-1] + 1 & \text{if } L_i \leq f[j][i-1] \leq R_i \\ f[j][i-1] & \text{otherwise} \end{cases}$

邊界條件為 $f[j][0] = j$ ，所求為 $f[j][n]$ ，其中 $j = X$ 。

因此可以考慮維護 $f[j][i]$ ，由於我們不需要中間的結果，因此只要維護 $f[j]$ 即可。那麼當參加完第 $i$ 場比賽後，我們可以更新所有滿足 $L_i \leq f[j] \leq R_i$ 的 $j$ ，使用稀疏表(Sparse Table) 或線段樹(Segment Tree) 的話，區間更新可以在 $O(\log X)$ 的時間內完成，其中 $X$ 為 rating 的值域，注意區間更新需要使用懶標記線段樹(Lazy Segment Tree)。

但這樣還有一個問題，如何找到 $f[j][i - 1]$ 中的 $L_i$ 和 $R_i$ 的位置呢？這裡可以利用 $f[j]$ 的特性，注意到當 $i = 0$ 時， $f[j]$ 的值是單調遞增的，而當 $i > 0$ 時， $f[j]$ 的值也一定是單調不減的，簡略的證明如下：

注意到每次比賽只會將符合條件的 rating 增加 $1$ ，而初始時 $f[j][0] = j$ 是單調不減的。每次比賽後，滿足條件的 $f[j]$ 增加 $1$ ，這最多只會讓 $f[j]$ 增加到和 $f[j+1]$ 相同，因此 $f[j]$ 是單調不減的。

根據這個性質，任何時刻的 $f[j]$ 都是單調不減的，因此可以使用二分搜尋(Binary Search) 來找到最小的 $j$ 使得 $f[j] \geq L_i$ ，以及最大的 $j$ 使得 $f[j] \leq R_i$ 。這樣可以確定需要更新的連續區間，從而利用線段樹進行區間更新。

為方便起見，這裡直接使用 AtCoder Library 的懶標記線段樹(Lazy Segment Tree)。

複雜度分析

時間複雜度： $\mathcal{O}(X + N \log X + Q \log X)$ $O (X + N lo g X + Q lo g X)$
- 初始化線段樹需要 $\mathcal{O}(X)$
- 對於每場比賽，需要 $\mathcal{O}(\log X)$ 的時間找到 $L_i$ 和 $R_i$ 的位置
- 對於每個查詢，需要 $\mathcal{O}(\log X)$ 的時間找到 $f[j][n]$ 的值
空間複雜度： $\mathcal{O}(N + X)$ $O (N + X)$
- 線段樹需要 $\mathcal{O}(X)$ 的空間

from atcoder.lazysegtree import LazySegTree

N = int(input())
contests = [tuple(map(int, input().split())) for _ in range(N)]
Q = int(input())
queries = [int(input()) for _ in range(Q)]

MX = max(max(r for _, r in contests), max(q for q in queries)) + 1
lst = LazySegTree(op=max,
                  e=0, 
                  mapping=lambda f, x: f+x,
                  composition=lambda f, g: f+g,
                  id_=0,
                  v=list(range(MX))  # 初始值是當前 index 對應的 rating
                  )

for l, r in contests:
    # 找到最小的 j 使得 f[j] >= l
    l = lst.max_right(0, lambda x: x < l)  
    # 找到最小的 j 使得 f[j] > r，其前一個位置即是最大的 j 使得 f[j] <= r
    r = lst.max_right(0, lambda x: x <= r)  
    lst.apply(l, r, 1)  # 將 [l, r) 的 rating 增加 1

for q in queries:
    print(lst.get(q))

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background, anime style,

1girl, solo, Furina, Furina (Genshin Impact), Genshin Impact, long hair, blush, smile, bangs, skirt, shirt, holding, hair between eyes, blue hair, collarbone, jacket, ahoge, outdoors, food, belt, holding food, strawberry, crepe,

An animated image of an anime girl with long blue hair and a white horn on her head. She is holding a cup with strawberries in it. Her eyes are open and her mouth is slightly open. She has a brown purse strap over her left shoulder. Her hair is a light blue color and she is wearing a cream colored shirt with a white collar. Her left hand is raised in the air. Her right hand is holding the ice cream cup. The ice cream is filled with strawberries.

近期打最差的一次，還是要多補題QQ