ZeroJudge 解題筆記：a134. 00948 - Fibonaccimal Base

作者：王一哲
日期：2025年12月21日


ZeroJudge 題目連結：a134. 00948 - Fibonaccimal Base

解題想法

由於題目限制要轉換的數字是小於 $100,000,000$ 的正整數，而費氏數列第 40 項就已經是 $102,334,155$，所以建表時只要建前 40 項就可以了。 我另外寫一個轉換數字基底用的函式，假設要轉換的數字是 num，先判斷特例，如果 num 等於 0 直接回傳字串 0，如果 num 等於 1 直接回傳字串 1。接下來用一個 for 迴圈，從表格 fib 後面往前找第一個小於等於 num 的值，以這一項作為起點 start。再用一個 for 迴圈，從 start 往回找到 fib[2] 為止，如果 num 大於等於 fib[j]，要選用這一項，儲存轉換結果的字串 s 加上 1，再將 num 減去 fib[j]；反之，字串 s 加上 0。

Python 程式碼

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

def convert(num):
    if num == 0: return "0"
    if num == 1: return "1"
    start = -1
    for j in range(40, 1, -1):
        if fib[j] <= num:
            start = j
            break
    if start == -1: return "-1"
    s = ""
    for j in range(start, 1, -1):
        if num >= fib[j]:
            s += "1"
            num -= fib[j]
        else:
            s += "0"
    return s

fib = [0]*41
fib[1] = 1
for i in range(2, 41):
    fib[i] = fib[i-1] + fib[i-2]
n = int(input())
for _ in range(n):
    m = int(input())
    print(f"{m:d} = {convert(m)} (fib)")

ZeroJudge 解題筆記：a132. 10931 - Parity

作者：王一哲
日期：2025年12月20日


ZeroJudge 題目連結：a132. 10931 - Parity

解題想法

這題要將一個 10 進位整數轉換成 2 進位字串，再計算字串中 1 的數量。如果用 Python 解題，可以直接用內建的 bin，不過轉換後的字串前面有 0b，要用切片從索引值 2 開始取子字串。如果用 C++ 解題，可以自己寫轉換用的函式，也可以引入 bitset，用 bitset 之中的 to_string() 功能轉換整數。

Python 程式碼

Python 有內建的 10 進位整數轉換成 2 進位字串函式，使用時間約為 8 ms，記憶體約為 2.9 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    s = bin(n)[2:]
    p = sum([c == '1' for c in s])
    print(f"The parity of {s:s} is {p:d} (mod 2).")

C++ 程式碼

自己寫將 10 進位整數轉換成 2 進位字串的函式，使用時間約為 1 ms，記憶體約為 316 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;

string bin(int n) {
    string s = "";
    while(n) {
        if (n&1) s = "1" + s;
        else s = "0" + s;
        n >>= 1;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n && n != 0) {
        string s = bin(n);
        int p = 0;
        for(char c : s) {
            if (c == '1') p++;
        }
        cout << "The parity of " << s << " is " << p << " (mod 2).\n";
    }
    return 0;
}

ZeroJudge 解題筆記：a133. 10066 - The Twin Towers

作者：王一哲
日期：2025年12月19日


ZeroJudge 題目連結：a133. 10066 - The Twin Towers

解題想法

這題考最長共同子序列 (longest common subsequence, LCS)，只要找長度，不需要找 LCS 的內容。寫法有兩種，假設兩筆資料 a、b 的長度分別為 n、m，可以用一個 $(n+1) \times (m+1)$ 的二維陣列儲存動態規劃資料，$dp[i][j]$ 代表比較到 $a[i-1]$ 與 $b[i-1]$ 時 LCS 的長度；也可以用兩個陣列儲存資料，用滾動陣列節省記憶體。

Python 程式碼

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

import sys

ca = 0
for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    ca += 1
    print(f"Twin Towers #{ca:d}")
    a = tuple(map(int, sys.stdin.readline().split()))
    b = tuple(map(int, sys.stdin.readline().split()))
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+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])
    print(f"Number of Tiles : {dp[-1][-1]:d}\n")

