ZeroJudge 解題筆記：k615. 蝸牛的踩地雷攻略 2 (掃雷)

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


ZeroJudge 題目連結：k615. 蝸牛的踩地雷攻略 2 (掃雷)

解題想法

用二維串列儲存地圖，在最右側、最下方加上底線當作哨兵。接下來依序掃過地圖每一格，遇到不是數子的格子就跳過；計算周圍 8 格未翻開的格子數量 space 以及標記的數量 bomb，如果 space 大於 0 而且 bomb 等於這格的數字，則這格周圍的炸彈都已經被標記，這格改成 0。

Python 程式碼

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

n, m = map(int, input().split())
grid = [list(input() + '_') for _ in range(n)]
grid.append(['_']*(m+1))
for r in range(n):
    for c in range(m):
        if not grid[r][c].isnumeric(): continue
        bomb, space = 0, 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] == '#':
                space += 1
            elif grid[nr][nc] == 'P':
                bomb += 1
        if space > 0 and bomb == int(grid[r][c]):
            grid[r][c] = 'O'
for row in grid[:n]:
    print("".join(row[:m]))

ZeroJudge 解題筆記：k475. 4或7的倍數

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


ZeroJudge 題目連結：k475. 4或7的倍數

解題想法

先讀取第一行的數字 a, b 以及要輸出的字串 c。接下來一次讀取一行字串，依序檢查字串中的每個字元，計算這行之中有幾個 a 或 b 的倍數，或是數字之中含有 a 或 b，最後輸出對應數量的 c。這樣的檢查方式比較慢，但是寫起來很直接。

Python 程式碼

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

import sys

a, b, word = sys.stdin.readline().split()
an = int(a); bn = int(b)
for line in sys.stdin:
    line = line.strip()
    n = len(line)
    num = ""
    cnt = 0
    idx = 0
    while idx < n:
        c = line[idx]
        if c.isdigit():
            num += c
        else:
            if num.isdigit() and (a in num or b in num or int(num)%an == 0 or int(num)%bn == 0): cnt += 1
            num = ""
        idx += 1
    if num.isdigit() and (a in num or b in num or int(num)%an == 0 or int(num)%bn == 0): cnt += 1
    if cnt > 0: print(word*cnt)

ZeroJudge 解題筆記：k376. 求包含最大質因數的數

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


ZeroJudge 題目連結：k376. 求包含最大質因數的數

解題想法

先用埃拉托斯特尼篩法建立1 ~ 20000 之間的質數表 primes。讀取 n 個數字 m，用內建的二分搜尋法從 primes 之中找 m 插入的位置 idx，如果 m 是質數，再檢查 m 是否是新的答案； 如果 m 不是質數，從 idx 往回找最大的質因數 fac，再檢查 fac 是否是新的答案。

Python 程式碼

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

from bisect import bisect_left

""" 建立 1 ~ 20000 之間的質數表 """
maxn = 20000
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
primes = [i for i in range(maxn+1) if sieve[i]]
""" 讀取 n 個數字找答案 """
ans, fmax = 0, 0  # 答案，最大質因數
n = int(input())
for _ in range(n):
    m = int(input())
    idx = bisect_left(primes, m)  # 用二分搜尋法找 m 在 primes 之中插入的位置
    if m == primes[idx] and m >= fmax and m > ans:  # 如果 m 是質數
        ans = m; fmax = m
    else:  # 如果 m 不是質數，從 idx 往回找最大的因數
        for i in range(idx, -1, -1):
            fac = primes[i]
            if m%fac == 0:
                if fac >= fmax and m > ans:
                    ans = m; fmax = fac
                break
print(ans)

ZeroJudge 解題筆記：k205. 蝸牛的踩地雷攻略 1 (插旗)

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


ZeroJudge 題目連結：k205. 蝸牛的踩地雷攻略 1 (插旗)

解題想法

我用二維陣列儲存地圖，並在周圍加上 _ 當作哨兵避免出界。依序掃過每個格子，如果這格不是數字，就跳過找下一格；如果是數字，計算周圍 8 格有幾個 # 或 P，並記錄這些位置，如果 # 及 P 的數量等於這格標記的數字，剛才記錄的位置都改成 P。

Python 程式碼

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

