一個地球人在臺北

2026年1月20日星期二

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))

2026年1月19日星期一

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))

2026年1月18日星期日

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")

2026年1月17日星期六

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)

2026年1月16日星期五

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))

2026年1月15日星期四

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))

2026年1月14日星期三

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))

2026年1月13日星期二

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))

2026年1月12日星期一

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}")

2026年1月11日星期日

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))

訂閱：文章 (Atom)

置頂

熱門文章

2026年1月20日 星期二

解題想法

Python 程式碼

2026年1月19日 星期一

解題想法

Python 程式碼

2026年1月18日 星期日

解題想法

Python 程式碼

2026年1月17日 星期六

解題想法

Python 程式碼

2026年1月16日 星期五

解題想法

Python 程式碼

2026年1月15日 星期四

解題想法

Python 程式碼

2026年1月14日 星期三

解題想法

Python 程式碼

2026年1月13日 星期二

解題想法

Python 程式碼

2026年1月12日 星期一

解題想法

Python 程式碼

2026年1月11日 星期日

解題想法

Python 程式碼

2026年1月20日星期二

2026年1月19日星期一

2026年1月18日星期日

2026年1月17日星期六

2026年1月16日星期五

2026年1月15日星期四

2026年1月14日星期三

2026年1月13日星期二

2026年1月12日星期一

2026年1月11日星期日