# APCS學習歷程報告
## 1. 引言
### 1.1 APCS簡介及其重要性
APCS（Advanced Placement Computer Science）是「大學程式設計先修檢測」的英文縮寫。這項檢測參考美國大學先修課程（AP）模式，與各大學合作命題，確保題目經過信效度考驗，以建立其公信力。APCS的重要性體現在以下幾個方面：
1. 填補評量缺口：在現有的入學管道中，APCS為學生的程式設計能力提供了客觀的評量依據。
2. 升學優勢：多所大學將APCS成績納入申請入學、特殊選才等多元入學管道的重要參考資料。
3. 銜接高等教育：有助於高中職重視資訊科學課程，並為大學提供抵免程式設計學分的依據。
### 1.2 個人學習目標和動機
我從小學四年級開始自學Python，並對程式設計產生了濃厚的興趣。國中會考後開始密集練習APCS題目，目標是全面提升自己的程式設計能力，為未來的學習與職涯發展奠定堅實的基礎。我不僅追求解題的正確性，更挑戰優化程式碼，力求達到最佳效能，同時也希望能為其他學習者提供有價值的參考資源。
## 2. 學習過程
### 2.1 系統性學習和準備
我的APCS學習歷程主要分為以下幾個階段：
1. 基礎知識積累：從小學開始自學Python，建立程式設計的基本概念和語法理解。
2. 集中訓練階段：國中會考後，開始密集練習APCS考古題和相關教材。
3. 深化優化階段：在完成所有題目後，開始挑戰程式碼的極限優化。
### 2.2 學習資源和方法
主要使用的學習資源包括：
1. APCS官方考古題
2. 吳邦一教授編寫的AP325講義
3. Python官方文檔和社區資源
學習方法主要包括：
1. 系統性刷題：按照難度和主題逐步完成所有APCS考古題。
2. 深入分析：對每道題目進行深入思考，探索多種解法。
3. 效能優化：不滿足於AC，而是志在追求最優解與頂尖的執行速度。
4. 知識整理：為每道題目撰寫詳細註解，鞏固所學知識，也替後人鋪路。
## 3. 考點分析
我成功完成了APCS所有的實作考古題，涵蓋了以下主要概念：
資料結構：
- 基本：陣列(array)、堆疊(stack)、佇列(queue)
- 進階：前後綴和(prefix and suffix)、差分(difference)、鏈結串列(linked list)、堆積(heap)、雜湊表(hash table)、並查集(dsu)、圖論(graph)
演算法：
- 排序與搜尋：排序演算法(sorting)、深度/廣度優先搜尋(dfs and bfs)、二分搜尋(binary searching)
- 進階技巧：貪心演算法(greedy)、動態規劃(dynamic programing)
## 4. 優化策略概述
在完成所有APCS題目後，我開始探索如何將Python程式碼優化到極致。這個過程不僅涉及邏輯的改進，還包括對Python語言特性的深入理解和巧妙運用。以下是我採用的主要優化策略：
1. **充分利用Python內建函式**：
- 基於Python的語言特性，優先使用內建函式庫。
- 內建函式通常以純C實現，執行效率可比純Python代碼快10~100倍。
- 需要注意版本兼容性：APCS使用Python 3.6.7 (Zero Judge 則是3.6.8)，某些新特性（如海象運算符、bisect的key參數、itertools.batched、itertools.pairwise）無法使用。
2. **IO優化**：
- 使用底層的sys.stdin和sys.stdout替代input()和print()。
- 在大量輸入輸出情況下，這種方法能顯著提升性能。
- 原因：input()和print()在sys.stdin和sys.stdout基礎上增加了更多user-friendly的功能，卻也因此犧牲了部分效率。
3. **避免使用全域變數**：
- Python對全域和區域變數的處理機制不同，使用區域變數可顯著提升速度。
- 實現方法：將所有程式碼封裝在一個main()函數中。
4. **方法調用快取**：
- 對頻繁使用的class.method()調用，將method存儲為局部變數。
- 這樣可以避免在class.__dict__中重複進行hash操作，提高access速度。
5. **善用迭代器**：
- 對於可以一次性處理的數據，優先使用迭代器。
- 迭代器可以節省內存空間，某些情況下比list或tuple的訪問更快。
- 上手難度偏高。
6. **減少函數定義**：
- 在Python中，進入函數會創建新的stack frame，這個過程有較大的固定開銷。
- 優化方法：盡可能用迴圈代替遞迴，使用bottom-up而非top-down的方法。
7. **邏輯優化**：
- 並非單純從撰寫程式的角度，而是在運行的邏輯上優化演算法，從根本提升效率。
這些優化策略不僅提高了程式的執行效率，也深化了我對Python語言和演算法設計的理解。在接下來的部分，我將通過具體的例子來展示這些優化策略的實際應用及其效果。
## 5. 優化成果展示
因為篇幅問題，我只列出優化後的程式，剛寫APCS的時候寫出來的程式又彆扭又醜，有各種list.pop(0)之類的噁心寫法，實在吐槽不完。最後的附錄會附上我寫APCS的完整歷程，包括剛開始接觸時，從青澀的WA痕跡以及各式絢爛的TLE死法，再到初次AC時的欣喜；以及經過優化的完整檔案。
### 5.1 使用itertools套件建立高效率iterator
1. [c297 棒球遊戲](https://zerojudge.tw/ShowProblem?problemid=c297)
考點主要是如何處理輸入的問題，用itertools輕鬆搞定。
因為是APCS早期，也沒有甚麼edge case，應該可以算是最簡單的第四題。
```python
def main():
from sys import stdin
from itertools import chain, zip_longest
*lines, b = stdin.readlines()
b = int(b)
# 把輸入重新排版 變成每一輪結果的iterator
plays = chain.from_iterable(
zip_longest(*(line.strip().split()[1:] for line in lines))
)
out = score = fi = se = th = 0
while out < b:
play = next(plays)
if play == "1B":
score += th
fi, se, th = 1, fi, se
elif play == "2B":
score += se + th
fi, se, th = 0, 1, fi
elif play == "3B":
score += fi + se + th
fi, se, th = 0, 0, 1
elif play == "HR":
score += fi + se + th + 1
fi = se = th = 0
else: # 出局
out += 1
if out % 3 == 0:
fi = se = th = 0
print(score)
main()
```
2. [o078 缺字問題](https://zerojudge.tw/ShowProblem?problemid=o078)
這題有很多種解法，可以直接產生所有排列組合，再將目標字串S中出現的所有子字串從排列組合中刪除；或者先生成S的所有子字串，再依照字典序由小到大嘗試所有排列組合，直到該次嘗試的排列組合沒有出現在S中。以下是分別是第一、二種解法。
這題的重點主要還是在估算時間複雜度上，觀察到題目保證k^l (下面的d^k)在6*10⁵內，因此就從窮舉法下手。窮舉出所有的子字串組合也是一個小考點，但用itertools可以輕鬆解決。
- Sol 1
```python
# 缺字問題 - O(d^k + s*k) O(d^k) - 0.2sec 16.3mb (second place)
# https://zerojudge.tw/ShowProblem?problemid=o078
def main():
from sys import stdin
from itertools import product, repeat
e = stdin.readline
d = e().strip()
k = int(e())
s = e().strip()
# 產生所有可能的子字串並存入set
u = set(map("".join, product(*repeat(d, k))))
for i in range(len(s) - k + 1):
u.discard(s[i:i+k]) # 將出現在S中的子字串刪除
print(min(u)) # 輸出字典序最小
main()
```
- Sol 2
```python
# 缺字問題 - O(d^k + s*k) O(d^k) - 0.3sec 16.6mb (third place)
# https://zerojudge.tw/ShowProblem?problemid=o078
def main():
from sys import stdin
from itertools import product, repeat
e = stdin.readline
d = e().strip()
k = int(e())
s = e().strip()
# 依字典序由小到大產生所有可能的子字串的iterator (不會產生全部)
it = map("".join, product(*repeat(d, k)))
# 產生S的所有子字串
sub = frozenset(s[i:i+k] for i in range(len(s) - k + 1))
for i in it:
if i not in sub: # 沒有出現在S的任何子字串中
return print(i)
main()
```
### 5.2 使用前綴和與差分序列優化曼哈頓距離相關題目
1. [k732 特殊位置](https://zerojudge.tw/ShowProblem?problemid=k732)
不太難的二維陣列題，照題述實作即可。只是在求曼哈頓距離內的和時我是用了比較麻煩的每一行做前綴和寫法，從原本的92ms優化到55ms，沒差多少。
```python
# 特殊位置 - O(mn) O(10mn)=O(mn) - 55ms 3.6mb
# https://zerojudge.tw/ShowProblem?problemid=k732
def main():
from sys import stdin
from itertools import accumulate
e = stdin.readline
m, n = map(int, e().split())
# 每行做前綴和
l = tuple((*accumulate(map(int, e().split())), 0) for i in range(m))
ans = []
for i, row in enumerate(l):
pre = 0
for j, cur in enumerate(row):
v = cur - pre # 用前綴和求該格的值
if sum((lambda r, d: r[min(n - 1, j + d)] - r[max(0, j - d) - 1])(l[ii], v - abs(i - ii)) # 查詢該行曼哈頓距離內的區間和
for ii in range(max(0, i - v), min(m, i + v + 1))) % 10 == v: # 遍歷曼哈頓距離內的行
ans.append((i, j))
pre = cur
# 列印答案
print(len(ans), *(f"{i} {j}" for i, j in ans), sep="\n")
main()
```
2. [o077 電子畫布](https://zerojudge.tw/ShowProblem?problemid=o077)
這題也是依照題述實作即可，python也比較不需要注意edge case。我則是用差分序列進行每一行的區間修改，最後再對差分做前綴和後輸出，比較需要注意的就是左右邊界的edge case。
```python
# 電子畫布 - O(mn + rt) O(mn) - 20ms 3.4mb TOP
# https://zerojudge.tw/ShowProblem?problemid=o077
def main():
from sys import stdin, stdout
from itertools import accumulate
e = stdin.readline
m, n, k = map(int, e().split())
l = tuple([0] * n for i in range(m))
for _ in range(k):
r, c, t, x = map(int, e().split())
for i in range(max(0, r - t), min(m, r + t + 1)):
# 使用差分更新區間
row = l[i]
d = t - abs(r - i) # 該行左右延伸的長度
row[max(0, c - d)] += x # 更新左端點
# 右端點在界內再更新
ri = c + d + 1
if ri < n: row[ri] -= x
# 將差分還原並輸出
# 等價於 for row in l: print(*accumulate(row))
stdout.write("\n".join(" ".join(map(str, accumulate(row))) for row in l))
main()
```
### 5.3 使用Bottom-up代替Top-down
1. [b967 血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967)
這題就是基本的樹的DP，說來挺有情懷，其實早在小學時媽媽就幫我買了本APCS的Python實戰手冊，這題就是第一次讓我毫無想法的考古題，看著書中的參考解答不知想了多久依舊只有半知半解。書中使用的是用遞迴寫成的Top-down dfs (說不定在ZJ上根本過不了)，而現在我已經可以在十幾分鐘內搓出如此漂亮的Bottom-up解法，對於自身的進步十分有感!
稍微解釋一下可讀性較低的部分: stk是一個stack，為了一點點效率我將它的mathod快取起來存進變數，後面還會再看到這樣的作法；`h: list[tuple[int, int]]`內儲存的是每個父節點的 (第一高子樹, 第二高子樹)；ans內儲存的則是`max(h0 + x1 for h0, h1 in h)`也就是前二高子樹的高度總和最大值，即為所求。
```python
# 血緣關係 - Bottom-up dfs - O(n) O(n) - 0.4sec 17.7mb (third place)
# (雖然我只有第三名 但第一名看起來像是NA95%以後心態炸裂直接用了O(1)黑魔法 所以我理論第二)
# https://zerojudge.tw/ShowProblem?problemid=b967
def main():
from sys import stdin
e = stdin.readline
n = int(e())
pa = [None] * n # 父節點
indeg = [0] * n # 子節點個數
for i in range(n-1):
a, b = map(int, e().split())
indeg[a] += 1
pa[b] = a
ans = 0
h = [(0, 0)] * n # (最高, 次高)
# 找出葉子
stk = [i for i, v in enumerate(indeg) if v == 0]
app, pop = stk.append, stk.pop
while stk:
i = pop()
h0, h1 = h[i]
# 更新答案
ans = max(ans, h0 + h1)
p = pa[i]
if p is None:
# 到root就停
root = i
break
# 更新父節點高度
h0 += 1 # 自己的高度要+1
p0, p1 = h[p]
if h0 > p0:
# 更新最高
h[p] = (h0, p0)
elif h0 > p1:
# 更新次高
h[p] = (p0, h0)
# 如果父節點的所有子節點都算完了就接著處理
indeg[p] -= 1
if indeg[p] == 0:
app(p)
print(ans)
main()
```
2. [c463 樹狀圖分析](https://zerojudge.tw/ShowProblem?problemid=c463)
此題也是基本的樹DP bottom-up，就不過多贅述。
比較有趣的是`while ans[i] < h`的部分，寫了一個小小的剪枝。
```python
# 樹狀圖分析 - bottom-up dfs - O(n) O(n) - 0.3sec (second place) 17.4mb (TOP)
# https://zerojudge.tw/ShowProblem?problemid=c463
def main():
from sys import stdin
e = stdin.readline
n = int(e())
parent = [None] * n
leaves = []
for i in range(n):
c, *child = map(int, e().split())
if c == 0: # 子節點數為零就是葉子
leaves.append(i)
else:
for j in child: # 讓每個子節點都找得到爸爸
parent[j-1] = i
root = parent.index(None) # 找根
ans = [-1] * n
for i in leaves:
h = 0 # 高度
while ans[i] < h: # 不再是最大值就結束
ans[i] = h
if i == root: break # 到根就停
i = parent[i] # 追本溯源
h += 1
print(root+1)
print(sum(ans))
main()
```
3. [m933 邏輯電路](https://zerojudge.tw/ShowProblem?problemid=m933
)
這題也是樹DP的概念，只是有了輸入、計算、輸出三種節點，計算更有四種操作，實作起來對新手有一定難度。
這題我是將所有節點的資訊都串成一條，增加單一list的使用率，避免建立額外的指標。
`sig: list[int]`用來儲存所有節點輸入的訊號，因為最多只有二元計算，所以每個節點只需要一格空間暫存即可；`typ: tuple[int]`儲存計算節點的運算類型，唯讀；`delay: list[int]`用來儲存運算及輸出節點的延遲，其實也就是節點高度。
二元運算的部分我都是直接使用int完成，而不是轉成bool再轉回來。
```python
# 邏輯電路 - O(p+q) O(p+q+r) - 0.4sec 13.9mb TOP
# https://zerojudge.tw/ShowProblem?problemid=m933
def main():
from sys import stdin
from itertools import repeat
from operator import __and__, __or__, __xor__
e = stdin.readline
# 二元運算函式
f = (None, __and__, __or__, __xor__)
p, q, r, m = map(int, e().split())
p_q = p + q
sig = [*map(int, e().split()), *repeat(None, q + r)]
typ = tuple(map(int, e().split()))
delay = [0] * (q+r)
# 建圖
G = [[] for i in range(p_q)]
for i in range(m):
u, v = map(int, e().split())
G[u-1].append(v-1)
# dfs的stack (idx, signal, delay)
l = [(i, s, 0) for i, s in enumerate(sig[:p])]
app, pop = l.append, l.pop # 快取函式
while l:
i, s, d = pop()
for j in G[i]:
if j >= p_q: # 輸出端
sig[j] = s
delay[j-p] = d
elif typ[j-p] == 4: # 進到not邏輯閘
ns = sig[j] = s ^ 1
nd = delay[j-p] = d + 1
app((j, ns, nd))
elif sig[j] is None: # 進到新的二元邏輯閘
sig[j] = s
delay[j-p] = d + 1
else: # 第二次進入二元邏輯閘
ns = sig[j] = f[typ[j-p]](s, sig[j])
nd = delay[j-p]
if nd < d + 1:
nd = delay[j-p] = d + 1
app((j, ns, nd))
print(max(delay[-r:]))
print(*sig[-r:])
main()
```
### 5.4 優化stack (避免遞迴)
簡單說明一下我優化stack的方式:
- 快取pop, append(或是extend)等method。
- 快取最後一項，也就是`stack[-1]`，減少access時間。
- 將二維壓成一維，減少access時間。
例如: 原本要append一個tuple，變成將tuple用extend逐項加入，但如果tuple項數較多就還是用append。需要注意，如果是用extend逐項加入，pop出來的時候會是倒序的狀態，實際實作的時候完全不要用這種找自己麻煩又成效不大的優化。
1. [h028 砍樹](https://zerojudge.tw/ShowProblem?problemid=h028)
這題比較明顯是純stack的題目。stack的優化與上述的方法差不多就不多加贅述。
比較有意思的是我one-pass的方式，輸入的資訊都維持iterator的狀態，遍歷時遍歷要砍的樹(cur)的右邊那棵樹(nxt)，以nxt和前面未砍的樹(last,即為stack[-1])的位置判斷cur是否能往左右砍倒。
左側邊界條件，也就是stack內的樹全都被砍空的情況，我在stack[0]\(也就是初始化時的last)放了一顆無限高的樹，因此他跟吳剛的桂樹一樣不可能被砍倒；右側邊界條件，我則用chain在輸入檔的最後安插了一顆位置R高度None的樹(使用None是因為其進行大部分運算時皆會報錯，便於debug)，因為只會討論nxt的前一棵樹是否能砍，右邊界(R, None)時沒有更右邊的樹了，因此程式不會考慮這顆"樹"。
```python
# 砍樹 - O(n) O(n) - 0.2sec 21.4mb TOP
# https://zerojudge.tw/ShowProblem?problemid=h028
def main():
from sys import stdin
from itertools import chain
e = stdin.readline
n, R = map(int, e().split())
p = map(int, e().split())
h = map(int, e().split())
c = m = 0 # 可砍數量 最大高度
# 初始化stack
stk = [] # 儲存暫時沒辦法砍的樹的stack
extend, pop = stk.extend, stk.pop # 快取函數
lp, lh = 0, float("INF") # 快取stack的最後一項 初始化為 sentinel
# 製作所有樹的iterator
it = chain(zip(p, h), ((R, None), )) # 加入右邊界
cp, ch = next(it) # 目前這棵樹 初始化先取第一項
for np, nh in it: # 取下一顆樹 討論目前這棵樹(cp, ch)能否被砍
# 往右砍 或 往左砍
if ch <= np - cp or ch <= cp - lp:
# 可以直接砍掉
c += 1
m = max(ch, m)
# 看前面的樹能不能往右砍
while lh <= np - lp:
c += 1
m = max(lh, m)
lh, lp = pop(), pop() # pop時記得倒序
else:
# 往左往右都壓到 沒辦法砍 先加到stack
extend((lp, lh))
lp, lh = cp, ch
cp, ch = np, nh
print(c, m, sep="\n")
main()
```
2. [f637 DF-expression](https://zerojudge.tw/ShowProblem?problemid=f637)
題目給的n≤1024，使用函式遞迴的話很有可能會吃`RecursionError: maximum recursion depth exceeded`(Python預設遞迴深度限制是1000)，而且前面也提過，函式遞迴的常數很大，因此寫Python一定要會用stack代替遞迴，此題就是適合做此練習的題目，各層遞迴之間的變數傳遞關係很單純。
一般寫法可能是紀錄邊長，紀錄答案時再平方，而我的寫法是直接紀錄面積，層級變化時再*4或/4 (位元運算左右移兩位)；stack中紀錄的是當前區塊還剩多少子區塊尚未處理，並使用cur變數快取stack的最後一項。
```python
# DF-expression - O(n) O(n) - 0.5sec 6.9mb TOP
# https://zerojudge.tw/ShowProblem?problemid=f637
def main():
from sys import stdin
e = stdin.readline
s = e().strip()
area = int(e()) ** 2
ans = 0
stk = [None] # 初始化為一大塊 None為sentinel
cur = 1 # 用來儲存原本應該放在stk最後一項的值 減少access時間
app, pop = stk.append, stk.pop # 快取函數
for i in s:
# 處理目前這塊
cur -= 1
if i != "2": # i == "0" or "1"
# 加上黑色面積
if i == "1": ans += area
# 將已經處理完的色塊pop掉 把面積*4
while cur == 0:
cur = pop()
area <<= 2
else: # i == "2"
# 面積/4 分成四小塊
area >>= 2
app(cur)
cur = 4
print(ans)
main()
```
3. [j124 石窟探險](https://zerojudge.tw/ShowProblem?problemid=j124)
跟上一題很像，不多加贅述。
`(x & 1) + 2`的式子是針對題述的"編號奇數3個房間，偶數2個房間"
```python
# 石窟探險 - O(n) O(n) - 0.2sec 12.3mb (second place)
# (雖然我只是第二名 但第一名看起來像是用了O(1)黑魔法 他用C++ 58ms 用python 30ms)
# https://zerojudge.tw/ShowProblem?problemid=j124
def main():
from sys import stdin
e = stdin.readline
l = map(int, e().split())
i = next(l)
c = (i & 1) + 2
ans = 0
stk = [None, None]
extend, pop = stk.extend, stk.pop
for j in l: # 遍歷紀錄的路徑
while c == 0:
c, i = pop(), pop() # pop時記得倒序
c -= 1
if j != 0:
ans += abs(j - i)
extend((i, c))
i, c = j, (j & 1) + 2
print(ans)
main()
```
4. [j607 先加後乘與函數](https://zerojudge.tw/ShowProblem?problemid=j607)
- Sol 1
先給一個有創意的寫法：簡單來講就是創一個class，將乘法和加法的動作互換，讓實際做了加法的函式的優先級比實際做了乘法的函式要高，再將輸入中的乘法和加法符號互換，最後eval一下就行了。
但這題把eval禁了。
```python
# 先加後乘與函數 - "不允許使用eval"
# https://zerojudge.tw/ShowProblem?problemid=j607
def main():
from sys import stdin
class I(int):
def __new__(cls, arg) -> object:
return super().__new__(cls, arg)
def __mul__(self, other):
return I(int.__add__(self, other))
def __add__(self, other):
return I(int.__mul__(self, other))
def f(*args):
return max(args) - min(args)
s = stdin.readline().strip()
ans = []
curnum = None
for i, c in enumerate(s):
if c.isdigit():
if curnum is None:
curnum = i
else:
if curnum is not None:
ans.append("I({})".format(s[curnum:i]))
curnum = None
ans.append("+" if c == "*" else "*" if c == "+" else c)
if curnum is not None:
ans.append("I({})".format(s[curnum:]))
print(eval("".join(ans)))
main()
```
- Sol 2
正經的解法，一層f()使用四個數字記錄該層遞迴資訊，但輸入的長度不超過500，所以理論用函式遞迴也能AC。程式的實際運作我都用註解寫得很清楚了，但說實話還是不太好理解，生個測資看著程式跑幾次大概就能懂了。
這題身為p3給出了相當的難度(除了數值範圍的部分實在太鬆，至少可以上10⁵)，尤其case挺多，實作時思考起來並不容易，需要搞清楚哪些case的共同動作是甚麼，再安排好順序，適時地continue。
我認為比較有趣的是我將\n換行字元當作一個case去結束程式。
```python
# 先加後乘與函數 - O(n) O(f)(max depth of f(), worst O(n)) - 19ms 3.4mb
# https://zerojudge.tw/ShowProblem?problemid=j607
"""理論最高效率 但測資太弱"""
def main():
from sys import stdin
l = stdin.readline() # including "\n"
"""
stk: list[int]
為4個數字一組的資料結構(除了第一組為2)，一組表示一層f()函式
4個數字分別表示 最大值, 最小值, 當前數字積, 當前數字和
而第一組(沒有被任何f()包著的)因為不需要最大最小值，所以只需要後面兩格
"""
stk = []
app, pop = stk.append, stk.pop # 快取stack會用到的函式
M, m, p, s = None, None, 1, 0 # 快取stack最後一項
numi = None
for i, c in enumerate(l): # 總共可能會有 數字 f ( , ) + * 共7類字元 (結尾還會有\n)
# case 數字
if c.isdigit():
if numi is None:
# 新的數字開始
numi = i
continue
# c is not digit
if numi is not None:
# 拼接多位數字
x = int(l[numi:i])
numi = None
else:
x = 0
# case f (
if c == "f":
# f不做任何事 看括號就可以了
continue
if c == "(":
# 加入四個初始值 表示新的一層f()
app((M, m, p, s))
M, m, p, s = 0, 200, 1, 0
continue
# case + * , ) \n
# 遇到以上5種字元都要先"加"上當前數字
s += x
if c == "+":
# 已經加了 這邊沒事
continue
# case * , ) \n
# 遇到以上4種字元都要再將最後兩個儲存的數字相"乘"
x = p * s
# case * \n
if c == "*":
# 重新設定最後兩格數
p, s = x, 0
continue
if c == "\n": # line ends
# 直接列印答案
print(x)
return
# case , )
# 結算最大值&最小值
M, m, p, s = max(M, x), min(m, x), 1, 0
# case , 沒事幹了 直接pass
# case )
if c == ")":
# 結束一層f()
d = M - m
M, m, p, s = pop()
# 將 最大最小值之差 加到上一層
s += d
main()
```
5. [f733 磁軌移動序列](https://zerojudge.tw/ShowProblem?problemid=k733)
這題可有情懷了，是我第一回寫APCS時卡最久的一題。因為有迴圈第一個位置的轉移問題，導致各層之間的遞迴關係不是單層，可能要往前找好幾層。
第一回寫時，我最開始的寫法是把每一層迴圈展開，拉成直鏈硬跑；接著改成迴圈用計算的，但瘋狂WA，遞迴也還是TLE；最後寫了一個很醜的stack解法，至少AC了，真開心。
這次優化時看著舊的code，毫無可讀性可言，完全看不懂，只好打掉重練，這回還是在迴圈各層級之間的轉移踩了不少坑。
最終突破排行榜的0.1sec大關，晉升到毫秒等級，真是恭喜自己。
邏輯上比前一題還要更加抽象而難以理解，此題實為難題，更為愛題。
```python
# 磁軌移動序列 - O(n) O(n) - 76ms 4.6mb TOP
# https://zerojudge.tw/ShowProblem?problemid=k733
def main():
from sys import stdin
e = iter(stdin.readline().strip())
nxt = e.__next__
nxt() ; nxt() ; nxt() # 最前面固定有的T10弄掉
cur = 10
# 初始化用來記錄迴圈資訊的stack
# True是sentinel (詳見case Txx內的迴圈)
# 0是第0層(沒有迴圈)的位移總和
stk = [True, 0]
_len = 2 # 使用一個變數紀錄len(stk) 省時間
extend, pop = stk.extend, stk.pop # 快取函數
for c in e:
if c == "T": # Txx
x = int(nxt() + nxt())
idx = _len - 2
while stk[idx] is None:
stk[idx] = x # 紀錄 迴圈內的第一個位置
idx -= 4 # 往前找一層迴圈
stk[idx + 1] += abs(x - cur) # 紀錄位移
cur = x # 移動位置
elif c == "L": # Lx
x = int(nxt())
# 加入迴圈資訊 (次數, 迴圈前的最後位置, 迴圈內的第一個位置, 迴圈內位移總和)
extend((x, cur, None, 0))
_len += 4
else: # c == "E"
# pop的時候順序會相反
dis, first, last, x = pop(), pop(), pop(), pop()
# 模擬重複多次
stk[-1] += dis + (dis + abs(cur - first)) * (x-1)
_len -= 4
print(stk[-1])
main()
```
### 5.5 邏輯優化
不同於前面比較語法導向的優化(當然也優化了許多自己原先的邏輯)，接下來這些就是完完全全的邏輯優化了。
1. [e465 置物櫃分配](https://zerojudge.tw/ShowProblem?problemid=e465)
參考了解題報告: [0/1 背包仿 bitset 解](https://zerojudge.tw/ShowThread?postid=35780&reply=0) (但裡面附的code連結已經掛掉了)
這題就是0/1背包加上了一點包裝的題目，一般的做法就是用一個set雜湊可能的櫃子借出數量，轉移就會變成O(n)，但此解巧妙之處就在於用二進位代替set，如果將位移操作考慮為O(1) (當然最後數字會變很大，位移操作接近線性複雜度)，那整體就會從O(n²)變成常數稍大的O(n)。
我跟題解原作者的差別其實也只有在倒數第二行的lowbit，原作者是將bit依二進位轉成str後用str.find尋找符合條件的第一個"1"，而我則是利用在BIT中學到的lowbit二進位算式優化，使結果拉開了1ms的微小差距。
這次是數學的勝利。
```python
# 置物櫃分配 - O(n) O(n) - 18ms 3.3mb TOP
# https://zerojudge.tw/ShowProblem?problemid=e465
def main():
from sys import stdin
e = stdin.readline
# 櫃子總數 櫃子需求量 人數(用不到)
m, s, n = map(int, e().split())
l = tuple(map(int, e().split()))
m -= sum(l) # 沒有被借走的櫃子
if m >= s:
# 剩下的櫃子夠用 不用退還
print(0)
else:
bit = 1
for i in l:
bit |= (bit << i)
# 把剩下的櫃子都先借出
# 至少需要退還 s-m 個
s -= m
bit >>= s
# 找出最右邊的1 (lowbit(x) = x & -x)
print(s + (bit & -bit).bit_length()-1)
main()
```
2. [f638 支點切割](https://zerojudge.tw/ShowProblem?problemid=f638)
參考解題報告: [找支點O(1)的方法](https://zerojudge.tw/ShowThread?postid=30025&reply=0)
此題限制切割層級K<30，因此使用遞迴可以AC，但還是用stack。
這題一般來講就是用sliding window的邏輯，線性複雜度找切點；但也可以藉由億些前綴和寫出區間力矩和的O(1)查值(常屬稍大)，再對區間內二分搜就能O(logn)找切點；然而這遠沒有直接套質心公式來得好寫又快速，而套公式需要注意的就是各種edge case，選的切點不能在邊緣、小數如何四捨五入......等等。
最終也是成功突破0.1sec的大關，以88ms榮登桂冠。
這次是物理的勝利。
```python
# 支點切割 - O(n+2^k) O(n+2^k) - 88ms 13mb TOP
# https://zerojudge.tw/ShowProblem?problemid=f638
def main():
from sys import stdin
from itertools import accumulate, starmap
e = stdin.readline
"""
質心公式: (x 表示位置, m表示質量)
sum(xi * mi for xi, mi in zip(x, m)) / sum(m)
"""
n, k = map(int, e().split())
l = tuple(map(int, e().split()))
# 求質心需要用到區間和 把前綴和準備好 (1-based)
p = (0, *accumulate(l))
xp = (0, *accumulate(starmap(int.__mul__, enumerate(l))))
ans = 0
# 初始化 區間為整個棍子(左閉右開) 切割層級1
stk = [(0, n, 1)]
app, pop = stk.append, stk.pop
while stk:
# 取出一個區間
i, j, d = pop()
# 計算切點
sxp, sp = xp[j] - xp[i], p[j] - p[i] # 前綴和取區間 (1-based)
q, r = divmod(sxp, sp)
if r > sp >> 1: # 四捨五入的概念 比較靠近實際切點的位置 (>而不是>= 因為左側優先)
q += 1
# 不能切邊邊 校正回歸
if q <= i:
q = i + 1
elif q >= j - 1:
q = j - 2
# 更新答案
ans += l[q]
# 分割新的區間
if d < k: # 確保切割層級
# 左半邊
t = q - i # 該區間長度
if t == 3: # 長度剛好為3 可以直接更新答案
ans += l[i + 1]
elif t > 3: # >3 就存起來等等切
app((i, q, d + 1))
# <3 不能切 直接丟掉
# 右半邊 同理
t = j - q - 1
if t == 3:
ans += l[q + 2]
elif t > 3:
app((q + 1, j, d + 1))
print(ans)
main()
```
3. [o078 缺字問題](https://zerojudge.tw/ShowProblem?problemid=o078)
前面說過，這題有很多種解法，上面已經分享了兩個用字串排列組合的解，分別拿了排行榜第二、第三名，下方題解的邏輯，是將所有可能的排列組合依照k進位編號(k為字母種類數，即下面的t)，再以相同的方法尋找答案。
因為將字串編碼成數字，因此在遍歷子字串時的求值就能用sliding window的技巧從原本的O(l) (l為子字串長度，即下面的k) 優化成O(1)。但如何壓低編碼轉換時的常數也很重要。
又是數學的勝利。
- Sol 3
```python
# 缺字問題 - O(d^k + s) O(d^k) - 0.2sec 5.1mb TOP
# https://zerojudge.tw/ShowProblem?problemid=o078
def main():
from sys import stdin
from itertools import islice
e = stdin.readline
# 輸入並產生各種資訊
a = e().strip()
d = {c:i for i, c in enumerate(a)}
t = len(a)
k = int(e())
s = map(d.__getitem__, e().strip()) # 將字元轉成數字
n = pow(t, k) # 所有可能的數量
cur = 0
# 將所有可能存入set
u = [True] * n
# 處理前k-1個字元
for i in islice(s, k-1):
cur = cur * t + i
# 處理所有字串
for i in s:
cur = cur * t % n + i
u[cur] = False # 刪除該字串
cur = next(i for i, v in enumerate(u) if v is True) # 最小的為答案
# 將答案轉換回字串
ans = []
for i in range(k):
cur, r = divmod(cur, t)
ans.append(r)
print("".join(map(a.__getitem__, reversed(ans))))
main()
```
- Sol 4
```python
# 缺字問題 - O(d^k + s*k) O(d^k) - 0.3sec 14.3mb (fifth place)
# https://zerojudge.tw/ShowProblem?problemid=o078
def main():
from sys import stdin
from itertools import islice
e = stdin.readline
# 輸入並產生各種資訊
a = e().strip()
d = {c:i for i, c in enumerate(a)}
t = len(a)
k = int(e())
s = map(d.__getitem__, e().strip()) # 將字元轉成數字
n = pow(t, k) # 所有可能的數量
# 將s的所有子字串進行編碼
u = set()
cur = 0
# 處理前k-1個字元
for i in islice(s, k-1):
cur = cur * t + i
# 處理所有字串
for i in s:
cur = cur * t % n + i
u.add(cur)
for cur in range(n): # 依照字典序由小到大嘗試
if cur not in u:
# 將答案轉換回字串
ans = []
for i in range(k):
cur, r = divmod(cur, t)
ans.append(r)
print("".join(map(a.__getitem__, reversed(ans))))
return
main()
```
4. [j123 運貨站](https://zerojudge.tw/ShowProblem?problemid=j123)
看起來是難寫的模擬題，但詳見[題解](https://zerojudge.tw/ShowThread?postid=40953) (自)
```python
# 運貨站 - O(k) O(m) - 19ms 3.4mb
# https://zerojudge.tw/ShowProblem?problemid=j123
def main():
from sys import stdin
from itertools import repeat
e = stdin.readline
add = int.__add__
# A~E貨物的 高度,面積,形狀
T = (
(4, 4, (1, 1, 1, 1)),
(1, 3, (3,)),
(2, 4, (2, 2)),
(2, 4, (1, 3)),
(3, 5, (1, 2, 2))
)
m, n, k = map(int, e().split())
l = [0] * m # 貨艙目前狀況 (每個高度已經塞了幾個單位)
area = throw = 0 # 答案
for _ in range(k):
t, y = e().split()
h, a, t = T[ord(t) - 65] # 取得貨物資訊
y = int(y)
x = max(map(add, l[y:y + h], t)) # 把貨物硬塞進去後 該區間會到x
if x <= n: # 未超過限制 更新區間
l[y:y + h] = repeat(x, h)
area += a
else: # 超過限制 丟掉
throw += 1
print(m * n - area, throw)
main()
```
5. [m371 卡牌遊戲](https://zerojudge.tw/ShowProblem?problemid=m371)
這題一般來講依照題意實作即可，數字很小所以複雜度沒問題。
但再稍微觀察題目就會發現其實能夠一次刪多組。
假設某一行是`0 2 3 3 2 0`，我們就`for val in row`遍歷。
初始化`stack = [None] # sentinel`
`val = 0 != None; push(0) -> stack = [None, 0]`
`val = 2 != 0; push(2) -> stack = [None, 0, 2]`
`val = 3 != 2; push(3) -> stack = [None, 0, 2, 3]`
`val = 3 == 3; pop() -> stack = [None, 0, 2]`
有沒有看到? 魔法在慢慢發生
`val = 2 == 2; pop() -> stack = [None, 0]`
`val = 0 == 0; pop() -> stack = [None]`
但實際上不太可能一次刪完，刪除一組牌之後還要將他們設定為-1之類的代表空格，遍歷時遇到-1就不執行任何動作直接略過。
就依照這個邏輯橫豎橫豎一直跑，直到刪不了任何東西就結束。
```python
# 卡牌遊戲 - O(m²n²) O(mn) - 20ms 3.4mb TOP
# https://zerojudge.tw/ShowProblem?problemid=m371
def main():
from sys import stdin
e = stdin.readline
m, n = map(int, e().split())
l = tuple(list(map(int, e().split())) for i in range(m))
ans = 0
# first 紀錄第一輪時兩個方向都要跑過不能先break
# flag 紀錄該輪是否可以break (即完全沒有刪除任何一對卡牌)
first = flag = True
while True:
# 橫著跑過每一行
for i, row in enumerate(l):
stk = [] # stack
lv = li = None # 快取stack的最後一項 初始化為sentinel
for j, v in enumerate(row):
if v is None: continue # 已經刪除的空格
if v == lv: # 成功配對
row[li] = row[j] = None # 設定成空格
ans += lv # 更新答案
lv, li = stk.pop()
flag = False # 不能break
else:
stk.append((lv, li))
lv, li = v, j
if flag and not first: break # 第一輪不能break
flag = True
# 豎著跑過每一列 跟上面的差不多
for j, col in enumerate(zip(*l)):
stk = []
lv = li = None # sentinel
for i, v in enumerate(col):
if v is None: continue
if v == lv:
# 這邊不能直接對col賦值 必須用index從l去找
l[li][j] = l[i][j] = None
ans += lv
lv, li = stk.pop()
flag = False
else:
stk.append((lv, li))
lv, li = v, i
if flag: break
first = False
print(ans)
main()
```
6. [m373 投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)
一般的DP，優化的部分在於發現: 如果是連續的正數，DP的結果具有加成性，因此我使用一個變數bonus將連續的正數累加起來，等到遇到負數的時候再一次處理。
最終喜題第二名(不知道第一是怎寫的......)。
```python
# 投資遊戲 - O(nk) O(k) - 0.7sec (second) 13.2mb (TOP)
# https://zerojudge.tw/ShowProblem?problemid=m373
def main():
from sys import stdin
e = stdin.readline
n, k = map(int, e().split())
l = map(int, e().split())
if k == 0: # k = 0 的case獨立出來快速處理
ans = dp = 0
for v in l:
if dp < 0: dp = 0
dp += v
if dp > ans: ans = dp
print(ans)
else:
ans = bonus = 0 # bonus 處理連續正數 可以累積起來直接一起加
# 初始化可以先dp第一輪
d, p = [max(0, next(l))] * (k+1), [0] * (k+1)
for v in l:
if v >= 0: # 正數可以先累積起來
bonus += v
else:
# 更新前一輪答案
ans = max(ans, d[-1] + bonus)
# 第一項處理方式不同
it = enumerate(d)
_, pre = next(it)
# 第一項只有在沒有使用金牌的情況下能加上bonus(因為沒有前一項)
p[0] = max(0, pre + v + bonus)
for i, cur in it:
p[i] = bonus + max(pre, cur + v)
pre = cur
# bonus都加完了 歸零
bonus = 0
d, p = p, d
# 考慮最後一輪的答案 (可能結尾全是正數)
print(max(ans, d[-1] + bonus))
main()
```
7. [搬家](https://zerojudge.tw/ShowProblem?problemid=m372)
參考題解: [併查集](https://www.facebook.com/share/p/45uketa39NLP1LNY/)
一眼就能看出是bfs或dfs的走訪題，比較麻煩的是如何處理水管連接的問題，最簡潔漂亮的解法是用二進位編碼。
而下面的解是與上方或左邊的格子做併查集合併，比單純的走訪稍快。
```python
# 搬家 - O(mnα(mn)) O(mn) - 0.5sec 9.2mb TOP
# https://zerojudge.tw/ShowProblem?problemid=m372
def main():
from sys import stdin
e = stdin.readline
# 轉換表 將水管字元轉換為二進位的標記 各位分別表示 上下左右 是否有接口 (行末的\n作為sentinel)
t = {"F": 5, "H": 3, "7": 6, "I": 12, "X": 15, "L": 9, "J": 10, "0": 0, "\n": 0}
trans = t.get
m, n = map(int, e().split())
# 把圖壓成一維並轉換成接口標記
l = tuple(v for i in range(m) for v in map(trans, e()))
# dsu 正數代表父節點 負數代表該塊面積
dsu = [-1] * (m * (n + 1) - 1)
for i, v in enumerate(l):
if v == 0: continue # 是空格就跳過
# 是否可與上方連接
ra = a = i - n - 1
if 0 <= a and v & 8 == 8 and l[a] & 4 == 4:
pa = dsu[ra]
while pa >= 0:
ra, pa = pa, dsu[pa]
if a != ra: dsu[a] = ra
else:
ra = None
# 是否可與左邊連接
rb = b = i - 1
if v & 2 == 2 and l[i-1] & 1 == 1:
pb = dsu[rb]
while pb >= 0:
rb, pb = pb, dsu[pb]
if b != rb: dsu[b] = rb
else:
rb = None
if ra is None:
if rb is None:
# 上左都不能連 自己當根
continue
else:
# 只有左邊可以連
dsu[i] = rb
dsu[rb] -= 1
else:
if rb is None:
# 只有上面可以連
dsu[i] = ra
dsu[ra] -= 1
else:
# 上左都可以連
if ra == rb:
# 上左本來就是同一塊
dsu[i] = ra
dsu[ra] -= 1
elif pa <= pb:
# 上面的面積比較大 將左邊指向上面
dsu[i] = dsu[rb] = ra
dsu[ra] += pb - 1
else:
# 左邊的面積比較大 將上面指向左邊
dsu[i] = dsu[ra] = rb
dsu[rb] += pa - 1
print(-min(dsu)) # 取面積最大
main()
```
8. [f607 切割費用](https://zerojudge.tw/ShowProblem?problemid=f607)
參考題解: [吳邦一教授提供的三種解法](https://www.facebook.com/share/p/XJtChqyxQgxuSnry/)
解法邏輯的部分看上面的貼文就好了，教授講得很清楚。
- Sol 1
```python
# 切割費用 - O(sort+n) O(n) - 0.5sec 34.2mb TOP
# https://zerojudge.tw/ShowProblem?problemid=f607
def main():
from sys import stdin
e = stdin.readline
n, l = map(int, e().split())
# 將切點依照座標排序
p = sorted(tuple(map(int, e().split())) for i in range(n))
p.append((l, 0)) # 右邊界做為sentinel
ans = 0
stk = [] # 依照切割順序i單調遞增的stack
last_x = last_i = 0 # stk最後一項 初始化為(0, 0)左邊界
append, pop = stk.append, stk.pop
for x, i in p:
while last_i > i:
ans += x # 對於last這個切點 現在的切點是右端點
last_x, last_i = pop()
ans -= last_x # 對於現在的切點 現在的last是左端點
append((last_x, last_i))
last_x, last_i = x, i
print(ans)
main()
```
- Sol 2-1
直接使用bisect.insort當然可以，但O(n)就是慢。
這個解是參考sortedcontainers.SortedList的實作方式，用分塊的方式將插入的複雜度降到理論O(sqrt(n))。
算快了。
```python
# 切割費用 - O(nsqrt(n)) O(n) - 0.8sec 12.9mb
# https://zerojudge.tw/ShowProblem?problemid=f607
"""
使用分塊的邏輯，實作一個簡單的Sorted List
_list: list[list[int]] = 是分塊的list
_max: list[int] = 每一塊的最大值(也就是最後一項) (可以直接對_list每一塊的最後一項二分搜，但一級access比較二級access快，而且3.6.8的bisect沒有key)
MAXLEN: int = isqrt(n/2) * 2 是根據切割次數n的決定的分塊門檻，如果當前的塊比MAXLEN還要大，就把這塊切一半
"""
def main():
from sys import stdin
from bisect import bisect_left
e = stdin.readline
n, l = map(int, e().split())
MAXLEN = int(pow(n >> 1, 0.5)) << 1
x = [None] * n
for i in range(n): # O(n) 根據切點順序排序
a, b = map(int, e().split())
x[b-1] = a
ans = 0
_list = [[0, l]]
_max = [l]
for v in x:
# 二分搜找塊
b = bisect_left(_max, v)
block = _list[b]
# 二分搜找值
i = bisect_left(block, v)
# 計算答案(該段長度) 如果前一項超出這塊就去前一塊的最後一項找
ans += block[i] - (block[i-1] if i > 0 else _list[b-1][-1])
# 插入新切點
block.insert(i, v)
# 更新該塊最大值
_max[b] = max(_max[b], v)
# 如果長度超過MAXLEN
_len = len(block)
if _len > MAXLEN:
# 切一半
idx = _len >> 1
half = block[idx:]
del block[idx:]
_max[b] = block[-1]
# 插入後半塊
_list.insert(b+1, half)
_max.insert(b+1, half[-1])
print(ans)
main()
```
- Sol 2-2
把最近刻的一棵AVL平衡樹砍掉一些功能直接拿來用，理論時間複雜度比上面的分塊還要好，但常數太大所以被TLE了。
參考著看就好，但我自認為這棵樹以first-try來講算是挺好看的了。
```python
# 切割費用 - O(nlogn) O(n) - AC50% TLE50%
# https://zerojudge.tw/ShowProblem?problemid=f607
def main():
from sys import stdin
e = stdin.readline
class TreeNode:
def __init__(self, val=None, pa=None, le=None, ri=None, hei=1):
self.val, self.pa, self.le, self.ri, self.hei = val, pa, le, ri, hei
class AVLTree:
def __init__(self) -> None:
self.root = TreeNode()
def insert(self, val) -> TreeNode:
root = self.root
node = root.le
if node is None: # first node
res = root.le = TreeNode(val, root)
return res
while True:
if val < node.val:
le = node.le
if le is None:
res = node.le = TreeNode(val, node)
self.balance(node)
return res
else:
node = le
else:
ri = node.ri
if ri is None:
res = node.ri = TreeNode(val, node)
self.balance(node)
return res
else:
node = ri
def leftmost_greater(self, val) -> TreeNode:
node = self.root.le
res = None
while node is not None:
if val < node.val:
res = node
node = node.le
else:
node = node.ri
return res
def rightmost_lower(self, val) -> TreeNode:
node = self.root.le
res = None
while node is not None:
if node.val < val:
res = node
node = node.ri
else:
node = node.le
return res
def balance(self, node) -> None:
root = self.root
get_bf = self.get_bf
get_child_hei = self.get_child_hei
L, R = self.L_rotate, self.R_rotate
while node is not root:
bf = get_bf(node)
if bf > 1:
le = node.le
lh, rh = get_child_hei(le)
if lh > rh: # RR
R(node)
else: # LR
L(le)
R(node)
elif bf < -1:
ri = node.ri
lh, rh = get_child_hei(ri)
if lh < rh: # LL
L(node)
else: # RL
R(ri)
L(node)
node = node.pa
@staticmethod
def get_child_hei(node) -> tuple:
le, ri = node.le, node.ri
return (le.hei if le is not None else 0,
ri.hei if ri is not None else 0)
def get_bf(self, node) -> int:
lh, rh = self.get_child_hei(node)
node.hei = 1 + max(lh, rh)
bf = lh - rh
return bf
def R_rotate(self, node) -> None:
get_bf = self.get_bf
le = node.le
ri = le.ri
pa = node.pa
# node.pa -- node.le
if pa.le is node:
pa.le = le
else:
pa.ri = le
le.pa = pa
# node.le -- node -- node.le.ri
le.ri = node
node.pa = le
node.le = ri
if ri is not None: ri.pa = node
# update height
get_bf(node)
get_bf(le)
def L_rotate(self, node) -> None:
get_bf = self.get_bf
ri = node.ri
le = ri.le
pa = node.pa
# node.pa -- node.ri
if pa.le is node:
pa.le = ri
else:
pa.ri = ri
ri.pa = pa
# node.ri -- node -- node.ri.le
ri.le = node
node.pa = ri
node.ri = le
if le is not None: le.pa = node
# update height
get_bf(node)
get_bf(ri)
# ===============
# 主程式從這裡開始 |
# ===============
n, l = map(int, e().split())
x = [None] * n
for i in range(n): # O(n) 根據切點順序排序
a, b = map(int, e().split())
x[b-1] = a
tree = AVLTree()
insert, rl, lg = tree.insert, tree.rightmost_lower, tree.leftmost_greater
insert(0) ; insert(l) # 初始化加入左右邊界
ans = 0
for v in x:
# 尋找最靠近的左右切點
le, ri = rl(v).val, lg(v).val
ans += ri - le
# 加入當前切點
insert(v)
print(ans)
main()
```
- Sol 3
這個解是倒序地將木棍黏起來，十分反直覺而無比精妙。
```python
# 切割費用 - O(sort+n) O(n) - 0.7sec 69.5mb
# https://zerojudge.tw/ShowProblem?problemid=f607
def main():
from sys import stdin
e = stdin.readline
n, l = map(int, e().split())
# 將切點依照位置排序
p = sorted(tuple(map(int, e().split())) for i in range(n))
# 將切點依照切割順序倒序排序
rev = [None] * n
for idx, (_, i) in enumerate(p):
rev[-i] = idx
# 加上左右端點做為sentinel
p.extend(((l, 0), (0, 0)))
ans = 0
# double linked list的概念
link = [[i-1, i+1] for i in range(n+2)]
for idx in rev:
# 找左右端點
le, ri = link[idx]
ans += p[ri][0] - p[le][0]
# 將該切點左右的木棍黏起來
link[le][1] = ri
link[ri][0] = le
print(ans)
main()
```
9. 階梯數字
這題是我最喜歡也最有成就感的一題。
看題目可以很明顯地看出解法就是建表查值的digit DP，建一次表的時間O(digit)，當然也可以優化空間到常數O(10)。
然而稍微觀察一下轉移式就會發現: 1.可以只在數字上升的地方查值 2.轉移式可以寫成轉移矩陣。原本想說建表的部分說不定能夠直接推出公式變成O(1)，但因為該位是0和1~9的情況不一樣，所以只能夠用矩陣乘法快速冪變成O(log digit) (數字上升點必小於10次，加上sentinel也最多10幾次，視為常數)，儘管時間複雜度受到尋找上升點部分的限制，必須要O(digit)，但尋找上升點的常數很小，所以效率很高。
最終將時間推進到0.1sec，和第二名0.3sec、第三名0.7sec拉開龐大差距。
(說實話Sol 3的寫法還能再繼續優化，但為了可讀性就先暫時這樣吧!)
- Sol 1: 普通作法 (但將表壓成一維)
```python
# 階梯數字 - O(t*digit) O(digit) - 0.7sec 44.4mb (second place)
# https://zerojudge.tw/ShowProblem?problemid=c543
def main():
from sys import stdin, stdout
from itertools import islice
mod = 1000000007
# 一次性讀入所有數字
l = list(tuple(map(int, e.strip())) for e in stdin)
# 找出最長的數字，dp到該位數+1
n = max(map(len, l))
# 建表
dp = [1] * 10 * (n+1) # 二維表壓成一維表 初始化為1
dp[0] = 0 # dp[0][0] = 0
it_dp, it_idx = iter(dp), iter(range(10, len(dp)))
for _ in range(n):
s = 0
# 取10個為一行，並將該行倒序，再做前綴和
group, idx = reversed(tuple(islice(it_dp, 10))), reversed(tuple(islice(it_idx, 10)))
for v, i in zip(group, idx):
dp[i] = s = (s + v) % mod
# 求值
for i, num in enumerate(l):
s = last = 0 # last儲存上一位數字
for idx, digit in zip(range(len(num) * 10, -1, -10), num):
if last > digit: break # 數字變小，直接跳出
if last == digit: continue # 數字一樣不用加
s = (s + dp[idx+last] - dp[idx+digit]) % mod
last = digit
else:
# 自己也是階梯數字，加上去
s = (s + 1) % mod
l[i] = str(s)
stdout.write("\n".join(l))
main()
```
- Sol 2: 常數空間
```python
# 階梯數字 - O(t*digit) O(1) - 0.8sec 4.2mb (memory TOP)
# https://zerojudge.tw/ShowProblem?problemid=c543
def main():
from sys import stdin, stdout
from itertools import zip_longest
mod = 1000000007
# 一次性讀入所有數字並反轉，從個位數開始dp
l = tuple(map(int, reversed("0" + e.strip())) for e in stdin)
# 滾輪dp 空間O(10)
d, p = [0] * 10, [0] * 10
# 一些神奇的初始化
d[0] = -1
d[-1] = p[-1] = 1
ans = [0] * len(l) # 答案
last = [9] * len(l) # 上一位數字
flag = [True] * len(l) # 本身是否為階梯數字
for idx, digits in enumerate(zip_longest(*l)):
# 計算新的一排dp
s = 1
for i in range(8, -1, -1):
p[i] = s = (s + d[i]) % mod
# 對每個數字查值
for i, (pre, digit) in enumerate(zip(last, digits)):
if digit is None: continue
if digit > pre: # 左邊比右邊大
# 本身不是階梯數字
flag[i] = False
# 重置答案
ans[i] = 0
elif digit < pre:
ans[i] = (ans[i] + p[digit] - p[pre]) % mod
last[i] = digit
d, p = p, d
# 列印答案，如果本身是階梯數字就加上去
stdout.write("\n".join(str((i + 1) % mod) if f else str(i) for i, f in zip(ans, flag)))
main()
```
- Sol 3: 矩陣乘法快速冪
```python
# 階梯數字 - O(t*digit) O(t) - 0.1sec (TOP) 9mb (second place)
# https://zerojudge.tw/ShowProblem?problemid=c543
def main():
from sys import stdin, stdout
mod = 1000000007
# 快取乘法函式
mul = int.__mul__
# 矩陣轉移式
mat = tuple(
(1,) * (i + 1) + (0,) * (9 - i) for i in range(10)
)
# one-liner 矩陣乘法
def matmul(a, b):
return tuple(
tuple(sum(map(mul, row, col)) % mod
for col in zip(*b))
for row in a
)
# 一次性讀入所有數字
l = [tuple(map(int, e.strip())) for e in stdin]
for idx, num in enumerate(l):
n = len(num)
last_digit = 0
# 紀錄每一個數字的"位數上升點"，維護digit嚴格上升，故len(new)為常數
new = l[idx] = [(n, 0)]
for i, digit in enumerate(num, start=1):
if digit < last_digit: break # 此數字不是階梯數字
if digit == last_digit:
# 此位數和前一位一樣，替換掉
new.pop()
# 新增上升點
new.append((n - i, digit))
last_digit = digit
else:
# 此數字是階梯數字狀態下的sentinel
new.append((-1, 9))
for idx, num in enumerate(l):
# 初始化矩陣 這是dp[-1]的狀態
d = ((-1, ) + (0, ) * 8 + (1, ), )
# 將上升點倒序再做dp
rev = reversed(num)
last_i, last_digit = next(rev)
n = last_i + 1 # 原意是 last_i - (-1)，也就是計算從dp[-1]轉移到初始化狀態，需要乘幾個轉移矩陣
if n == 0: # 也代表此數字本身是階梯數字 先把自己加入所求
ans = 1
else: # 快速冪到初始狀態
ans = 0
p = mat
while n > 1:
if n & 1:
d = matmul(d, p)
p = matmul(p, p)
n >>= 1
d = matmul(d, p)
for i, digit in rev:
# 從上一個上升點快速冪到下一個
n = i - last_i
p = mat
while n > 1:
if n & 1:
d = matmul(d, p)
p = matmul(p, p)
n >>= 1
d = matmul(d, p)
# 計算所求
dp = d[0]
ans = (ans + dp[digit] - dp[last_digit]) % mod
last_i, last_digit = i, digit
l[idx] = str(ans)
stdout.write("\n".join(l))
main()
```
> 事先澄清，以上三解的成績紀錄止於2024/7/13之前。
為了閱讀的邏輯連貫性，就不將舊紀錄刪除，以下是7/13以後的更新及優化。
一點意外的驚喜，又將此題在我心中的印象有了更豐富的色彩。
先說個小故事，2024/7/13 我剛拿到虎尾科大python勁程比賽的冠軍(這是另一篇學習歷程)，在高鐵站等著回家。沒事刷刷APCS模擬測驗團隊的訊息，發現有人(網名sheep)提問此題，我稍微看了一下他的程式，是使用Top-down遞迴DP + memory的寫法，我於是和他分享我寫的以上三種解法，隨後他的程式忽然就過了(23ms)，我又仔細閱讀了一下他的程式，發現了一個函式裡出現了各種階乘的運算，在加總答案時還做了一個`if digit == 0: dp -= 1`的判斷，讓我頓時靈光一現，上面原本寫到: 如果該位數字是0的時候，會和其他位不一樣，因此無法直接公式解，我卻是被"一個通式涵蓋整個表"的固有意識箝制，忽略了這樣簡單的一行條件判斷就能解決的問題，多參考他人的idea真的很重要!
在修改程式的時候我又發現了一個看似合理卻極大拖慢執行速度的真兇── `[tuple(map(int, e.strip())) for e in stdin]`，這一行程式把每個數字都讀入並一位一位拆開轉成int再放進一個tuple，方便後面讀值，但這樣就一定會跑滿10000位，更好的方式是直接遍歷輸入的原始字串，遍歷時將該位數字從str轉成int。光是這項改動就使原本0.1sec的Sol3躍升到43ms。
接下來我解釋一下如何使用數學的排列組合在O(1)時間內進行單次查值。
首先複習一下，參照Sol1中DP表的定義: `DP[i][digit] = 以digit為最高位數的i+1位數中，總共有幾個階梯數字?`，根據階梯數字的定義，符合條件的`i+1`位數必須呈現遞增，因此他的後`i`個位數都應該 `>= digit`，也就是說後`i`個位數的取值範圍是`[digit, 9]`，取完後遞增排列。以這樣的邏輯我們就可以推得`DP[i][digit] = h(9 - digit + 1, i)`，其中h是排列組合中的重複組合。
至於前面提到的0的問題，原本我是在查值的時候考慮`digit == 0`時dp值要減一，但這種情況只會出現在首位(也就是最高位)，觀察到最後如果是階梯數字就要將所求加一，於是稍微置換步驟，不考慮`digit == 0`，而是在發現此數字不是階梯數字的時候，break迴圈同時將所求減一。
最後執行時間來到19ms，第一名18ms是sheep。
- Sol 4: 使用重複組合O(1)查值
計算h的時會需要除法，但不能先取模再做除法，因此我使用0!~9!的模逆元，直接建表。
```python
def main():
from sys import stdin
mod = 1000000007
def dp(pos, digit):
# dp(pos, digit) = h(9 - digit + 1, pos)
res = rev_fac[~digit]
for i in range(pos + 1, pos + 10 - digit):
res *= i
return res % mod
# 0! ~ 9! 的模逆元
rev_fac = (1, 1, 500000004, 166666668, 41666667, 808333339, 301388891, 900198419, 487524805, 831947206)
for num in map(str.strip, stdin):
ans = last = 0
n = len(num)
for i, cur in zip(range(n, 0, -1), map(int, num)):
if cur < last:
# 此數字不是階梯數字
ans -= 1
break
if cur > last:
# 遇到上升點 查值一次
ans += dp(i, last) - dp(i, cur)
last = cur
print(ans % mod)
main()
```
- Sol 5: 使用分配律減少乘法次數
```python
def main():
from sys import stdin
mod = 1000000007
# 0! ~ 9! 的模逆元
rev_fac = (1, 1, 500000004, 166666668, 41666667, 808333339, 301388891, 900198419, 487524805, 831947206)
for num in map(str.strip, stdin):
ans = last = 0
n = len(num)
for i, cur in zip(range(n, 0, -1), map(int, num)):
if cur < last:
# 此數字不是階梯數字
ans -= 1
break
if cur > last:
# 遇到上升點 查值一次
# 分兩段連乘
a = 1
if cur == 9:
x = i
else:
for x in range(i + 1, i + 10 - cur):
a *= x
b = 1
for x in range(x + 1, i + 10 - last):
b *= x
# 分配律
ans += a * (b * rev_fac[~last] - rev_fac[~cur]) % mod
last = cur
print(ans % mod)
main()
```
- Sol 6: 一行解壓軸
理論上有更好的寫法，但為了殘存的可讀性 ~~還有我的肝~~，這樣就好了。
```python
# 一行解
(lambda sys, mod, rev_fac: print(*((sum((lambda func: (rev_fac[~last] * func(i + 1, i + 10 - last, func) - rev_fac[~cur] * func(i + 1, i + 10 - cur, func)) % mod)(lambda s, t, self: (s * self(s + 1, t, self)) if s < t else 1) for i, cur, last, _ in zip(range(len(num), 0, -1), map(int, num), map(int, "0" + num), iter((v <= num[i] for i, v in enumerate("0" + num[:-1])).__next__, False)) if cur > last) - any(v > num[i] for i, v in enumerate("0" + num[:-1]))) % mod for num in map(str.strip, sys.stdin)), sep="\n"))(__builtins__.__dict__["__import__"]("sys"), 1000000007, (1, 1, 500000004, 166666668, 41666667, 808333339, 301388891, 900198419, 487524805, 831947206))
# 拆解 + 註解
((lambda sys, mod, rev_fac:
print(
*(
(
sum(
# 求值 實際呼叫func函數遞迴乘法
(lambda func: (rev_fac[~last] * func(i + 1, i + 10 - last, func) - rev_fac[~cur] * func(i + 1, i + 10 - cur, func)) % mod)
# 定義遞迴連乘函數func
(lambda s, t, self: (s * self(s + 1, t, self)) if s < t else 1)
# 主迴圈
for i, cur, last, _ in zip(
range(len(num), 0, -1),
map(int, num),
map(int, "0" + num),
# 用來判斷不為階梯數字 break迴圈
iter((v <= num[i] for i, v in enumerate("0" + num[:-1])).__next__, False)
)
if cur > last
) - any(v > num[i] for i, v in enumerate("0" + num[:-1])) # 如果本身不是階梯數字要 - 1
) % mod
for num in map(str.strip, sys.stdin # 讀入每一筆測資 去掉結尾\n
)
),
sep="\n" # 將輸入的每筆測資分行輸出
))
(
__builtins__.__dict__["__import__"]("sys"), # import sys (直接__import__會被judge擋)
1000000007, # 題目給的mod數
(1, 1, 500000004, 166666668, 41666667, 808333339, 301388891, 900198419, 487524805, 831947206) # 0! ~ 9! 的模逆元
))
```
## 6. 反思與收穫
### 6.1 學習過程中的挑戰
1. 思維培養：從基礎的程式編寫到複雜算法的理解和實現，需要不斷提升抽象思考的能力。
2. 原理探討：在保證程式正確性的同時追求極致的運行效率，需要初步理解Python的底層機制，對於長年耽溺於高階語言舒適圈的我來說，有點冒險也有點新鮮。
3. 時間管理：在高中繁重的學業與補習和APCS的學習與練習之間找到平衡，需要良好的自制力和規劃能力。
### 6.2 關鍵收穫
1. 程式設計能力的全面提升：從基礎語法到高階演算法，建立了系統化的知識體系。
2. 問題解決能力的增強：通過不斷挑戰自己，培養了面對複雜問題的解決能力。
3. 優化思維的形成：學會了如何從多個角度思考問題，追求最優解。
4. 自學能力的提升：通過自主學習APCS，培養了獨立學習和研究的能力。
5. 紀錄學習軌跡：藉由撰寫詳細的註解和記錄各版本程式，見證自我的進步與成長，也能將題解公開給大眾，造福後輩。
### 6.3 對未來學習和職涯的影響
1. 堅定繼續於資訊領域深造的決心。
2. 為未來參與更高層次的程式設計競賽打下基礎。
3. 培養對軟體效能與複雜度估算的敏感度，為未來可能從事的軟體開發工作做好準備。
## 7. 結論
### 7.1 學習歷程總結
通過系統性地學習和準備APCS，我不僅掌握了扎實的程式設計基礎，還磨練了解決複雜問題的能力和突破頂峰的精神。這段經歷不僅提升了我的技術能力，也培養了我面對挑戰的態度。
### 7.2 未來學習計劃
1. 繼續深入學習更專業的演算法和資料結構。
2. 學習其他程式語言，例如C++或Rust，拓展技術視野。
3. 參與更多程式設計競賽，挑戰自己的極限。
4. 開始涉獵實際的軟體開發項目，將所學知識應用於實踐。
這份APCS學習歷程不僅記錄了我的成長軌跡，也為我的未來指明了方向。我期待在計算機科學的道路上繼續探索，為未來的學習和職業生涯鋪下穩健的康莊大道。
## 8. 附錄
[APCS考古題 初見](https://colab.research.google.com/drive/1iMx7fCiWYetZDs7Gob0ZlUm2oR0iAdXq?hl=en) (註解十分奔放 請包容熬夜的精神狀態)
[APCS考古題 優化](https://colab.research.google.com/drive/1jnX4JvDWejyQxpHHfX_EsA0_Hx0ENaiy?hl=en) (這個比較正經)
[此篇學習歷程的小前身](https://www.facebook.com/share/p/Zcrk2fsrbf9eqTBM/)
> 感謝閱讀至此，辛苦了(ʘᴗʘ✿)。
Sign in with Wallet
Connect another wallet