n, m = map(int, input().split())
grid = [list(input() + '_') for _ in range(n)]
grid.append(['_']*(m+1))
for r in range(n):
    for c in range(m):
        if not grid[r][c].isnumeric(): continue
        cnt = 0
        bomb = []
        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] == '#' or grid[nr][nc] == 'P':
                cnt += 1
                bomb.append((nr, nc))
        if cnt == int(grid[r][c]):
            for nr, nc in bomb:
                grid[nr][nc] = 'P'
for row in grid[:n]:
    print("".join(row[:m]))

ZeroJudge 解題筆記：k076. 簡易棒球模擬

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


ZeroJudge 題目連結：k076. 簡易棒球模擬

解題想法

這題跟〈c297. APCS-2016-1029-4棒球遊戲〉很像，按照題目的敘述處理壘上跑者、得分及出局數即可。

Python 程式碼

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

bases = list(map(int, input().split()))
hit = int(input())
runs = 0
if hit == 4:
    runs = 1 + sum(bases)
    bases = [0, 0, 0]
elif hit == 3:
    runs = sum(bases)
    bases = [1, 0, 0]
elif hit == 2:
    runs = sum(bases[:2])
    if bases[2] == 1:
        bases = [1, 1, 0]
    else:
        bases = [0, 1, 0]
elif hit == 1:
    if bases[0] == 1:
        runs = 1
        bases[0] = 0
    if bases[1] == 1:
        bases[0] = 1
        bases[1] = 0
    if bases[2] == 1:
        bases[1] = 1
    bases[2] = 1
print(runs)
print(*bases)

ZeroJudge 解題筆記：j568. 無預警小考 ( 上 )

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


ZeroJudge 題目連結：j568. 無預警小考 ( 上 )

解題想法

按照題目要求的格式組合答案。我在 Python 先將所有要輸出的內容用字串格式儲存在串列之中，最後再接成很長的字串用 sys.stdout.write 輸出；在 C++ 則是每組合完一小段答案就用 cout 輸出。

Python 程式碼

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

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    result = ["請使用配方法解下列一元二次方程式\n\n"]
    n = int(sys.stdin.readline())
    for i in range(1, n+1):
        cof = list(map(int, sys.stdin.readline().split()))
        eq = str(i) + ". "
        if cof[0] == 1: eq += "x^2"
        elif cof[0] == -1: eq += "-x^2"
        else: eq += str(cof[0]) + "x^2"
        if cof[1] == 0: pass
        elif cof[1] == 1: eq += "+x"
        elif cof[1] > 1: eq += "+" + str(cof[1]) + "x"
        elif cof[1] == -1: eq += "-x"
        else: eq += str(cof[1]) + "x"
        if cof[2] == 0: pass
        elif cof[2] > 0: eq += "+" + str(cof[2])
        else: eq += str(cof[2])
        eq += "=0\n\n"
        result.append(eq)
    result.append("考試要加油口屋\n\n")
    sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a586. 4. 捷運計價問題

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


ZeroJudge 題目連結：a586. 4. 捷運計價問題

解題想法

我用 BFS 解題，由於這題可以用不同的走法到達同一座車站，不能用是否已走訪這座車站來排除重複的走法。改用一個字典 prices 儲存由起點到達各車站的最低票價，如果經由現在的路線走到這座車站的票價大於目前已知的最低票價，代表這個走法走到終點時不可能是新的最低票價，不需要加入待走訪佇列 que 之中。由於 que 要儲存的資料為 (車站編號, 目前的票價, 經過站數, 轉乘路線數)，有 1 個字串及 3 個整數，在 C++ 我另外定義 struct Station 儲存資料。

Python 程式碼

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

from collections import defaultdict, deque

n = int(input())  # 接下來有 n 行
graph = defaultdict(list)  # 車站連接方式，無向圖
for _ in range(n):
    u, v = input().split()
    graph[u].append(v)
    graph[v].append(u)
start, end = input().split()  # 起點、終點
if start == end:  # 特例，起點、終點相同
    print(10)  # 最低票價 10 元