ZeroJudge 解題筆記：a131. 00739 - Soundex Indexing

作者：王一哲
日期：2025年12月18日


ZeroJudge 題目連結：a131. 00739 - Soundex Indexing

解題想法

可以用陣列建立字母、數字對照表，將字母 A, B, C, ..., Z 對應的數字填入陣列之中。也可以用字典建立對照表，這個寫法比較容易閱讀。

Python 程式碼

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

import sys

table = ('0', '1', '2', '3', '0', '1', '2', '0', '0', '2',
         '2', '4', '5', '5', '0', '1', '2', '6', '2', '3',
         '0', '1', '0', '2', '0', '2')
print("         NAME                     SOUNDEX CODE")
for line in sys.stdin:
    s = line.strip()
    n = len(s)
    last = table[ord(s[0]) - ord('A')]
    result = [s[0]]
    for i in range(1, n):
        if len(result) >= 4: break
        curr = table[ord(s[i]) - ord('A')]
        if curr != '0' and curr != last: result.append(curr)
        last = curr
    while len(result) < 4: result.append('0')
    output = " "*9 + s + " "*(25-n) + "".join(result)
    print(output)
print("                   END OF OUTPUT")

ZeroJudge 解題筆記：a130. 12015 - Google is Feeling Lucky

作者：王一哲
日期：2025年12月17日


ZeroJudge 題目連結：a130. 12015 - Google is Feeling Lucky

解題想法

這題考排序，網站相關度高排前面，如果相關度相同，先讀到的放前面。如果用 Python 解題，可以將網站相關度 val、讀取資料的索引值 idx、網址 url 組成 tuple 再存入串列，排序時用 lambda function 寫比較式 (-x[0], x[1])。如果用 C++ 解題，可以自訂結構體儲存網站相關度 val、讀取資料的索引值 idx、網址 url，資料存入 vector，排序時用 lambda function 寫比較式。

Python 程式碼

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

T = int(input())
for t in range(1, T+1):
    print(f"Case #{t:d}:")
    data = []
    for i in range(10):
        url, v = input().split()
        data.append((int(v), i, url))
    # 排序，相關度高排前面，如果相關度相同，先讀到的放前面
    data.sort(key = lambda x : (-x[0], x[1]))
    vmax = data[0][0]
    for d in data:
        if d[0] < vmax: break
        print(d[2])

ZeroJudge 解題筆記：a111. 12149 - Feynman

作者：王一哲
日期：2025年12月16日


ZeroJudge 題目連結：a111. 12149 - Feynman

解題想法

如果 $n = 1$ 答案為 $1$；如果 $n = 2$，答案為 $1 + 4 = 1 + 2^2 = 5$；如果 $n = 3$，答案有邊長 3 的正方形 1 個，邊長 2 的正方形 4 個，邊長 1 的正方形 9 個，也就是 $1 + 4 + 9 = 1 + 2^2 + 3^2 = 14$。解題時可以建表或是代公式 $$ ans = \sum_{i = 1}^n i^2 = \frac{n(n+1)(2n+1)}{6} $$

Python 程式碼

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

import sys

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

for line in sys.stdin:
    n = int(line)
    if n == 0: continue
    print(dp[n])

