ZeroJudge 解題筆記：c001. 10405 - Longest Common Subsequence

作者：王一哲
日期：2026年1月21日


ZeroJudge 題目連結：c001. 10405 - Longest Common Subsequence

解題想法

只要找最長共同子序列 (longest common subsequence, LCS) 的長度，用二維串列 dp 儲存兩個字串 s, t 的第 i 個、第 j 個字母對應的 LCS 長度。

Python 程式碼

使用時間約為 24 ms，記憶體約為 3 MB，通過測試。

import sys

def length_LCS(s, t):
    m, n = len(s), len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    a = lines[idx].strip()
    idx += 1
    b = lines[idx].strip()
    idx += 1
    ans = length_LCS(a, b)
    result.append(f"{ans:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：b917. 11059 Maximum Product

作者：王一哲
日期：2026年1月20日


ZeroJudge 題目連結：b917. 11059 Maximum Product

解題想法

這題用兩層 for 迴圈硬算，假設要測試的數字存在串列 $nums$，依序測試從 $nums[i]$ 為首項，再乘以 $nums[j], (j < i)$ 到 $nums[-1]$，每次乘完之後更新最大值。時間複雜度約為 $O(n^2)$，可以通過測試。反而是輸出格式要小心，每一行測資對應的結果底下都要印出一行空行。

Python 程式碼

使用時間約為 9 ms，記憶體約為 2.9 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
ca = 0
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    ca += 1
    n = int(lines[idx])
    idx += 1
    nums = list(map(int, lines[idx].split()))
    idx += 1
    imax = 0
    for i in range(n):
        curr = 1
        for j in range(i, n):
            curr *= nums[j]
            imax = max(imax, curr)
    result.append(f"Case #{ca:d}: The maximum product is {imax:d}.\n\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：b587. 10918 - Tri Tiling

作者：王一哲
日期：2026年1月19日


ZeroJudge 題目連結：b587. 10918 - Tri Tiling

解題想法

因為地板的尺寸為 $3 \times n$，要放入的地板磚尺寸為 $1 \times 2$，如果 $n$ 為奇數時無解。接下來列出 $n$ 的前幾項可能的拼法，例如 $n = 2$ 有 3 種

AA   AB   CC
BB   AB   AB
CC   CC   AB

如果以 $dp[n]$ 代表地板尺寸為 $3 \times n$ 的拼法數量，其中 $dp[0] = 1$，因為沒有放置地板算 1 種；$dp[2] = 3$，像是上面的例子；接下來推算 $n \geq 4$ 的狀況。 狀況1，如果最右側是完整的 $3 \times 2$，這個部分有 3 種拼法，左側的拼法為 $dp[n-2]$，因此 $dp[n] = 3 \times dp[n-2]$。 狀況2，如果最右側不是完整的 $3 \times 2$，先列出 $$ dp[n] = 3 \times dp[n-2] + 2 \times (dp[n-4] + dp[n-6] + \dots + dp[0]) $$ 再列出 $$ dp[n-2] = 3 \times dp[n-4] + 2 \times (dp[n-6] + dp[n-8] + \dots + dp[0]) $$ 將兩式相減 $$ dp[n] - dp[n-2] = 3 \times dp[n-2] - dp[n-4] $$ 移項後得到 $$ dp[n] = 4 \times dp[n-2] - dp[n-4] $$

Python 程式碼

使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def solve(n):
    if n == 0: return 1
    if n == 2: return 3
    if n%2 == 1: return 0
    dp = [0]*(n+1)
    dp[0] = 1; dp[2] = 3
    for i in range(4, n+1, 2):
        dp[i] = 4*dp[i-2] - dp[i-4]
    return dp[n]

for line in sys.stdin:
    n = int(line)
    if n == -1: break
    print(solve(n))

ZeroJudge 解題筆記：b304. 00673 - Parentheses Balance

作者：王一哲
日期：2026年1月18日


ZeroJudge 題目連結：b304. 00673 - Parentheses Balance

解題想法

先用字典儲存 3 種右括號對應的左括號，這樣在檢查括號是否成對時比較方便。先讀取一行測資，再依序讀取這行測資中的每個字元，如果是左括號就存入堆疊 st 之中，如果讀到右括號，檢查堆疊最上面是否為對應的左括號，如果成對就移除這筆資料，如果堆疊是空的或不是對應的左括號，無解，中止迴圈。最後再檢查堆疊是否還有資料，如果有，無解。

Python 程式碼

使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

left = {')': '(', ']': '['}  # 左、右括號配對
n = int(input())  # n 組測資
for _ in range(n):  # 執行 n 次
    s = list(input())  # 字串轉成串列
    st = []  # 左括號堆疊
    flag = True  # 是否有解
    for c in s:  # 依序由 s 讀取字元 c
        if c in "([": st.append(c)  # 如果 c 是左括號放入堆疊
        else:  # 反之為右括號
            if not st or st[-1] != left[c]:  # 如果 st 是空的或是最後一項無法與 c 配對
                flag = False  # 無解
                break  # 中止迴圈
            else: st.pop() # 有解，移除 st 最後一項
    if st: flag = False  # 如果有剩下的左括號，無解
    print("Yes" if flag else "No")

ZeroJudge 解題筆記：a743. 10420 - List of Conquests

作者：王一哲
日期：2026年1月17日


ZeroJudge 題目連結：a743. 10420 - List of Conquests

解題想法

這題用 map 及 set 儲存各國家的人名，讀取所有的測資之後，再將國家及人名數量組成 tuple 存入另一個 list 之中，將 list 依照人名數量由小到大排序，如果數量相同再依照國家名稱排序。

Python 程式碼

使用時間約為 23 ms，記憶體約為 4.2 MB，通過測試。

from collections import defaultdict

n = int(input())
cnt = defaultdict(set)
for _ in range(n):
    country, name = list(input().split(" ", 1))  # 用空格分格，只切一次
    cnt[country].add(name)
ans = sorted([(k, len(v)) for k, v in cnt.items()])
for a in ans: print(*a)

ZeroJudge 解題筆記：a741. 10101 - Bangla Numbers

作者：王一哲
日期：2026年1月16日


ZeroJudge 題目連結：a741. 10101 - Bangla Numbers

解題想法

用自訂函式 convert，將輸入的整數 n 轉換成題目要的字串。先處理 $n = 0$ 的特例，直接回傳字串 0。如果 $n > 1000000000$，需要先處理這部分的係數，也就是 kuti 的數量。接下來再依序處理 lakh, hajar, shata 的數量。

Python 程式碼

使用時間約為 30 ms，記憶體約為 5.8 MB，通過測試。

import sys

def convert(n):  # 輸入數字 n，輸出答案字串
    if n == 0: return "0"  # 特例，直接回傳 0
    unit = (10000000, 100000, 1000, 100)
    word = ("kuti", "lakh", "hajar", "shata")
    result = []  # 儲存答案用的串列，內容為 [數量, 單位, ...]
    if n > 1000000000:  # 前面的位數可以再細分
        left = n // 10000000  # 前面的位數，上限為 99999999
        n %= 10000000  # 剩下的位數
        for u, w in zip(unit, word):
            r = left // u  # 取這個單位對應的數量
            if r > 0: result += [str(r), w]  # r 大於 0，r 轉成字串，r, w 加到 result
            left %= u  # left 取餘數
        if left > 0: result.append(str(left))  # 剩下的位數
        result.append("kuti")  # 前面整串代表 kuti 的數量
    for u, w in zip(unit, word):  # 由大到小讀取單位對應的數值、字串
        r = n // u  # 取這個單位對應的數量
        if r > 0: result += [str(r), w]  # r 大於 0，r 轉成字串，r, w 加到 result
        n %= u  # n 取餘數
    if n > 0: result.append(str(n))  # 如果有小於 100 的值，加到 result
    return " ".join(result)  # 用空格接成字串再回傳

result = []
lines = sys.stdin.readlines()  # 讀取所有測資
idx = 0
while idx < len(lines):
    n = int(lines[idx])
    idx += 1
    result.append(f"{idx:3d}. {convert(n):s}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a676. 00111 - History Grading

作者：王一哲
日期：2026年1月15日


ZeroJudge 題目連結：a676. 00111 - History Grading

解題想法

寫法1，找正確的事件編號排序與學生作答的編號排序最長共同子序列長度 (longest common subsecquence, LCS)。寫法2，找最長遞增子序列 (longest increasing subsecquence, LCS)。

Python 程式碼

使用時間約為 0.9 s，記憶體約為 4.7 MB，通過測試。

import sys

def length_LCS(a, b):  # 輸入串列 a, b，回傳 LCS 長度
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

n = int(input())  # n 個事件
ans = [0]*n  # 事件編號正確的排序
for i, a in enumerate(map(int, input().split()), start=1): ans[a-1] = i
for line in sys.stdin:  # 讀取學生的答案
    stu = [0]*n  # 學生回答的事件編號排序
    for i, a in enumerate(map(int, line.split()), start=1): stu[a-1] = i
    print(length_LCS(ans, stu))  # 找 ans, stu 的 LCS 長度

使用時間約為 0.2 s，記憶體約為 4.7 MB，通過測試。

import sys
from bisect import bisect_left

def length_LIS(nums):  # 找最長遞增子序列長度
    tails = []
    for num in nums:
        idx = bisect_left(tails, num)
        if idx == len(tails): tails.append(num)
        else: tails[idx] = num
    return len(tails)

n = int(input())  # n 個事件
ans = dict()  # 事件編號: 正確排序的索引值
for i, a in enumerate(map(int, input().split()), start=1): ans[i] = a-1
for line in sys.stdin:  # 讀取學生的答案
    stu = [0]*n  # 學生回答的事件編號換成正確答案對應的索引值，如果全對為 0, 1, ..., n-1
    for i, a in enumerate(map(int, line.split()), start=1): stu[a-1] = ans[i]
    print(length_LIS(stu))

ZeroJudge 解題筆記：a674. 10048 - Audiophobia

作者：王一哲
日期：2026年1月14日


ZeroJudge 題目連結：a674. 10048 - Audiophobia

解題想法

這題考 Floyd-Warshall 演算法。

Python 程式碼

使用時間約為 0.4 s，記憶體約為 3.8 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
ca = 0  # case number
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    if lines[idx].strip() == "0 0 0":
        break
    C, S, Q = map(int, lines[idx].split())
    idx += 1
    ca += 1
    if result:  # 如果 result 已經有內容，先換行
        result.append("\n")
    result.append(f"Case #{ca:d}\n")
    # 建立儲存節點 u 到 v 噪音值的接鄰矩陣，預設為無窮大，代表不連通
    cost = [[float('inf')]*(C+1) for _ in range(C+1)]
    for i in range(C+1):  # 同一個節點成本為 0
        cost[i][i] = 0
    for _ in range(S):  # 節點 u 到 v 成本
        u, v, d = map(int, lines[idx].split())
        idx += 1
        cost[u][v] = d
        cost[v][u] = d
    # Floyd-Warshall 演算法，以 k 為中繼點，從 i 到 j 的最大噪音值
    for k in range(1, C+1):
        for i in range(1, C+1):
            for j in range(1, C+1):
                if cost[i][k] != float('inf') and cost[k][j] != float('inf'):
                    if cost[i][j] > max(cost[i][k], cost[k][j]):
                        cost[i][j] = max(cost[i][k], cost[k][j])
    # Q 次查詢
    for _ in range(Q):
        u, v = map(int, lines[idx].split())
        idx += 1
        if cost[u][v] == float('inf'):
            result.append("no path\n")
        else:
            result.append(f"{cost[u][v]:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a673. 10026 - Shoemaker's Problem

作者：王一哲
日期：2026年1月13日


ZeroJudge 題目連結：a673. 10026 - Shoemaker's Problem

解題想法

先依照每日平均罰款金額由大到小排序，如果相同再依照讀取順序排序。

Python 程式碼

由於這題的測資有許多的空行，用 Python 解題時需要適時地跳過這些空行，導致以下的程式碼有些複雜。使用時間約為 8 ms，記憶體約為 3.3 MB，通過測試。

import sys

lines = sys.stdin.read().split('\n')
M = len(lines)
head = 0
T = int(lines[head])
head += 1
first_case = True

while T > 0:
    while head < M and lines[head].strip() == "": head += 1
    if head >= M: break
    N = int(lines[head])
    head += 1
    jobs = []
    for i in range(1, N+1):
        day, fine = map(int, lines[head].split())
        head += 1
        jobs.append((day, fine, i))
    jobs.sort(key = lambda x : (-(x[1]/x[0]), x[2]))
    if not first_case: print()
    print(" ".join([str(i) for _, _, i in jobs]))
    first_case = False
    T -= 1

改用 sys.stdin.read().split() 及 iter 可以讓程式碼比較簡潔，但是速度上反而慢了一點。使用時間約為 14 ms，記憶體約為 3.3 MB，通過測試。

import sys

result = []
lines = iter(sys.stdin.read().split())
T = int(next(lines))

for _ in range(T):
    N = int(next(lines))
    jobs = []
    for i in range(1, N+1):
        day = int(next(lines))
        fine = int(next(lines))
        jobs.append((day, fine, i))
    jobs.sort(key = lambda x : (-(x[1]/x[0]), x[2]))
    if result:  # 如果 result 已經有內容，先換行
        result.append("\n")
    res = " ".join([str(i) for _, _, i in jobs])
    result.append(f"{res}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a672. 00155 - All Squares

作者：王一哲
日期：2026年1月12日


ZeroJudge 題目連結：a672. 00155 - All Squares

解題想法

因為以大小為 $k$ 的正方形頂點向外擴張最大範圍為 $$ k_{max} = k + (k-2) + (k-4) + \dots + 1 = \frac{(k+1)^2}{4} $$ 如果 $(x, y)$ 在四個頂點 $\pm k_{max}$ 以外的範圍，可以不需要再加到堆疊之中，可以少算很多次。

Python 程式碼

使用時間約為 35 ms，記憶體約為 3.4 MB，通過測試。

import sys

def count_squares(k, x, y):  # 輸入大小 k，要找的點座標 (x, y)
    cnt = 0  # (x, y) 被幾個正方形包圍
    st = [(k, 1024, 1024)]  # 要計算的正方形大小、中心位置
    while st:  # 如果 st 還有資料繼續執行
        kc, xc, yc = st.pop()  # 目前的正方形大小、中心位置
        left, right = xc-kc, xc+kc  # 左、右頂點位置
        top, bottom = yc-kc, yc+kc  # 上、下頂點位置
        if left <= x <= right and top <= y <= bottom:  # (x, y) 在這個正方形之中
            cnt += 1  # cnt 加 1
        kn = kc//2  # 下一個正方形的大小
        if kn >= 1:  # 下一個正方形的中心
            kmax = (kc+1)*(kc+1)//4  # 以這個正方形頂點向外擴張的上限，公差為 2 的等差級數
            if left-kmax <= x <= left+kmax and top-kmax <= y <= top+kmax: st.append((kn, left, top))
            if left-kmax <= x <= left+kmax and bottom-kmax <= y <= bottom+kmax: st.append((kn, left, bottom))
            if right-kmax <= x <= right+kmax and top-kmax <= y <= top+kmax: st.append((kn, right, top))
            if right-kmax <= x <= right+kmax and bottom-kmax <= y <= bottom+kmax:st.append((kn, right, bottom))
    return cnt  # 回傳數量

for line in sys.stdin:
    k, x, y = map(int, line.split())
    if k == 0 and x == 0 and y == 0: continue
    print(f"{count_squares(k, x, y):3d}")

ZeroJudge 解題筆記：a540. 10684 - The jackpot

作者：王一哲
日期：2026年1月11日


ZeroJudge 題目連結：a540. 10684 - The jackpot

解題想法

這題考 Kadane's Algorithm，詳細的說明可以參考這篇 Maximum Subarray Sum - Kadane's Algorithm。

Python 程式碼

使用時間約為 25 ms，記憶體約為 4 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    n = int(lines[idx])
    idx += 1
    if n == 0: break
    nums = list(map(int, lines[idx].split()))
    idx += 1
    curr = imax = nums[0]
    for num in nums[1:]:
        # 如果用前面累積的值加上 num 較大，取這個值，反之取 num 重新開始
        curr = max(num, curr + num)
        imax = max(imax, curr)
    if imax > 0:
        result.append(f"The maximum winning streak is {imax:d}.\n")
    else:
        result.append("Losing streak.\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a539. 10327 - Flip Sort

作者：王一哲
日期：2026年1月10日


ZeroJudge 題目連結：a539. 10327 - Flip Sort

解題想法

看起來像是考氣泡排序，但是不能直接跑氣泡排序並計算交換次數，這樣會很慢。從最後一個數字往前找，計算這個數字之前有幾個比較大的數字，將數量相加就是答案。

Python 程式碼

使用時間約為 38 ms，記憶體約為 3.2 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    n = int(lines[idx])
    idx += 1
    arr = list(map(int, lines[idx].split()))
    idx += 1
    cnt = 0
    for i in range(n-1, 0, -1):
        for j in range(i-1, -1, -1):
            if arr[i] < arr[j]:
                cnt += 1
    result.append(f"Minimum exchange operations : {cnt:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a537. 10789 - Prime Frequency

作者：王一哲
日期：2026年1月9日


ZeroJudge 題目連結：a537. 10789 - Prime Frequency

解題想法

先用埃拉托斯特尼篩法建立 0 到 2000 之間的質數篩選器，再對每一行字串用字典或表格計數，計算字母數量，如果數量是質數就加到答案之中。最後再依照答案中儲存的內容按照字典序輸出，如果答案是空的則印出 empty。

Python 程式碼

Python 有現成的計數工具 Counter，使用時間約為 11 ms，記憶體約為 3.2 MB，通過測試。

from collections import Counter
""" 建立 0 ~ 2000 的質數篩選器 """
maxn = 2000
sieve = [True]*(maxn + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(maxn**0.5) + 1):
    if sieve[i]:
        for j in range(i*i, maxn+1, i):
            sieve[j] = False
""" 主要的解題過程 """
T = int(input())
for t in range(1, T+1):
    cnt = Counter(input())  # 計數器
    ans = []  # 答案
    for k, v in cnt.items():  # 依序取出字母 k 及數量 v
        if sieve[v]: ans.append(k)  # 如果 v 是質數，k 加入 ans
    ans.sort()  # 排序
    print(f"Case {t:d}: ", end="")  # 輸出答案
    if not ans: print("empty")
    else: print("".join(ans))

ZeroJudge 解題筆記：a535. 10141 - Request for Proposal

作者：王一哲
日期：2026年1月8日


ZeroJudge 題目連結：a535. 10141 - Request for Proposal

解題想法

依序掃過所有的廠商資料，如果讀到新的最大商品數量、最低價格，更新贏家名稱。

Python 程式碼

使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

import sys

ca = 0
for line in sys.stdin:
    n, p = map(int, line.split())  # 需求表項目數量 n、廠商數量 p
    ca += 1
    if n == 0 and p == 0: break
    for _ in range(n):  # 讀取 n 行資料，解題時用不到
        _ = sys.stdin.readline()
    winner = ""  # 贏家
    price = float('inf')  # 最低價格，預設為最大值
    item = 0  # 廠商提供的商品在需求表中的最大數量
    for _ in range(p):  # 讀取 p 家廠商資料
        name = sys.stdin.readline().rstrip()  # 廠商名稱
        d, r = sys.stdin.readline().split()  # 價格 d、商品數量 r
        d = float(d)  # d 轉成浮點數
        r = int(r)  # r 轉成整數
        if r > item:  # 如果 r 大於 item
            winner = name  # 新的贏家
            price = d  # 新的最低價
            item = r  # 新的商品數量
        elif r == item and d < price:  # 如果商品數量一樣而且價格較低
            winner = name  # 新的贏家
            price = d  # 新的最低價
        for _ in range(r):  # 讀取 r 行資料，解題時用不到
            _ = sys.stdin.readline()
    if ca > 1: sys.stdout.write("\n")
    sys.stdout.write(f"RFP #{ca:d}\n{winner:s}\n")  

ZeroJudge 解題筆記：a522. 12455 - Bars

作者：王一哲
日期：2026年1月7日


ZeroJudge 題目連結：a522. 12455 - Bars

解題想法

這題考 0/1 背包問題，由於測資不大，用 set 儲存所有可能的長度組合也能 AC，比較標準的作法是用一維陣列儲存所有長度總合的組合數，或是用 bitset 儲存所有可能的長度組合。

Python 程式碼

用集合儲存所有可能的長度組合，使用時間約為 22 ms，記憶體約為 3.3 MB，通過測試。

t = int(input())  # t 組測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # 需要的長度 n
    have = {0}  # 已經有的長度集合，先放入 0
    p = int(input())  # p 根金屬棒，用不到
    for m in map(int, input().split()):  # 讀取金屬棒長度
        tmp = set()  # 暫存新的總長度
        for h in have: tmp.add(h+m)  # 依序讀取已經有的長度 h，新的長度 h+m 加入 tmp
        #for t in tmp: have.add(t)  # tmp 的資料加入 have
        have.update(tmp)  # tmp 的資料加入 have，另一種寫法
    print("YES" if n in have else "NO")  # 如果 n 在 have 之中印出 YES，反之印出 NO

用動態規劃找出所有長度可能的組合數，如果長度 $n \leq imax$ 而且組合數大於 0 印出 Yes，反之印出 No。使用時間約為 10 ms，記憶體約為 2.9 MB，通過測試。

t = int(input())  # t 組測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # 需要的長度 n
    p = int(input())  # p 根金屬棒，用不到
    ms = list(map(int, input().split()))  # 金屬棒長度
    imax = sum(ms)  # 總長度
    dp = [0]*(imax + 1)  # 所有長度可能的組合數
    dp[0] = 1  # 基礎狀態，長度 0 的組合數 1
    for m in ms:  # 依序讀取金屬棒長度，0/1 背包問題
        for i in range(imax, m-1, -1):
            if dp[i-m] > 0:
                dp[i] += dp[i-m]
    # 如果長度 n 小於等於 imax 而且組合數大於 0 印出 Yes
    print("YES" if n <= imax and dp[n] > 0 else "NO")  

用動態規劃及 bitset 儲存所有可能的長度組合，不記錄組合數，如果長度 $n$ 有對應的組合印出 Yes，反之印出 No。使用時間約為 7 ms，記憶體約為 2.8 MB，通過測試。

t = int(input())  # t 組測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # 需要的長度 n
    p = int(input())  # p 根金屬棒，用不到
    ms = list(map(int, input().split()))  # 金屬棒長度
    dp = 1  # 用 bitset 儲存所有可能的長度組合，基礎狀態，長度 0 的組合數 1
    for m in ms:  # 依序讀取金屬棒長度，0/1 背包問題
        dp |= (dp << m)
    # 如果長度 n 小於等於 imax 而且組合數大於 0 印出 Yes
    print("YES" if (dp >> n) & 1 else "NO")  

ZeroJudge 解題筆記：a520. 12416 - Excessive Space Remover

作者：王一哲
日期：2026年1月6日


ZeroJudge 題目連結：a520. 12416 - Excessive Space Remover

解題想法

這題要先排除特例，如果字串中所有的連續空格都是 1 格，不需要取代空格，印出 0 即可。 接下來用數學解。先計算連續空格的數量最大值 $imax$。 狀況1，如果 $imax = 2^n$，每取代一次會使 $imax$ 減半，共要取代 $n$ 次。例如 $imax = 16$，每次取代空格之後，$imax$ 分別變為 $8, 4, 2, 1$，共 4 次。 狀況2，如果 $2^{n-1} < imax < 2^n$，需要取代 $n$ 次。例如 $imax = 13$，每次取代空格之後，$imax$ 分別變為 $7, 4, 2, 1$，共 4 次。

Python 程式碼

使用時間約為 8 ms，記憶體約為 2.8 MB，通過測試。

import sys, math

for line in sys.stdin:
    s = line.rstrip()
    imax, cnt = 0, 0
    for c in s:
        if c.isspace():
            cnt += 1
        else:
            imax = max(imax, cnt)
            cnt = 0
    imax = max(imax, cnt)
    if imax == 1:
        print(0)
    else:
        print(math.ceil(math.log2(imax)))

ZeroJudge 解題筆記：a519. 12459 - Bees' ancestors

作者：王一哲
日期：2026年1月5日


ZeroJudge 題目連結：a519. 12459 - Bees' ancestors

解題想法

先列出幾代的祖先看一下數量是否有規律，以下各行依序為第幾代，祖先性別 M 為雄性、F 為雌性，祖先數量。

1, F, 1
2, FM, 2
3, FMF, 3
4, FMFFM, 5
5, FMFFMFMF, 8
6, FMFFMFMFFMFFM, 13

第 $n$ 代的祖先數量就是費氏數列 $F(n+1)$ 對應的值。由於這題有多筆測資要查詢對應的數量，可以先建表格，節省查詢的時間。

Python 程式碼

使用時間約為 7 ms，記憶體約為 2.8 MB，通過測試。

import sys

fib = [0]*82
fib[1] = 1
for i in range(2, 82):
    fib[i] = fib[i-1] + fib[i-2]

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    print(fib[n+1])

ZeroJudge 解題筆記：a518. 12468 - Zapping

作者：王一哲
日期：2026年1月4日


ZeroJudge 題目連結：a518. 12468 - Zapping

解題想法

有三種可能性，如果 a 等於 b，不需要切換，答案為 0；如果 a 大於 b，按下再從另一頭繞回來，或是一直按上；如果 a 小於 b，按上再從另一頭繞回來，或是一直按下。對後面兩種狀況，分別計算按上或下的次數，答案是較小的那個。

Python 程式碼

使用時間約為 16 ms，記憶體約為 2.9 MB，通過測試。

import sys

for line in sys.stdin:
    a, b = map(int, line.split())
    if a == -1 and b == -1: break
    up, down = 100, 100  # 按上、下最少的次數，預設為超出範圍的值
    if a == b:  # a 等於 b，不需切換
        up = down = 0
    elif a > b:  # a 大於 b，按下再從另一頭繞回來，或是一直按上
        up = a - b
        down = 100 - a + b
    else:  # a 小於 b，按上再從另一頭繞回來，或是一直按下
        up = a + 100 - b
        down = b - a
    print(min(up, down))

ZeroJudge 解題筆記：a469. 10063 - Knuth's Permutation

作者：王一哲
日期：2026年1月3日


ZeroJudge 題目連結：a469. 10063 - Knuth's Permutation

解題想法

題目的文字敘述不太容易理解，討論區這篇貼文的解釋比較詳細 https://zerojudge.tw/ShowThread?postid=18884&reply=18880#18884。寫一個自訂函式 solve，依照 Knuth's Permutation 的規則産生所有的排列方式。

Python 程式碼

使用時間約為 0.2 s，記憶體約為 33.7 MB，通過測試。

import sys

def solve(letters):  # 輸入字串，依照 Knuth's Permutation 的規則産生所有的排列方式
    perms = [letters[0]]  # 所有的排列方式，先放入 letters[0]
    for letter in letters[1:]:  # 依序讀取 letters[1] ~ letters[-1]
        new_perms = []  # 新的排列方式
        for perm in perms:  # 依序讀取 perms 每一項
            for i in range(len(perm) + 1):  # 依序找 i = 0 ~ len(perm) 的位置
                new_perm = perm[:i] + letter + perm[i:]  # 用字串切片，從左到右的位置組合新的排列方式
                new_perms.append(new_perm)  # new_perm 加入 new_perms
        perms = new_perms  # 更新 perms，每跑完一次 perms 中每一項長度加 1
    return perms  # 回傳 perms

for line in sys.stdin:
    perms = solve(line.strip())
    for perm in perms: print(perm)
    print()

ZeroJudge 解題筆記：a468. 12439 - February 29

作者：王一哲
日期：2026年1月2日


ZeroJudge 題目連結：a468. 12439 - February 29

解題想法

先自訂 3 個函式，分別為用來檢查指定年份是否為閏年的 is_leap，計算指定年份到西元 0 年的閏年數量的 leaps_before，計算兩個年份之間的閏年數量的 count_leap_years。讀取日期之後，將日期的年、月、日轉成整數。如果起始年在2月29日之後，則不計入該年。如果結束年在2月29日之前，則不計入該年。將調整後的起始年、結束年代入 count_leap_years 計算答案。

Python 程式碼

使用時間約為 24 ms，記憶體約為 3.4 MB，通過測試。

def is_leap(year):  # 判斷輸入的年份是否為閏年
    if year % 400 == 0: return True  # 可以被 400 整除，是閏年
    if year % 100 == 0: return False  # 可以被 100 整除但不能被 400 整除，是平年
    if year % 4 == 0: return True  # 可以被 4 整除但不能被 100 整除，是閏年
    return False  # 其它狀況，是平年

def leaps_before(year):  # 計算指定年份到西元 0 年的閏年數量
    return year//4 - year//100 + year//400

def count_leap_years(start_year, end_year):  # 計算兩個年份之間的閏年數量，包含兩端的年份
    return leaps_before(end_year) - leaps_before(start_year - 1)

""" 主要的解題過程 """
month_map = {"January": 1, "February": 2, "March": 3, "April": 4, "May": 5, "June": 6,
             "July": 7, "August": 8, "September": 9, "October": 10, "November": 11, "December": 12}
T = int(input())  # T 筆測資
for t in range(1, T+1):  # 執行 T 次
    ### 處理起始日期 ###
    date1 = list(input().split())  # 起始日期
    month1 = month_map[date1[0]]  # 起始月份
    day1 = int(date1[1][:-1])  # 起始日，刪除最後的逗號
    year1 = int(date1[2])  # 起始年份
    ### 處理結束日期 ###
    date2 = list(input().split())  # 結束日期
    month2 = month_map[date2[0]]  # 結束月份
    day2 = int(date2[1][:-1])  # 結束日，刪除最後的逗號
    year2 = int(date2[2])  # 結束年份
    ### 調整起始年份和結束年份 ###
    start_year = year1
    end_year = year2
    if is_leap(year1):  # 如果起始年在2月29日之後，則不計入該年
        if month1 > 2 or (month1 == 2 and day1 > 29):
            start_year += 1
    if is_leap(year2):  # 如果結束年在2月29日之前，則不計入該年
        if month2 < 2 or (month2 == 2 and day2 < 29):
            end_year -= 1
    ### 計算閏年數量 ###
    if start_year > end_year:  # 題目保證結束日期在起始日期之後，基本上不會發生
        ans = 0
    else:
        ans = count_leap_years(start_year, end_year)
    print(f"Case {t:d}: {ans:d}")

ZeroJudge 解題筆記：a467. 11398 - The Base-1 Number System

作者：王一哲
日期：2026年1月1日


ZeroJudge 題目連結：a467. 11398 - The Base-1 Number System

解題想法

依照題目敘述處理讀取到的字串，如果字串內容只有 ~ 就中止程式； 如果是其它內容，將字串用空格分隔後存入串列 arr 之中。可以用字串或是串列儲存一行測資轉換後得到的 0, 1 字串 result。依序讀取 arr 的內容存入 a，如果 a 是 # 將 result 用 2 進位制轉換成整數後輸出；如果 a 是 0，將 flag 改成 1； 如果 a 是 1，將 flag 改成 0；其它狀況，在 result 後面接上 a 的長度減 2 個 flag。

Python 程式碼

使用時間約為 25 ms，記憶體約為 3 MB，通過測試。

import sys

result = ""
flag = "1"
for line in sys.stdin:
    if line.strip() == "~": break
    arr = line.split()
    for a in arr:
        if a == "#":
            print(int(result, 2))
            result = ""
        elif a == "0": flag = "1"
        elif a == "00": flag = "0"
        else:
            result += flag*(len(a)-2)

使用時間約為 84 ms，記憶體約為 4.4 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
flag = "1"
idx = 0
while idx < len(lines):
    if lines[idx].strip() == "~": break
    arr = lines[idx].split()
    idx += 1
    res = []  # 暫存這行測資輸出結果用的串列
    for a in arr:
        if a == "#":
            num = int("".join(res), 2)
            res.clear()
            result.append(f"{num:d}\n")
        elif a == "0": flag = "1"
        elif a == "00": flag = "0"
        else:
            res += [flag]*(len(a)-2)
sys.stdout.write("".join(result))