else:
    # 到各車站所需最低票價，預設為無窮大
    prices = defaultdict(lambda : float('inf'))
    prices[start] = 10  # 到起點票價 10 元
    # 待走訪佇列，資料為 (車站編號, 目前的票價, 經過站數, 轉乘路線數)
    que = deque([(start, 10, 0, 0)])
    while que:  # 用 BFS 找走到終點的最低票價
        curr, fee, cnt, trans = que.popleft()
        if curr == end:  # 走到終點
            prices[end] = min(prices[end], fee)  # 更新走到終點的最低票價
            continue  # 找下一個點，可能有其它更低票價的走法
        if fee > prices[end]:  # 目前票價大於已知到達終點的最低票價
            continue  # 找下一個點，不可能是新的最低票價
        for nxt in graph[curr]:  # 依序讀取相連的車站
            new_cnt = cnt + 1  # 經過站數加 1
            if nxt[0] != curr[0]: new_trans = trans + 1  # 轉乘不同路線
            else: new_trans = trans
            new_fee = 10 + new_cnt//3*5 + new_trans*5  # 新的票價
            if new_fee > prices[nxt]:  # 到達此站的票價超過已知的最低票價
                continue  # 找下一個點，不可能是新的最低票價
            prices[nxt] = new_fee
            que.append((nxt, new_fee, new_cnt, new_trans))
    print(prices[end])

ZeroJudge 解題筆記：i646. 排列組合-排列

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


ZeroJudge 題目連結：i646. 排列組合-排列

解題想法

這題原來應該是要考用函式遞迴及回溯，但是在 Python 可以用 itertools.permutatinos 産生所有的排列，在 C++ 可以用 algorithm 函式庫的 next_permutation。

Python 程式碼

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

import sys

def perm(n, s):
    if len(s) == n:
        print(s)
        return 
    for i in range(n):
        c = chr(i + ord('a'))
        if c in s: continue
        perm(n, s+c)

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    perm(n, "")

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