代公式，使用時間約為 20 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    if n == 0: continue
    print(n*(n+1)*(2*n + 1)//6)

ZeroJudge 解題筆記：a011. 00494 - Kindergarten Counting Game

作者：王一哲
日期：2025年12月15日


ZeroJudge 題目連結：a011. 00494 - Kindergarten Counting Game

解題想法

這題要讀取整行字串之後依序讀取每個字元，用變數 last 記錄目前連續出現的字母數量，如果這個字元是字母則 last 加 1； 反之，前一個單字結束了，如果 last 大於 0，單字數量 cnt 加 1，再將 last 歸零。檢查完整行字串之後，記得要再結算一次，才不會漏掉最後一個單字。

Python 程式碼

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

import sys

for line in sys.stdin:
    last, cnt = 0, 0
    for c in line.strip():
        if c.isalpha(): last += 1
        else:
            if last > 0: cnt += 1
            last = 0
    if last > 0: cnt += 1
    print(cnt)

ZeroJudge 解題筆記：o087. 王子的名字

作者：王一哲
日期：2025年12月14日


ZeroJudge 題目連結：o087. 王子的名字

解題想法

先檢查讀取到的名字是否都是字母，如果有任何一個字元不是字母，分數為 -1；如果所有字元都是字母，按照題目給的規則計分。將分數、索引、名字組成 tuple 或是自訂的 struct ，存入陣列之中，最後按照分數、索引值由小到大排序。

Python 程式碼

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

def Evaluate(Name: str):
    if(type(Name) != str): return -1                              
    Score = 0
    NameLen = len(Name)
    for i in range(NameLen):
        CharCode = ord(Name[i])
        Score += ((CharCode * 1123) % 1002)
        while (CharCode > 0):
            Score += (CharCode % 10)
            CharCode = (CharCode // 10)
    return (Score % 101)

n = int(input())
names = []
for i in range(n):
    name = input()
    score = Evaluate(name)
    names.append((score, i, name))
names.sort()
for score, _, name in names:
    print(f"{name:s} {score:d}")

ZeroJudge 解題筆記：o067. 柯尼斯堡七橋問題

作者：王一哲
日期：2025年12月13日


ZeroJudge 題目連結：o067. 柯尼斯堡七橋問題

解題想法

有奇數條邊的節點數量必須小於等於 2 才有解，可以真的存圖再計算有奇數條邊的節點數量，也可以不存圖、只儲存每個節點是否有奇數條邊。不要真的模擬走訪過程。

Python 程式碼

真的存圖，使用時間約為 0.4 s，記憶體約為 12.7 MB，通過測試。

n, m = map(int, input().split())
graph = dict()
for _ in range(m):
    u, v = map(int, input().split())
    if u not in graph: graph[u] = [v]
    else: graph[u].append(v)
    if v not in graph: graph[v] = [u]
    else: graph[v].append(u)
cnt = 0
flag = True
for v in graph.values():
    if len(v)%2 == 1: cnt += 1
    if cnt > 2:
        flag = False
        break
print("YES" if flag else "NO")

只存每個節點是否有奇數條邊，使用時間約為 0.4 s，記憶體約為 3.4 MB，通過測試。

n, m = map(int, input().split())
vertice = [False]*(n+1)
for _ in range(m):
    u, v = map(int, input().split())
    vertice[u] = not vertice[u]
    vertice[v] = not vertice[v]
cnt = sum(vertice)
print("YES" if cnt <= 2 else "NO")

ZeroJudge 解題筆記：n700. 蝸牛的踩地雷攻略 3 (點方塊)

作者：王一哲
日期：2025年12月12日


ZeroJudge 題目連結：n700. 蝸牛的踩地雷攻略 3 (點方塊)

解題想法

為了不要檢查是否出界，我習慣在地圖的最右側、最下方加上用不到的符號當作哨兵。用自訂函式 count 計算周圍 8 格的地雷數量，再用另一個自訂函式 reveal 翻開格子，reveal 之中是用 BFS 找出所有可以翻開的格子，同時將翻開後的地圖儲存到另一個二維串列之中。

Python 程式碼

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

from collections import deque

def count(grid, r, c):  # 計算周圍 8 格的地雷數量
    cnt = 0  # 地雷數量
    for dr, dc in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
        nr, nc = r+dr, c+dc
        if grid[nr][nc] == '*': cnt += 1
    return cnt

def reveal(grid, result, ri, ci, n, m):  # 翻開格子，代入地圖 grid，結果 result，位置 (ri, ci)，維度 n*m
    visited = [[False]*(m+1) for _ in range(n+1)]  # 是否已走訪
    que = deque([(ri, ci)])  # 待走訪的位置
    visited[ri][ci] = True  # (ri, ci) 已走訪
    while que:  # 如果 que 還有資料繼續執行
        r, c = que.popleft()  # 從 que 開頭讀取並移除資料
        cnt = count(grid, r, c)  # 計算 (r, c) 周圍的地雷數量
        if cnt == 0:  # 如果周圍沒有地雷
            result[r][c] = '_'  # 翻開，是空地
            # 檢查周圍 8 格，如果還沒有出界、沒有走訪、是未翻開的格子
            for dr, dc in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
                nr, nc = r+dr, c+dc
                if grid[nr][nc] != '@' and not visited[nr][nc] and grid[nr][nc] == '#':
                    visited[nr][nc] = True  # (nr, nc) 已走訪
                    que.append((nr, nc))  # (nr, nc) 加入 que
        else: result[r][c] = str(cnt)  # 周圍有地雷，填入地雷的數量

def main():  # 主程式
    n, m, ri, ci = map(int, input().split())  # 地圖維度 n*m，起點 (ri, ci)
    grid = [list(input().strip() + '@') for _ in range(n)]  # 最右側加上 @ 作為哨兵
    grid.append(['@']*(m+1))  # 最下方加 m+1 個 @ 作為哨兵
    result = [['#']*m for _ in range(n)]  # 儲存結果用的 n*m 二維串列
    ri -= 1; ci -= 1  # 配合索引值，ri, ci 減 1
    reveal(grid, result, ri, ci, n, m)  # 呼叫 reveal 求解
    for row in result: print("".join(row))  # 印出答案

if __name__ == '__main__':
    main()

ZeroJudge 解題筆記：n689. pD. 技能點數

作者：王一哲
日期：2025年12月11日


ZeroJudge 題目連結：n689. pD. 技能點數

解題想法

我用接鄰矩陣 graph 儲存有向圖，用串列 need 儲存學習各技能所需的前置技能，用集合 learn 儲存學到的技能。將一開始拿到的技能書 book 存入待走訪佇列 que，用 BFS 找出所有可以學到的技能。

Python 程式碼

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

from collections import deque

n, m, k = map(int, input().split())
book = list(map(int, input().split()))
graph = [[] for _ in range(n)]
need = [set() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    need[v].add(u)
for b in book: need[b].clear()
learn = set(book)
que = deque(book)
while que:
    u = que.popleft()
    for v in graph[u]:
        if u in need[v]:
            need[v].remove(u)
        if not need[v]:
            que.append(v)
            learn.add(v)
print(len(learn))

ZeroJudge 解題筆記：n688. pC. 卡牌遊戲

作者：王一哲
日期：2025年12月10日


ZeroJudge 題目連結：n688. pC. 卡牌遊戲

解題想法

先將卡牌分別正值、負值兩堆，為了將卡牌總和最大化，策略是將負值牌堆中最小的牌，也就是負值、量值最大的牌取出、轉為正值、存入正值牌堆，如果負值牌堆沒有資料了，就反過來將正值牌堆中最小的牌取出、轉為負值、存入負值牌堆。為了達成這個目標，用最小優先佇列儲存牌堆是最方便的。

Python 程式碼

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

import heapq

n, k = map(int, input().split())
positive, negative = [], []
for x in map(int, input().split()):
    if x >= 0: heapq.heappush(positive, x)
    else: heapq.heappush(negative, x)
for _ in range(k):
    if negative:
        heapq.heappush(positive, -heapq.heappop(negative))
    elif positive:
        heapq.heappush(negative, -heapq.heappop(positive))
print(sum(positive) + sum(negative))

ZeroJudge 解題筆記：n083. 數字序號轉換

作者：王一哲
日期：2025年12月9日


ZeroJudge 題目連結：n083. 數字序號轉換

解題想法

假設計算結果儲存在變數 m，m 的初始值為 0。將讀到的字串從索引值 0 開始，每次取長度為 3 的子字串，並用一個布林值記錄這次是否需要將子字串反序。m 加上子字串轉成 int 之後的值，再對 997 取餘數。

Python 程式碼

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

import sys

MOD = 997
result = []
lines = sys.stdin.readlines()
for line in lines:
    line = line.strip()
    n = len(line)
    m = 0
    rev = False
    for i in range(0, n, 3):
        s = line[i:i+3]
        if rev: s = s[::-1]
        rev = not rev
        m = (m + int(s))%MOD
    result.append(str(m) + "\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：b181. 2. 網路設計

作者：王一哲
日期：2025年12月8日


ZeroJudge 題目連結：b181. 2. 網路設計

解題想法

這題用自訂的併查集類別建立物件，依序從成本最低的邊開始測試，如果這條邊加上去之後，能夠使兩個節點所在的區塊連通，就要選用這條邊，記錄節點編號並更新總成本。 題目沒有說清楚的地方有三點：

1. 這題是多筆測資
2. n 只是節點編號的最大值，不見得有 n 個節點。
3. 節點的排序方式，讀取測資儲存邊的成本、節點時要按照測資的順序。輸出節點時要按照節點的編號由小到大排序，轉換成整數再比大小，不用管開頭的 W，兩個節點一組，先比較第一個節點，再比較第二個節點。輸出時如果按照字典序排序會出錯

   WA (line:3)
   您的答案為: (W10 W2) (W2 W3) (W3 W4) (W3 W5) (W3 W6)
   正確答案為: (W2 W3) (W3 W4) (W3 W5) (W3 W6) (W10 W2)
   

   如果按照第一個節點的編號數字排序也會出錯

   WA (line:3)
   您的答案為: (W2 W3) (W3 W5) (W3 W4) (W3 W6) (W10 W2)
   正確答案為: (W2 W3) (W3 W4) (W3 W5) (W3 W6) (W10 W2)
   

Python 程式碼

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

import sys
from functools import cmp_to_key

class DisjointSetUnion:
    def __init__(self, nodes):
        self.parent = {node: node for node in nodes}
        self.rank = {node: 0 for node in nodes}

    def rfind(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.rfind(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_v] > self.rank[root_u]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1
            return True
        return False

def mycmp(a, b):
    """ 為了輸出節點定義的比較式 """
    if int(a[0][1:]) == int(b[0][1:]):  # 如果第一個節點的編號相同
        if int(a[1][1:]) < int(b[1][1:]): return -1  # 第二個節點編號小的放前面
        elif int(a[1][1:]) > int(b[1][1:]): return 1
        else: return 0
    if int(a[0][1:]) < int(b[0][1:]): return -1  # 第一個節點編號小的放前面
    else: return 1

""" 處理多筆測資 """
result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    """ 讀取測資 """
    n, m = map(int, lines[idx].split())  # 題目敘率不清，n 是可能的節點編號最大值，m 條邊
    idx += 1
    nodes = set()  # 所有節點，不見得有 n 個節點，要從邊的資料找節點
    edges = []  # 所有的邊
    for _ in range(m):  # 讀取 m 條邊
        line = lines[idx].split()
        idx += 1
        u, v = line[0], line[1]  # 節點 u, v 相連
        w = int(line[2])  # 邊的成本
        edges.append((w, u, v))  # (成本, 節點1, 節點2)，節點要按照測資的順序
        nodes.add(u)
        nodes.add(v)

    """ 用併查集找最低合併成本 """
    dsu = DisjointSetUnion(nodes)  # 建立併查集物件
    edges.sort()  # 依照成本由小到大排序
    cost = 0  # 總成本
    choose = []  # 選取的節點
    for w, u, v in edges:  # 依序讀取邊
        if dsu.union(u, v):  # 如果 u, v 可以合併
            cost += w  # 更新成本
            choose.append((u, v))  # 更新選取的節點
    """ 輸出答案 """
    choose.sort(key = cmp_to_key(mycmp))  # 輸出節點時，要按照節點編號大小排序，比數字
    res = []
    for u, v in choose:
        res.append(f"({u} {v})")
    result.append(" ".join(res) + "\n" + f"{cost:d}\n")
""" 一次輸出所有答案 """
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：m702. 傑出校友票選活動

作者：王一哲
日期：2025年12月7日


ZeroJudge 題目連結：m702. 傑出校友票選活動

解題想法

這題用字典計數比較方便。如果用 Python 解題，可以用預設的 dict 計數，再將 dict 的 (value, key) 組成 tuple 存入另一個 list，將 list 依照 value 由大到小排序；也可以先將所有的選票儲存到一個串列中，用 collections.Counter 計數，最後用 Counter 的功能 most_common 取出前 m 個最大的值。

Python 程式碼

使用預設的 dict，使用時間約為 0.2 s，記憶體約為 27.1 MB，通過測試。

n, m = map(int, input().split())
cnt = dict()
for _ in range(n):
    name = input()
    if name not in cnt: cnt[name] = 1
    else: cnt[name] += 1
    
ballot = sorted([(val, name) for name, val in cnt.items()], reverse=True)
print(" ".join([name for _, name in ballot[:m]]))

使用 Counter，使用時間約為 67 ms，記憶體約為 20.3 MB，通過測試。

from collections import Counter

n, m = map(int, input().split())
ballot = [input() for _ in range(n)]
cnt = Counter(ballot)
print(*[name for name, _ in cnt.most_common(m)])

ZeroJudge 解題筆記：m685. 三角形計數器

作者：王一哲
日期：2025年12月6日


ZeroJudge 題目連結：m685. 三角形計數器

解題想法

這題要找共有幾組邊長比例不同的三角形。我是將讀到的一個三角形邊長由小到大排序，再用三個邊長的最大公因數約分，最後將約分後的邊長組成 tuple 或 vector 存進 set。讀取完所有測資之後，set 的大小就是答案。

Python 程式碼

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

import math

n = int(input())
triangle = set()
for _ in range(n):
    a, b, c = sorted(list(map(int, input().split())))
    g = math.gcd(a, math.gcd(b, c))
    a, b, c = a//g, b//g, c//g
    triangle.add((a, b, c))
print(len(triangle))

ZeroJudge 解題筆記：m283. 螞蟻的擴散

作者：王一哲
日期：2025年12月5日


ZeroJudge 題目連結：m283. 螞蟻的擴散

解題想法

這題可以用一個二維陣列 $dp$ 記錄螞蟻從 $(a, b)$ 開始移動到每一格的機率，走到 $x = 0$ 或 $y = 0$ 時停止。走到格子 $(r, c)$ 的機率為 $$ dp[r][c] = (dp[r+1][c] + dp[r][c+1] + dp[r+1][c+1]) \times \frac{1}{3} $$ 用二層 for 迴圈計算往 $(0, 0)$ 方向走到每一格的機率。最後的答案等於 $1 - dp[0][0]$。 如果用 Python 解題，可以引入 fractions.Fraction 計算分數，也可以先計算分子最後再約分。

Python 程式碼

用 fractions.Fraction 計算分數，使用時間約為 53 ms，記憶體約為 4.1 MB，通過測試。

import sys
from fractions import Fraction

for line in sys.stdin:
    y, x = map(int, line.split())
    dp = [[0]*(x+1) for _ in range(y+1)]
    dp[y][x] = Fraction(1, 1)
    for r in range(y-1, -1, -1):
        for c in range(x-1, -1, -1):
            dp[r][c] = (dp[r+1][c] + dp[r][c+1] + dp[r+1][c+1])*Fraction(1, 3)
    print(1 - dp[0][0])

ZeroJudge 解題筆記：k862. 輩份比較

作者：王一哲
日期：2025年12月4日


ZeroJudge 題目連結：k862. 輩份比較

解題想法

我用字典儲存每個節點的父節點與子節點，存完圖之後再找出沒有父節點的節點名稱，這個節點就是根節點。接下來由兩個要比較輩份的節點出發，由下往上走到根節點，找出與根節點之間的距離。最後將兩個距離相減就是輩份差。

Python 程式碼

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

n = int(input())  # n 組關係
parent = dict()  # 父節點
child = dict()  # 子節點
for _ in range(n):  # 讀取 n 行資料
    a, b = input().split()  # a 是 b 的子節點
    if b not in child: child[b] = [a]  # 更新子節點
    else: child[b].append(a)
    if a not in parent: parent[a] = b  # 更新父節點
root = ""  # 根節點
for b in child.keys():  # 依序取出 child 的 key 值 b
    if b not in parent:  # 如果 b 沒有父節點
        root = b  # b 是根節點
        break
p, q = input().split()  # 如果 p 是晚輩輸出負值，如果 p 是長輩輸出正值，平輩輸出 0
dp, dq = 0, 0  # 從根節點往下算的距離
curr = p  # 目前的節點
while curr != root:  # 從 p 往上走到根節點
    dp += 1
    curr = parent[curr]
curr = q  # 目前的節點
while curr != root:  # 從 q 往上走到根節點
    dq += 1
    curr = parent[curr]
print(dq - dp)  # 輸出答案

ZeroJudge 解題筆記：k645. 數學得力工具

作者：王一哲
日期：2025年12月3日


ZeroJudge 題目連結：k645. 數學得力工具

解題想法

這題要先用 + 分割字串，取出字串中的數字，將數字由小到大排序，再將數字用 + 連接後輸出。如果用 Python 解題，可以用 split 分割字串，用 sorted 排序數字，用 join 連接字串，一行解。用 C++ 解題則會比較麻煩一點。

Python 程式碼

一行解，使用時間約為 40 ms，記憶體約為 3.3 MB，通過測試。

print("+".join(sorted(list(input().split("+")))))

C++ 程式碼

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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s, num = ""; getline(cin, s);
    vector<string> eq;
    for(char c : s) {
        if (c == '+') {
            eq.push_back(num);
            num = "";
        } else {
            num += c;
        }
    }
    eq.push_back(num);
    sort(eq.begin(), eq.end());
    for(int i=0; i<(int)eq.size(); i++) {
        cout << eq[i] << "+\n"[i == (int)eq.size()-1];
    }
    return 0;
}

ZeroJudge 解題筆記：k622. [棕]0-1背包問題

作者：王一哲
日期：2025年12月2日


ZeroJudge 題目連結：k622. [棕]0-1背包問題

解題想法

標準的背包問題。用一個陣列 dp 代表各種總重量對應的最大價值總和，依序讀取每樣物品的價值 p 及重量 w，從 dp 最後一項往回檢查到 dp[w] 為止，更新每一項的最大價值總和。

題目敘述有誤，物品重量上限不是 $10^4$，是 $10^7$。由於測資中物品重量大值為 $10^7$，用 C++ 解題時，如果將 array 開在 main 之中，倒數第二筆測資會遇到記憶體區段錯誤；如果將 array 開在 main 外面，在記憶體限制為 64 MB 的條件下，理論上最大長度為 $1.6 \times 10^7$ ，但我送程解答時會遇到記憶體區段錯誤。改用 vector 才能過關。至於 Python 則是怎麼樣都過不了。

這題的物品價值上限為 $10^8$，數量上限為 $10^9$，理論上價值總和應該會超過 int 的上限。如果用 long long 儲存 dp 的資料，會超過記憶體上限。改用 int 儲存 dp 的資料才能過關。

Python 程式碼

倒數第2筆測資超出記憶體上限，最後一筆測資超時。

n, k = map(int, input().split())
weight = list(map(int, input().split()))
price = list(map(int, input().split()))
dp = [0]*(k+1)
for w, p in zip(weight, price):
    for i in range(k, w-1, -1):
        dp[i] = max(dp[i], dp[i-w] + p)
print(dp[-1])

ZeroJudge 解題筆記：k621. [紅]括號匹配問題

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


ZeroJudge 題目連結：k621. [紅]括號匹配問題

解題想法

自訂函式 check，輸入一行字串 s，檢查 s 之中的括號是否能配對。用堆疊 st 儲存讀到的左括號，如果讀到右括號，檢查 st 最後一項是否能與這個右括號配對，如果可以配對則移除 st 最後一項；如果不能配對則印出 Wrong，跳出函式。如果函式可以執行到最後一行，印出 Right。

Python 程式碼

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

def check(s):
    st = []
    left = ("{", "[", "(")
    right = {"}": 0, "]": 1, ")":2}
    for c in s:
        if c in "{[(":
            st.append(c)
        else:
            if st and st[-1] == left[right[c]]:
                st.pop()
            else:
                print("Wrong")
                return
    print("Right")

check(input())