import sys
from itertools import permutations

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n == 0: break
    chars = [chr(i + ord('a')) for i in range(n)]
    for perm in permutations(chars):
        s = "".join(perm)
        result.append(f"{s}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：i706. B.永遠ㄉ神（yyds）

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


ZeroJudge 題目連結：i706. B.永遠ㄉ神（yyds）

解題想法

用堆疊 st 記錄前方的人身高及索引值，堆疊中先放入 (-float('inf'), 0) 避免遇到空堆疊的狀況。每次讀取第 i 個人的身高 h，用 while 迴圈從 st 最上方開始檢查，移除所有身高大於 h 的資料，當 while 迴圈結束之後，st 最上方的資料的索引值就是要輸出的答案，再將 (h, i) 加入 st。

Python 程式碼

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

import sys

n = int(sys.stdin.readline())
st = [(-float('inf'), 0)]
ans = []
for i, h in enumerate(map(int, sys.stdin.readline().split()), start=1):
    while st[-1][0] >= h: st.pop()
    ans.append(str(st[-1][1]))
    st.append((h, i))
sys.stdout.write(" ".join(ans) + "\n")

ZeroJudge 解題筆記：a584. 2. 親等關係

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


ZeroJudge 題目連結：a584. 2. 親等關係

解題想法

題目看起來像是樹，但其實用字典及串列儲存無向圖，再用 BFS 找兩個人之間的距離就過關了。如果用 Python 解題可以用 collections.defaultdict 存圖，這樣可以不需要檢查 key 值是否已在字典之中。我用 Python 寫這題很順利，反而是用 C++ 解題是吃了好幾次 WA，後來發現測資在第 1 行的人數 n 之後換行的格式可能比較特別，我一開始只有 cin.ignore() 跳過一個 \n，但是這樣會吃 WA，改成用 getline 讀取一整行才過關。

Python 程式碼

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

from collections import defaultdict, deque

""" 讀取測資並存圖 """
n = int(input())  # n 個人
graph = defaultdict(list)  # 無向圖，用字串當作 key，list 裡面存字串
for _ in range(n):  # 讀取 n 行
    names = input().split()  # 名字，用空格分割
    parent = names[0]  # 父節點名稱
    children = names[1:]  # 子節點名稱，可能有多個子節點
    for child in children:  # 依序讀取每個子節點名稱
        graph[parent].append(child)  # 儲存節點之間連接的方式
        graph[child].append(parent)
""" 讀取最後一行並用 BFS 找答案 """
a, b = input().split()  # 要找距離的兩個人名
que = deque([(a, 0)])  # 待走訪佇列，資料為 (節點, 距離)，先存入 (a, 0)
ans = 0  # 答案
visited = {a}  # 用 set 儲存已走訪節點名稱
while que:  # 如果 que 有資料繼續執行
    u, d = que.popleft()  # 從 que 開頭取出節點 u、距離 d
    if u == b:  # 如果 u 等於 b，找到終點
        ans = d  # 答案為 d
        break  # 中止迴圈
    for v in graph[u]:  # 依序讀取與 u 相連的節點 v
       if v in visited: continue  # 如果 v 已走訪過，找下一個節點
       visited.add(v)  # v 加入 visited
       que.append((v, d+1))  # (v, d+1) 加入 que
# 結束 BFS，印出答案
print(ans)

ZeroJudge 解題筆記：i645. 排列組合-組合

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


ZeroJudge 題目連結：i645. 排列組合-組合

解題想法

這題原來應該是要考用函式遞迴及回溯，但是在 Python 可以用 itertools.combinations 産生所有的組合。

Python 程式碼

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

import sys

def comb(n, m, start, s):
    if len(s) == m:
        print(s)
        return 
    for i in range(start, n):
        c = chr(i + ord('a'))
        comb(n, m, i+1, s+c)

for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    comb(n, m, 0, "")

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

import sys
from itertools import combinations

result = []
for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    chars = [chr(i + ord('a')) for i in range(n)]
    for comb in combinations(chars, m):
        s = "".join(comb)
        result.append(f"{s}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：i644. 列舉八皇后問題所有解

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


ZeroJudge 題目連結：i644. 列舉八皇后問題所有解

解題想法

經典的題目，用函式遞迴及回溯比較好寫。

Python 程式碼

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

def solve_n_queens(n):  # 自訂函式，解 n 皇后問題
    # 回溯，代入目前的列，已用的欄、左上右下斜線、右上左下斜線
    def backtrack(row, cols, diag1, diag2):
        if row == n:  # 遞迴出口，填入第 n 列，找到一組解
            # 將 borad 儲存的欄與列組成 tuple，依照欄排序，存入 ans
            # 由 ans 取出列的順序，轉成字串，存入 solutions
            ans = sorted([(c, i) for i, c in enumerate(board, start=1)])
            solutions.append("".join([str(i) for _, i in ans]))
        for col in range(n):  # 依序測試第 0 ~ n-1 欄
            d1 = row - col  # 左上右下斜線
            d2 = row + col  # 右上左下斜線
            # 如果 col, d1, d2 不在已用的集合之中，可以用這個位置
            if col not in cols and d1 not in diag1 and d2 not in diag2:
                board[row] = col  # row 列使用的欄為 col
                # 遞迴，找下一列，代入原來的集合分別與 col, d1, d2 的聯集
                backtrack(row+1, cols | {col}, diag1 | {d1}, diag2 | {d2})
    # end of backtrack
    solutions = []  # 所有的解
    board = [-1]*n  # 第 row 列的皇后放在第 col 欄
    backtrack(0, set(), set(), set())  # 呼叫 backtrack 求解
    return solutions  # 回傳所有的解
# end of solve_n_queens
all_solutions = solve_n_queens(8)
all_solutions.sort()  # 依照字典排序
for i, sol in enumerate(all_solutions, start=1):
    print(f"{i:d}: {sol:s}")

ZeroJudge 解題筆記：i510. 尋找子字串

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


ZeroJudge 題目連結：i510. 尋找子字串

解題想法

這題用字串的 find 功能很好寫。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    s, t = sys.stdin.readline().split()
    idx = s.find(t)
    if idx == -1: print("No")
    else: print(f"Yes\npos: {idx:d}")

ZeroJudge 解題筆記：i213. stack 練習

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


ZeroJudge 題目連結：i213. stack 練習

解題想法

這題是堆疊 (stack) 的基本操作，在 Python 可以用 list 代替，在 C++ 可以用 stack 或 vector。

Python 程式碼

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

n = int(input())
st = []
for _ in range(n):
    line = input().split()
    if len(line) == 1:
        if line[0] == '2':
            if st: print(st[-1])
            else: print(-1)
        elif line[0] == '3':
            if st: st.pop()
    else:
        st.append(int(line[1]))

ZeroJudge 解題筆記：i177. 小畫家 (Painter)

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


ZeroJudge 題目連結：i177. 小畫家 (Painter)

解題想法

這題用 BFS ，我習慣在旁邊加一圈哨兵，這樣可以不需要檢查是否出界。

Python 程式碼

加哨兵，不需要檢查是否出界，使用時間約為 0.4 s，記憶體約為 14.8 MB，通過測試。

from collections import deque

h, w, si, sj, z = map(int, input().split())
grid = [list(map(int, input().split())) + [-1] for _ in range(h)]
grid.append([-1]*(w+1))
color = grid[si-1][sj-1]
if color != z:
    que = deque([(si-1,sj-1)])
    grid[si-1][sj-1] = z
    while que:
        r, c = que.popleft()
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            nr, nc = r+dr, c+dc
            if grid[nr][nc] == color:
                grid[nr][nc] = z
                que.append((nr, nc))
for row in grid[:h]: print(*row[:w])

ZeroJudge 解題筆記：i121. 英文字母大小寫的抉擇

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


ZeroJudge 題目連結：i121. 英文字母大小寫的抉擇

解題想法

這題應該是專門出給 Python 的題目，因為 Python 的字串內建 capitalize(), upper(), title(), lower() 這四種格式，如果要用 C++ 寫這題會很麻煩。

Python 程式碼

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

line = input()
style = int(input())
if style == 1:
    print(line.capitalize())
elif style == 2:
    print(line.upper())
elif style == 3:
    print(line.title())
else:
    print(line.lower())

ZeroJudge 解題筆記：i025. 真因數和 (小 n)

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


ZeroJudge 題目連結：i025. 真因數和 (小 n)

解題想法

因為測資不太，用試除法測試 $i = 2$ 到 $i = floor(\sqrt{n})$ 之間的整數是否為因數，如果 $i$ 是因數，則答案要加上 $i$ 及 $n/i$，最後再檢查 $n$ 是否為平方數，如果是平方數則答案要再減去 $\sqrt{n}$。

Python 程式碼

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

n = int(input())
if n == 1: print(0)  # 特例
else:
    root = int(n**0.5)
    isum = 1  # 所有真因數的合，找到真因數直接加起來就好
    for i in range(2, root+1):
        if n%i == 0:
            isum += i + (n//i)
    if root*root == n: isum -= root  # 完全平方數會多加一個 root，要扣掉
    print(isum)

ZeroJudge 解題筆記：h495. 農家樂(Agricola)

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


ZeroJudge 題目連結：h495. 農家樂(Agricola)

解題想法

由於各項目的分數與數量沒有特定的數學關係，我只想到對每個項目分別建一個串列，記錄各數量對應的分數。

Python 程式碼

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

field = (-1, -1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
enclosure = (-1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
wheat = (-1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
vegetable = (-1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
sheep = (-1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
pig = (-1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
catle = (-1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
t = int(input())
for _ in range(t):
    arr = tuple(map(int, input().split()));
    score = field[arr[0]] + enclosure[arr[1]] + wheat[arr[2]] + vegetable[arr[3]] + \
            sheep[arr[4]] + pig[arr[5]] + catle[arr[6]] - arr[7] + arr[8] + arr[9] + \
            2*arr[10] + 3*arr[11] + arr[12]
    print(score)

ZeroJudge 解題筆記：h089. 疊披薩

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


ZeroJudge 題目連結：h089. 疊披薩

解題想法

這題就是河內塔。

Python 程式碼

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

def hanoi(n, src, aux, dst):
    if n == 1:
        print(f"from {src:s} to {dst:s}")
        return
    hanoi(n-1, src, dst, aux)
    print(f"from {src:s} to {dst:s}")
    hanoi(n-1, aux, src, dst)

hanoi(int(input()), "A", "B", "C")

ZeroJudge 解題筆記：h206. 強者就是要戰，但......什麼才是強者呢？

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


ZeroJudge 題目連結：h206. 強者就是要戰，但......什麼才是強者呢？

解題想法

這題考分治法。

Python 程式碼

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

def solve(nums, big):  # 自定函式，代入串列，是否取較大的值
    n = len(nums)  # 串列長度
    if n == 1: return nums[0]  # 遞迴出口，只剩一項，回傳此項
    left = nums[:n//2]  # 左半部
    right = nums[n//2:]  # 右半部
    mleft = solve(left, not big)  # 遞迴，代入左半部，big 的狀態要反過來
    mright = solve(right, not big)  # 遞迴，代入右半部，big 的狀態要反過來
    if big: return max(mleft, mright)  # 如果 big 為 True，取左、右兩半較大的值
    else: return min(mleft, mright)  # 反之，取左、右兩半較小的值

n = int(input())
arr = list(map(int, input().split()))
print(solve(arr, True))

ZeroJudge 解題筆記：h075. 成績排名

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


ZeroJudge 題目連結：h075. 成績排名

解題想法

這題輸出的加權平均可能是小數或整數，因為分母是10，如果是小數則印出到小數點後一位。由於題目要求的比序依序為加權平均、資訊、數學、英文成績由高到低，如果前面4項成績相同，再依照座號由小到大排序，如果使用 Python，可以將每個人的加權平均、資訊、數學、英文、座號的負值等5項組成 tuple 存到串列當中，用 sort 排序串列時會自動依照 tuple 之中的數值由小到大排序。如果使用 C++，可以用vector 儲存每個人資料，也可以自訂結構體，不過這樣就需要自己寫排序用的比較式。

Python 程式碼

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

n = int(input())
students = []  # (tot, cs, math, english, -num)
for _ in range(n):
    num, cs, math, english = list(map(int, input().split()))
    tot = cs*5 + math*3 + english*2
    students.append((tot, cs, math, english, -num))
students.sort(reverse=True)
for student in students:
    tot, num = student[0], -student[4]
    if tot%10 == 0: print(f"{num:d} {tot//10:d}")
    else: print(f"{num:d} {tot/10:.1f}")

ZeroJudge 解題筆記：g640. 璽羽的壽司

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


ZeroJudge 題目連結：g640. 璽羽的壽司

解題想法

因為壽司沒有限量，可以重複賣出同樣價格的壽司，所以只要先將所有的壽司價格由小到大排序，再用二分搜尋法從所有壽司價格找等於顧客標準或是大於標準且最接近的值。

Python 程式碼

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

from bisect import bisect_left

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
tot = 0
for b in map(int, input().split()):
    idx = bisect_left(arr, b)
    if idx == n: continue
    tot += arr[idx]
print(tot)

ZeroJudge 解題筆記：g499. 109北二1.感測器的比較

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


ZeroJudge 題目連結：g499. 109北二1.感測器的比較

解題想法

這題理論上可以用 while 迴圈計算 a 的個位數為 0 且 b 的個位數為 1 的數量，每次計算後將 a, b 除以 2，直到 a, b 其中一個等於 0 為止，但是這樣的速度很慢，用 C++ 可以過關，但是用 Python 在第 16 筆測資會超時。 改用位元運算，因為題目要求 a 的位數為 0、b 的位數為 1，先取 a XOR b，這樣位數不同的部分計算結果為 1，再與 b 取 AND，只有 a 的位數為 0、b 的位數為 1 的部分計算結果為 1。如果是 Python 可以用 bin 將計算結果轉成二進位制的字串，計算其中有幾個 1 即可。

Python 程式碼

第10筆測資開始超時。

data = list(map(int, input().split()))  # 讀取資料
n = data[0]  # 共有 n 對資料
cnt = 0  # A 測到0，B 測到 1 的次數
for i in range(1, 2*n+1, 2):  # 讀取 n 對資料
    a, b = data[i], data[i+1]  # a, b 的值
    while a > 0 or b > 0:  # 當 a 大於 0 或 b 大於 0 繼續執行 
        if a%2 == 0 and b%2 == 1: cnt += 1  # 如果 a 的個位數為 0 且 b 的個位數為 1，cnt 加 1
        a >>= 1; b >>= 1  # a, b 除以 2
print(cnt)  # 印出答案

改用 sys.stdin.readline 及 sys.stdout.write 加速，第16筆測資開始超時。

import sys

data = list(map(int, sys.stdin.readline().split()))  # 讀取資料
n = data[0]  # 共有 n 對資料
cnt = 0  # A 測到0，B 測到 1 的次數
for i in range(1, 2*n+1, 2):  # 讀取 n 對資料
    a, b = data[i], data[i+1]  # a, b 的值
    while a > 0 or b > 0:  # 當 a 大於 0 或 b 大於 0 繼續執行 
        if a&1 == 0 and b&1 == 1: cnt += 1  # 如果 a 的個位數為 0 且 b 的個位數為 1，cnt 加 1
        a >>= 1; b >>= 1  # a, b 除以 2
sys.stdout.write(f"{cnt:d}\n")  # 印出答案

改用位元運算，使用時間約為 2.8 s，記憶體約為 255.7 MB，通過測試。

import sys

data = list(map(int, sys.stdin.readline().split()))  # 讀取資料
n = data[0]  # 共有 n 對資料
cnt = 0  # A 測到0，B 測到 1 的次數
for i in range(1, 2*n+1, 2):  # 讀取 n 對資料
    a, b = data[i], data[i+1]  # a, b 的值
    cnt += sum(c == '1' for c in bin(b & (a^b))[2:])
sys.stdout.write(f"{cnt:d}\n")  # 印出答案

ZeroJudge 解題筆記：g489. 社團點點名

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


ZeroJudge 題目連結：g489. 社團點點名

解題想法

題目說明有問題，測資中有不在社團名單裡的出席者，所以答案有可能是負的。用集合 members 儲存社團成員學號，再用另一個集合 present 儲存非社團成員但有出席的人，最後將兩者的數量相減即可。

Python 程式碼

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

m, n = map(int, input().split())  # 社團人數 m，有到的人數 n
members = set([input() for _ in range(m)])  # 社團成員學號
present = set()  # 非社團成員但有出席的人
for _ in range(n):  # 讀取 n 行資料
    s = input()  # 學號
    if s in members: members.remove(s)  # s 是社團成員，從 members 移除 s
    else: present.add(s)  # s 不是社團成員，s 加入 present
print(len(members) - len(present))

ZeroJudge 解題筆記：g488. COVID-101

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


ZeroJudge 題目連結：g488. COVID-101

解題想法

題目給的遞迴式為 $$ n(x) = n(x-1) + x^2 - x + 1 $$ 列出前幾項找規律 $$ \begin{align*} n(1) &= 1\\ n(2) &= n(1) + 2^2 - 2 + 1\\ n(3) &= n(2) + 3^2 - 3 + 1\\ n(4) &= n(3) + 4^2 - 4 + 1\\ n(5) &= n(4) + 5^2 - 5 + 1\\ n(x) &= n(x-1) + x^2 - x + 1 \end{align*} $$ 將以上的式子相加，可以看出 $n(1)$ 到 $n(x-1)$ 會兩兩對消，因此 $$ \begin{align*} n(x) &= (2^2 + 3^2 + 4^2 + \dots + x^2) - (2 + 3 + 4 + \dots + x) + x\\ &= \sum_{i = 1}^x i^2 - 1 - \sum_{i=2}^x i + x\\ &= \frac{x(x+1)(2x+1)}{6} - \frac{(x+2)(x-1)}{2} + x - 1 \end{align*} $$

Python 程式碼

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

x = int(input())
print(x*(x+1)*(2*x+1)//6 - (x+2)*(x-1)//2 + x - 1)

遞迴解，使用時間約為 42 ms，記憶體約為 3.3 MB，通過測試。

def func(x):
    if x == 1: return 1
    return func(x-1) + x*x - x + 1

print(func(int(input())))

ZeroJudge 解題筆記：g422. PD.紅血球的快遞任務

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


ZeroJudge 題目連結：g422. PD.紅血球的快遞任務

解題想法

這題考 Dijkstra’s Shortest Path Algorithm。

Python 程式碼

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

import heapq

n, m, t = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))
cost = [float('inf')]*n
cost[0] = 0
pq = [(0, 0)]  # (cost, node)
while pq:
    cur_cost, u = heapq.heappop(pq)
    if u == t: break  # 已經走到終點
    if cur_cost > cost[u]: continue  # 如果已經找到比較低的成本，找下一筆資料
    for v, w in graph[u]:  # 依序取出 u 的子節點 v、成本 w
        if cost[u] + w < cost[v]:  # 如果從 u 走到 v 的成本較低
            cost[v] = cost[u] + w
            heapq.heappush(pq, (cost[v], v))
print(cost[t])

ZeroJudge 解題筆記：g309. pC. 傳遞杯子蛋糕(Cupcake)

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


ZeroJudge 題目連結：g309. pC. 傳遞杯子蛋糕(Cupcake)

解題想法

先讀取節點之間的關係，如果是 -1 代表沒有這個子節點。用串列 cnt 儲存每個節點分配到的數量，根節點先分到全部的數量 k。接下來用 BFS 走訪每個節點，計算要平分的數量 m 及平均值 avg。

Python 程式碼

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

from collections import deque

n, k = map(int, input().split())  # n 個節點，有 k 個東西要分配
tree = [[0, 0] for _ in range(n)]  # 節點的關係，i: [left, right]
for _ in range(n):  # 讀取 n 行資料
    i, left, right = map(int, input().split())
    tree[i] = [left, right]
cnt = [0]*(n)  # 各節點分配到的數量
cnt[0] = k  # 根節點先分到全部的數量
que = deque([0])  # 待走訪節點，先放入 0
while que:  # 若 que 還有資料繼續執行
    u = que.popleft()  # 從 que 開頭取出待走訪節點 u
    left, right = tree[u]  # u 的左節點、右節點
    m = 1 + (left != -1) + (right != -1)  # 共有 m 個點要平分數量，至少有 1 個點
    tot = cnt[u]  # 目前 u 節點擁有的數量
    avg = tot//m  # tot 除以 m 的平均值
    cnt[u] = avg + tot%m  # u 的數量改成 avg 加上 tot 除以 m 的餘數
    if left != -1:  # 如果有左子節點
        cnt[left] = avg; que.append(left)  # left 分到的數量為 avg，left 加入 que
    if right != -1:
        cnt[right] = avg; que.append(right)  # right 分到的數量為 avg，right 加入 que
print(*cnt)

ZeroJudge 解題筆記：g308. pB. 跳跳布朗尼(Brownie)

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


ZeroJudge 題目連結：g308. pB. 跳跳布朗尼(Brownie)

解題想法

將傳送門狀態存入串列 portal，將每格的布朗尼數量存入串列 brownie。起始位置為 cur，會先拿到這格的布朗尼，更新拿到的布朗尼總數 cnt，再從 protal 讀取傳送的目的地 nxt，將用過的傳送門改成 -1。用 while 迴圈重複以上的過程，直到 nxt 為 -1 時停止。

Python 程式碼

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

n, t = map(int, input().split())
portal = list(map(int, input().split()))
brownie = list(map(int, input().split()))
cur = t  # 目前的位置
cnt = brownie[cur]  # 拿到的布朗尼總數，預設為目前位置的數量
brownie[cur] = 0  # 將目前位置的布朗尼總數歸零
nxt = portal[cur]  # 下一個位置
portal[cur] = -1  # 將目前位置要傳送的位置設成 -1，代表已經走過這格
while nxt != -1:  # 當 nxt 不等於 -1 時繼續執行
    cur = nxt  # 更新 cur
    cnt += brownie[cur]  # 加上目前位置的數量
    brownie[cur] = 0  # 將目前位置的布朗尼總數歸零
    nxt = portal[cur]  # 下一個位置
    portal[cur] = -1  # 將目前位置要傳送的位置設成 -1，代表已經走過這格
print(cnt)  # 印出答案

ZeroJudge 解題筆記：g307. pA. 為了好吃的蘋果派(Apple Pie)

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


ZeroJudge 題目連結：g307. pA. 為了好吃的蘋果派(Apple Pie)

解題想法

依序讀取編號 i = 0 到 n-1 的分數，將分數排序後存入串列 scores，計算除了最高、最低分數以外的平均分數 avg，如果 avg 大於等於 t，將 i 存入答案之中。

Python 程式碼

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

n, k, t = map(int, input().split())
ans = []
for i in range(n):
    scores = sorted(map(int, input().split()))
    avg = sum(scores[1:-1])/(k-2)
    if avg >= t: ans.append(i)
if not ans:
    print("A is for apple.")
else:
    for a in ans:
        print(a)

ZeroJudge 解題筆記：g217. A.成雙成對（pairs）

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


ZeroJudge 題目連結：g217. A.成雙成對（pairs）

解題想法

只要數量最多的數字不超過一半就可以符合要求。

Python 程式碼

collections.Counter 有一個很好用的功能 most_common，語法為

[Counter物件].most_common(數量)

回傳值格式為 list，串列中的資料格式為 tuple，內容為 (key, 數量)。使用時間約為 16 ms，記憶體約為 3.4 MB，通過測試。

from collections import Counter

t = int(input())
for _ in range(t):
    n = int(input())
    cnt = Counter(map(int, input().split()))
    imax = cnt.most_common(1)[0][1]
    print("Yes" if imax <= n//2 else "No")