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

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

ZeroJudge 解題筆記：f935. 消失的二十年 - 續

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


ZeroJudge 題目連結：f935. 消失的二十年 - 續

解題想法

最低價 min_price 預設為第 0 天的價格，最大獲利 max_proift 預設為 0。依序讀取第 1 天到最後一天的價格 price，如果當天賣出的獲利大於目前的 max_profit，更新 max_profit、最低買價 buy、最高賣價 sell； 如果 price 小於 min_price，更新 min_price。最後如果找不到低於 min_price 的𧶠價，max_profit 等於 0，輸出 0 -1 -1； 反之，輸出 max_profit buy sell。

Python 程式碼

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

prices = list(map(int, input().split()))  # 每天的價格
min_price = prices[0]  # 最低價格，預設為第 0 天的價格
max_profit = 0  # 最大獲利，預設為 0
buy = sell = -1  # 最大獲利對應的最低買價、最高賣價，預設為 -1
for price in prices[1:]:  # 依序讀取讀取第 1 天到最後一天的價格
    if price - min_price > max_profit:  # 更高的獲利
        max_profit = price - min_price  # 更新最大獲利
        buy = min_price  # 更新最低買價
        sell = price  # 更新最高賣價
    elif price < min_price:  # 更低的價格
        min_price = price  # 更新最低價格
if max_profit == 0: print("0 -1 -1")
else: print(f"{max_profit:d} {buy:d} {sell:d}")

ZeroJudge 解題筆記：f929. 程式老師的作業

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


ZeroJudge 題目連結：f929. 程式老師的作業

解題想法

這題如果直接用 index 或是 find 找陣列中第一個 0 的索引值，速度會太慢，無法通過最後一筆測資。用一個最小優先佇列儲存陣列中所有 0 的索引值，如果需要將第一個 0 改成指定的值時，從最小優先佇列取出開頭的資料就能找到要修改的索引值，速度快很多。

Python 程式碼

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

import sys, heapq

n = int(sys.stdin.readline())  # 陣列長度
arr = list(map(int, sys.stdin.readline().split()))  # 陣列內容
pq = [i for i, a in enumerate(arr) if a == 0]  # 所有 0 的索引值
m = int(sys.stdin.readline())  # m 次操作
lines = sys.stdin.readlines()  # 讀取所有剩下的資料
ans = []  # 答案
for line in lines:  # 依序讀取事先存在 lines 的資料
    cmd = list(map(int, line.split()))  # 指令
    if cmd[0] == 1:  # 如果指令開頭是 1
        if pq:  # 如果 pq 有資料
            idx = heapq.heappop(pq)  # 取出 pq 開頭的資料
            arr[idx] = cmd[1]  # 修改 arr[idx]
    elif cmd[0] == 2 and arr[cmd[1]] != 0:  # 如果指令開頭是 2 而且指定的位置不是 0
        arr[cmd[1]] = 0  # 將指定的位置改成 0
        heapq.heappush(pq, cmd[1])  # 將這個位置加入 pq
    elif cmd[0] == 3:  # 如果指令開頭是 3
        if pq: ans.append(str(pq[0]) + "\n")  # 如果 pq 有資料，將 pq 開頭的資料轉成字串加上 \n 存入 ans 
        else: ans.append("-1\n")  # 反之，將 -1\n 存入 ans
sys.stdout.write("".join(ans))  # 將 ans 的資料接成很長的字串再輸出

ZeroJudge 解題筆記：f928. 連環炸彈.................Boom！

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


ZeroJudge 題目連結：f928. 連環炸彈.................Boom！

解題想法

這題的標籤是「遞迴」，不過我是用 BFS 解題。先讀取這格的炸彈種類 k，如果 k 等於 1 只會炸掉自己，如果 k 等於 2 再檢查左右兩格，如果 k 等於 3 則檢查左、右兩側距離 k 及 2k 的格子。檢查過的格子如果有炸彈，將炸彈加入待走訪佇列 que，再將檢查過的格子改成 0。

Python 程式碼

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

from collections import deque

n = int(input())
bombs = list(map(int, input().split()))
que = deque([int(input())])
while que:
    x = que.popleft()
    k = bombs[x]  # 暫存這格的值
    bombs[x] = 0  # 將這格歸零
    if k == 2:  # 如果 k 等於 2，檢查左、右兩格是否出界、是否有炸彈
        if x-1 >= 0 and bombs[x-1] != 0: que.append(x-1)
        if x+1 < n and bombs[x+1] != 0: que.append(x+1)
    elif k >= 3:  # 如果 k 大於等於 3，檢查左、右四格是否出界、是否有炸彈
        if x-k >= 0 and bombs[x-k] != 0: que.append(x-k)
        if x-k-k >= 0 and bombs[x-k-k] != 0: que.append(x-k-k)
        if x+k < n and bombs[x+k] != 0: que.append(x+k)
        if x+k+k < n and bombs[x+k+k] != 0: que.append(x+k+k)
print(*bombs)

ZeroJudge 解題筆記：f885. 加總

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


ZeroJudge 題目連結：f885. 加總

解題想法

這題考數學，要先推導公式。首先用等差級數公式 $$ \frac{(n+a)(n-a+1)}{2} \geq x ~\Rightarrow~ n^2 + n - a^2 + a - 2x \geq 0 $$ 用公式解 $$ n = \frac{-1 \pm \sqrt{1^2 - 4 \times (-a^2 + a - 2x)}}{2} = \frac{-1 \pm \sqrt{4a^2 - 4a + 8x + 1}}{2} $$ 從範例測資來看，答案應該是正整數，因此上式的解要取正值，如果計算結果不是正整數，則用 math.ceil 向上取最接近的正整數。

Python 程式碼

這題有卡 I/O，如果每次計算完之後就用 print 印出答案，在最後一筆測資會超時。改用 sys.stdion.readlines() 一次讀取所有測資，再將所有的計算結果全部存進串列之中，最後再用 sys.stdout.write 及 join 合併要輸出的答案，盡量縮短運算時間。使用時間約為 0.3 s，記憶體約為 15.7 MB，通過測試。

import sys, math

lines = sys.stdin.readlines()
t = int(lines[0])
ans = []
for line in lines[1:]:
    a, x = map(int, line.split())
    ans.append(str(math.ceil((-1 + math.sqrt(4*(a**2) - 4*a + 8*x + 1))/2)) + "\n")
sys.stdout.write("".join(ans))

ZeroJudge 解題筆記：f884. 柏恩的奶茶

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


ZeroJudge 題目連結：f884. 柏恩的奶茶

解題想法

這題考數學，要先推導公式。依照題意，給定某個正整數 $n$，要找到另一個正整數 $x$，使 $x(x+1)(x+2)(x+3) + 1 = x$。先化簡算式 $$ x(x+1)(x+2)(x+3) + 1 = x^4 + 6x^3 + 11x^2 + 6x + 1 = (x^2 + 3x + 1)^2 $$ 因此題目可以改為求 $$ (x^2 + 3x + 1)^2 = n $$ 因為題目要求 $n, x \in N$，所以 $n$ 一定是平方數，假設 $x^2 + 3x + 1 \equiv k$，則 $k = \sqrt{n}$。在程式碼之中，可以先檢查

k = math.isqrt(n)  # Python 3.11 之後的寫法，舊版可用 k = int(math.sqrt(n))
if k*k != n:
    print(-1); return

將題目由解一元四次方程化簡為解一元二次方程式 $$ x^2 + 3x + 1 - k = 0 $$ 判別式 $$ D = 3^2 - 4\times(1-k) = 5 + 4k $$ 因為 $x$ 要有正整數解，$D = 5 + 4k$ 為平方數，$\sqrt{D} = \sqrt{5 + 4k}$ 為奇數且大於 3。由公式解可得 $$ x = \frac{-3 + \sqrt{5 + 4k}}{2} = \frac{-3 + \sqrt{5 + 4 \sqrt{n}}}{2} $$ 在程式碼之中，可以先檢查

d = math.isqrt(5+4k)  # Python 3.11 之後的寫法，舊版可用 d = int(math.sqrt(5+4k))
if d*d != k:
    print(-1); return
if (5+4*k)%2 == 0 or 5+4*k <= 3:
    print(-1); return

最後將題目給的 $n$ 值代入公式求解。題目看起來保證測資一定有解，以上三個檢查是否有解的部分可以跳過，直接代公式求解。

Python 程式碼

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

import sys, math

for line in sys.stdin:
    n = int(line)
    x = (-3+int(math.sqrt(5 + 4*int(math.sqrt(n)))))//2
    print(x, x+1, x+2, x+3)

ZeroJudge 解題筆記：f822. 紅林愛下棋

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


ZeroJudge 題目連結：f822. 紅林愛下棋

解題想法

這題分成兩個部分。首先依序掃過每一格，如果這格是 .，用 list 儲存待走訪佇列，假設目前區塊的顏色 color 為 X，用四方位檢查找周圍的格子 (nr, nc)，如果 (nr, nc) 是 B 或 W，設定 color 的值； 如果 color 已經是 B 或 W，但是 (nr, nc) 的顔色與 color 不同，錯誤，無法計算領地大小。找到連通區塊之後，將 que 裡的格子改成 color 的值。第二部分，再用二層 for 迴圈，計算黑、白棋數量。最後按照題目的要求輸出答案。

Python 程式碼

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

def solve():
    grid = [list(input()) + ["#"] for _ in range(9)]  # 地圖，在最右側、最下方加 # 作為哨兵
    grid.append(["#"]*10)
    for i in range(9):  # 依序掃過每一格
        for j in range(9):
            if grid[i][j] == ".":  # 如果此格是 .
                que = [(i, j)]  # 將 (i, j) 加到待走訪佇列 que
                head = 0  # 從 que 讀取資料的索引值
                color = "X"  # 目前區塊的顏色，預設為 X
                ### BFS ###
                while head < len(que):  # 如果 head 還沒有出界繼續執行
                    r, c = que[head]; head += 1  # 從 que 讀取待走訪位置，head 加 1
                    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
                        nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                        if grid[nr][nc] == "#": continue  # 如果此格是邊界，找下一格
                        if (color == "B" and grid[nr][nc] == "W") or \  # 區塊顏色 B、此格顏色 W
                           (color == "W" and grid[nr][nc] == "B"):      # 區塊顏色 W、此格顏色 B
                                print("Wrong"); return  # 錯誤，離開函式
                        elif (color == "B" or color == "W") and grid[nr][nc] == ".":  # 區塊為 B 或 W，此格為 .
                                grid[nr][nc] = "@"  # 暫時填入 @，避免重複走訪
                                que.append((nr, nc))  # (nr, nc) 加入 que
                        elif color == "X":  # 如果區塊還沒有決定顏色
                            if grid[nr][nc] == ".":  # 如果此格是 .
                                grid[nr][nc] = "@"  # 暫時填入 @，避免重複走訪
                                que.append((nr, nc))  # (nr, nc) 加入 que
                            elif grid[nr][nc] == "B" or grid[nr][nc] == "W":  # 如果此格是 B 或 W
                                color = grid[nr][nc]  # 更新區塊顏色
                ### End of BFS ###
                for r, c in que: grid[r][c] = color  # 將 que 之中的位置填入對應的顏色
    ### 已掃過所有格子，計算黑、白棋數量 ###
    B, W = 0, 0  # 黑、白棋數量
    for i in range(9):
        for j in range(9):
            if grid[i][j] == "B": B += 1
            elif grid[i][j] == "W": W += 1
    ### 印出題目要求的答案 ###
    print("Black wins!!" if B > W else "White wins!!")
    print(f"{B:d}:{W:d}")
    for row in grid[:9]: print("".join(row[:9]))
### 主程式 ###
if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：f821. nAnB ( 正常版 )

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


ZeroJudge 題目連結：f821. nAnB ( 正常版 )

解題想法

這題的數字不會重複，寫起來簡單很多。假設數字、位置皆相同的數量為 a，數字相同、位置不同的數量為 b，依序讀取猜測字串中的每個字元，先比較這個字元與答案中同樣位置的字元是否相同，如果相同則 a 加 1；如果前一個條件不成立，再檢查這個數字是否在答案當中，如果有則 b 加 1。

Python 程式碼

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

ans, m = input().split()  # 正確答案，詢問筆數
n = len(ans)  # 答案的字數
for _ in range(int(m)):  # 執行 m 次
    guess = input()  # 猜測的數字
    a, b = 0, 0  # 數字、位置皆正確的數量，數字正確、位置錯誤的數量
    for i, c in enumerate(guess):  # 依序取出 guess 的數字
        if ans[i] == c: a += 1  # 數字、位置皆正確
        elif c in ans: b += 1  # 數字正確、位置錯誤
    print(f"{a:d}A{b:d}B")

ZeroJudge 解題筆記：f803. 質數篩法練習

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


ZeroJudge 題目連結：f803. 質數篩法練習

解題想法

這題可以用埃拉托斯特尼篩法建質數表，再用二分搜尋找指定的質數在表中的索引值。

Python 程式碼

原來測試時，使用時間約為 2.5 s，記憶體約為 323.6 MB，通過測試。但是在2025年10月23日測試時，最後一筆測資超時，好像沒有為 Python 使用者放寬時間限制，仍然為 1 s。

from bisect import bisect_left

n, m = map(int, input().split())
states = [True]*n
states[0] = states[1] = False
for i in range(2, int(n**0.5) + 1):
    if states[i]:
        states[i+i::i] = [False]*len(states[i+i::i])
primes = [i for i, is_prime in enumerate(states) if is_prime]
for _ in range(m):
    print(bisect_left(primes, int(input())) + 1)

改用 sys 加速並修改內層 for 迴圈的寫法仍然超時。

import sys
from bisect import bisect_left

result = []
lines = sys.stdin.readlines()
n, m = map(int, lines[0].split())
sieve = [True]*n
sieve[0] = sieve[1] = False
for i in range(2, int(n**0.5) + 1):
    if sieve[i]:
        for j in range(i*i, n, i):
            sieve[j] = False
primes = [int(i) for i in range(n) if sieve[i]]
idx = 1
while idx < len(lines):
    x = int(lines[idx])
    idx += 1
    pos = bisect_left(primes, x) + 1
    result.append(f"{pos:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：f787. 宇辰的閃電

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


ZeroJudge 題目連結：f787. 宇辰的閃電

解題想法

這題想要考 C 及 C++ 的結構體 (struct)，自訂結構體 Player，用來儲存玩家的姓名、血量、被電時的傷害、下個目標玩家編號、道具清單。由於 Python 的 list 可以儲存不同格式的資料，而且 Python 沒有 struct，所以我直接用 list 儲存玩家資料。

Python 程式碼

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

n, s = map(int, input().split())  # n 位玩家，一開始的目標為 s
players = [[]]  # 玩家資料，開頭放一個空的，資料依序為
                # [名字, 血量, 被電時的傷害, [道具清單], 下個目標玩家編號]
for i in range(1, n+1): # 讀取 1 ~ n 號玩家資料
    line = input().split()
    players.append([line[0], int(line[1]), int(line[2]),
                   line[3:-1], int(line[-1])])
visited = [False]*(1+n)  # 1 ~ n 號玩家是否已被攻擊過
while not visited[s]:  # 如果 s 號玩家還沒有被攻擊過則繼續執行
    visited[s] = True  # s 號玩家已經被攻擊過
    if players[s][2] >= players[s][1]:  # 傷害大於等於血量
        print(f"{players[s][0]:s} dead.")  # 已陣亡
    else:  # 反之
        players[s][1] -= players[s][2]  # 扣血
        for _ in range(players[s][2]):  # 從最後面開始掉道具
            if players[s][3]: players[s][3].pop()
        print(f"{players[s][0]:s} {players[s][1]:d} ", end="")
        print(*players[s][3])
    s = players[s][4]  # 更新目標

因為玩家持有的道具數量等於血量，所以不需要考慮還沒有陣亡但是已經沒有道具的狀況，可以刪掉第15、16行，第18行改成以下這樣。使用時間約為 83 ms，記憶體約為 9.6 MB，通過測試。

print(*players[s][3][:-players[s][2]])

ZeroJudge 解題筆記：f731. 老鼠的直播間

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


ZeroJudge 題目連結：f731. 老鼠的直播間

解題想法

這題與 APCS實作題2016年3月第3題：線段覆蓋長度 解題觀念相同，將所有時段的開始時間 start 與 1 組合成數組，結束時間 end 與 -1 組合成數組，將數組加到串列之中，再依照時間排序。接下來依序讀取時間，更新目前線上的人數及最大值。

Python 程式碼

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

n = int(input())  # n 個時段
segs = []  # 時刻與人數變化，(start, 1) 或 (end, -1)
for _ in range(n):  # 讀取 n 行資料
    start, end = map(int, input().split())
    segs += [(start, 1), (end, -1)]
segs.sort()  # 依照時刻排序
cnt, imax = 0, 0  # 目前的人數，最多人數
for t, c in segs:  # 依序讀取時刻與人數變化
    cnt += c  # 更新人數
    imax = max(imax, cnt)  # 更新 imax
print(imax) 

ZeroJudge 解題筆記：f716. 計算學期成績

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


ZeroJudge 題目連結：f716. 計算學期成績

解題想法

換算的公式為 $$ y = 45 \times \frac{x-a}{b} + 55 $$ 假設原始成績最高分為 $imax$、最低分為 $imin$，換算後成績最高分為 $100$、最低分為 $55$，代入上式可得 $$ 100 = 45 \times \frac{imax-a}{b} + 55 ~~~~~ 55 = 45 \times \frac{imin-a}{b} + 55 $$ 由以上2式可得 $$ b = imax - a ~~~~~ a = imin $$

Python 程式碼

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

scores = tuple(map(int, input().split()))
a = min(scores)
b = max(scores) - a
print(a, b)

C++ 程式碼

使用時間約為 2 ms，記憶體約為 92 kB，通過測試。2025年10月15日重測，使用時間約為 0 ms，記憶體約為 48 kB，通過測試。

#include <cstdio>

int main() {
    int imin = 1E9, imax = 0, score;
    while(scanf("%d", &score) != EOF) {
        if (score < imin) imin = score;
        if (score > imax) imax = score;
    }
    printf("%d %d\n", imin, imax - imin);
    return 0;
}

ZeroJudge 解題筆記：f701. 連接字詞

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


ZeroJudge 題目連結：f701. 連接字詞

解題想法

這題沒有說明要讀取的單字數量，用 C++ 寫起來會比較麻煩，用 getline 搭配 stringstream 及 vector 會比較方便。

Python 程式碼

以前測試時使用時間約為 19 ms，記憶體約為 3.3 MB。ZeroJudge 網站好像在 2025年10月更新過，同樣的程式碼使用時間約為 6 ms，記憶體約為 3 MB。

words = list(input().split())
conjuction = input()
n = len(words)
for i in range(n-1):
    print(f"{words[i]:s} {conjuction:s} ", end="")
print(words[-1])

可以用 join 將 " 連接詞 " 與串列 words 的內容接成一個字串再輸出，使用時間約為 7 ms，記憶體約為 3 MB，通過測試。

words = list(input().split())
conjuction = input()
print(f" {conjuction} ".join(words))

ZeroJudge 解題筆記：f699. 品嘉的茶葉蛋

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


ZeroJudge 題目連結：f699. 品嘉的茶葉蛋

解題想法

標準的 BFS 題目。因為不想檢查是否出界，我在地圖周圍加上 2 作為哨兵。另外開一個陣列儲存步數。

Python 程式碼

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

from collections import deque

n, m = map(int, input().split())  # 地圖 n*m，最右側、最下方加上 2 作為哨兵
grid = [list(map(int, input().split())) + [2] for _ in range(n)]
grid.append([2]*(m+1))  # 最下方加 m+1 個 2
steps = [[0]*m for _ in range(n)]  # 記錄步數用的二維串列
ans = []  # 答案
que = deque([(0, 0)])  # 待走訪佇列
grid[0][0] = 2  # (0, 0) 設定為 2
while que:  # 如果 que 還有資料繼續執行
    r, c = que.popleft()  # 從 que 開頭讀取並移除資料
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
        nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
        if grid[nr][nc] == 2: continue  # 如果此格是 2 找下一格
        steps[nr][nc] = steps[r][c] + 1  # (nr, nc) 的步數為 (r, c) 的步數加 1
        if grid[nr][nc] == 1: ans.append(steps[nr][nc])  # 如果此格是 1，將 (nr, nc) 的步數加入 ans
        grid[nr][nc] = 2  # 此格設定為 2
        que.append((nr, nc))  # (nr, nc) 加入 que
if not ans: print("嘉油！")  # 沒有找到茶葉蛋
else:  # 有找到茶葉蛋，印出 ans 的內容
    for a in ans: print(a)

ZeroJudge 解題筆記：f680. 色塊數量

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


ZeroJudge 題目連結：f680. 色塊數量

解題想法

標準的 BFS 題目。

Python 程式碼

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

from collections import deque

n = int(input())  # 地圖 n*n，最右側、最下方加上 0 作為哨兵
grid = [list(map(int, input().split())) + [0] for _ in range(n)]
grid.append([0]*(n+1))
### BFS ###
cnt = 0  # 色塊數量
for i in range(n):  # 依序掃過每一格
    for j in range(n):
        if grid[i][j] == 0: continue  # 如果此格是 0 找下一格
        color = grid[i][j]  # 此格的顏色
        grid[i][j] = 0  # 此格設定為 0
        que = deque([(i, j)])  # (i, j) 加入待走訪佇列
        cnt += 1  # 色塊數量加 1
        while que:  # 如果 que 還有資料繼續執行
            r, c = que.popleft()  # 從 que 開頭讀取並移除資料
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
                nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                if grid[nr][nc] != color: continue  # 如果此格顏色不一樣，找下一格
                grid[nr][nc] = 0  # 此格設定為 0
                que.append((nr, nc))  # (nr, nr) 加入待走訪佇列
### End of BFS ###
print(cnt)  # 印出答案

ZeroJudge 解題筆記：f647. 撲克牌

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


ZeroJudge 題目連結：f647. 撲克牌

解題想法

我用串列儲存牌組，先用 for 迴圈産生按照花色、數字排列好的 52 張牌，接下來依照指令用串列切片修改內容。

Python 程式碼

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

deck = [""]*52
suits = ('S', 'H', 'D', 'F')
akqj = {1: 'A', 13: 'K', 12: 'Q', 11: 'J'}
for i in range(4):
    for j in range(1, 14):
        if 2 <= j <= 10: deck[i*13 +j-1] = suits[i] + str(j)
        else: deck[i*13 + j-1] = suits[i] + akqj[j]
n = int(input())
for _ in range(n):
    line = input().split()
    if line[0] == '1':
        a, b = int(line[1])-1, int(line[2])-1
        deck = deck[a:b+1] + deck[:a] + deck[b+1:]
    elif line[0] == '2':
        a, b = int(line[1])-1, int(line[2])-1
        deck = deck[:a] + deck[b+1:] + deck[a:b+1]
    elif line[0] == '3':
        k = int(line[1])
        deck = deck[52-k:] + deck[:52-k]
    else:
        k = int(line[1])
        deck = deck[k:] + deck[:k]
print(*deck[:5])

ZeroJudge 解題筆記：f634. 士兵歸來

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


ZeroJudge 題目連結：f634. 士兵歸來

解題想法

我用集合 uni 儲存存活者的姓名、軍種、階級，再用另外兩個陣列 services、ranks 儲存各軍種、階級存活者的數量，用 cnt 儲存存活者總數。讀取 m 行資料之後，再依照題目要求的格式輸出答案。

Python 程式碼

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

n, m = map(int, input().split())  # 共派出 n 人，有 m 行資料
uni = set()  # (姓名 name, 軍種 service, 階級 rank)
services = [0]*4  # 海、陸、空軍存活人數，開頭有用不到的 0
ranks = [0]*4  # 軍官、士官、士兵存活人數，開頭有用不到的 0
cnt = 0  # 存活人數
for _ in range(m):  # 執行 m 次
    data = tuple(input().split())
    if data not in uni:  # 這筆資料組合不在 uni 之中，新的存活者
        uni.add(data)  # data 加入 uni
        cnt += 1  # 存活人數加 1
        services[int(data[1])] += 1  # 對應的軍種人數加 1
        ranks[int(data[2])] += 1  # 對應的階級人數加 1
print(f"navy:{services[1]:d} army:{services[2]:d} air:{services[3]:d}")
print(f"officer:{ranks[1]:d} sergeant:{ranks[2]:d} soldier:{ranks[3]:d}")
print(f"survival rate: {100.0*cnt/n:.1f}%")

ZeroJudge 解題筆記：f632. 渡船頭

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


ZeroJudge 題目連結：f632. 渡船頭

解題想法

先讀取所有的乘客資料，在結束營業之前到的人才加入串列 passenger 之中，接下來依照時間由小到大排序。另外開一個最大優先佇列，儲存目前乘客會給的小費。再用一個 for 迴圈依序産生出發時刻，讀取當時已到站的乘客資料，將乘客會給的小費存入 pq 之中；再從 pq 取出資料加到利潤 profit 之中，直到 pq 沒有資料或是這趟人數到達上限為止。

Python 程式碼

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

import sys, heapq

t1, t2, k, p = map(int, sys.stdin.readline().split())  # 營業時間，間距，每趟人數
passenger = []  # 乘客到站時間、小費
for line in sys.stdin:  # 讀取資料直到 EOF 為止
    if line.strip() == "": continue  # 如果讀到空行，找下一行
    t, m = map(int, line.split())  # 這個乘客的到站時間、小費
    if t <= t2: passenger.append((t, m))  # 在結束營業之前到的人才加入
passenger.sort()  # 依照時間排序
tot, profit, idx, n = 0, 0, 0, len(passenger)  # 總載客人數，總收入，從 passenger 讀資料的索引值，人數
pq = []  # 存入目前乘客小費的優先佇列
for dep in range(t1, t2+1, k):  # 依序産生出發時刻
    while idx < n:  # 如果 idx 還沒有出界繼續執行
        t, m = passenger[idx]  # 到站時間、小費
        if t <= dep: heapq.heappush(pq, -m)  # 如果 t 小於等於發車時刻，m 加負號再加入 pq
        else: break  # 否則中止迴圈
        idx += 1  # idx 加 1
    cnt = 0  # 這趟已載人數
    while pq and cnt < p:  # 如果 pq 還有資料而且還沒有載滿
        profit += -heapq.heappop(pq)  # 從 pq 讀取並移除首項，轉為正值加到 profit
        cnt += 1; tot += 1  # 更新人數
print(tot, profit)  # 印出答案

ZeroJudge 解題筆記：f631. 同學會

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


ZeroJudge 題目連結：f631. 同學會

解題想法

這題要用最大優先佇列儲存每個人目前有的錢，由於 Python 的 heapq 是最小優先佇列，要將每一筆資料都加上負號。

Python 程式碼

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

import sys, heapq

for line in sys.stdin:  # 繼續執行直到 EOF 為止
    if line.strip() == "": continue  # 遇到空行，找下一行
    n, m = map(int, line.split())  # n 個人，m 道菜
    money = list(map(int, sys.stdin.readline().split()))  # 每個人原來的錢
    dishes = list(map(int, sys.stdin.readline().split()))  # 每道菜的價格
    if sum(money) < sum(dishes):  # 所有人帶的錢小於所有菜的總價
        print("Oh My God")  # 印出 Oh My God
        continue  # 讀下一筆資料
    pq = [-m for m in money]  # 將 money 每一筆資料加負號存入 pq
    heapq.heapify(pq)  # pq 轉成最小優先佇列
    imax = -pq[0]  # 初始金額最大值
    for dish in dishes:  # 依序讀取每道菜的價格
        while pq and dish > 0:  # 當 pq 還有資料而且 dish 大於 0 時繼續執行
            m = -heapq.heappop(pq)  # 取出 pq 第一項加負號，變回正值
            if m > dish:  # 如果付完這道菜還有錢
                heapq.heappush(pq, -(m-dish))  # 剩下的錢加負號，存入 pq
                dish = 0  # 待付金額為 0
            elif m == dish: dish = 0  # 如果這個人的錢剛好夠用，待付金額為 0
            else: dish -= m  # 如果這個人的錢不夠，更新待付金額
    print(imax, -pq[0] if pq else 0)  # 印出 imax，如果 pq 有資料印出 -pq[0]，反之印出 0

ZeroJudge 解題筆記：f493. 水窪問題

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


ZeroJudge 題目連結：f493. 水窪問題

解題想法

這類型的題目我習慣用 BFS 解題，已走訪的位置改成題目給的陸地符號 #，不需要另外開一個陣列儲存已走訪的位置，可以節省一些記憶體。

Python 程式碼

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

from collections import deque

n, m = map(int, input().split())  # 地圖 n*m
grid = [list(input() + "#") for _ in range(n)]  # 讀取地圖資料，右側加上 #
grid.append(["#"]*(n+1))  # 最下方加上 n+1 個 #
cnt, imin, imax = 0, float('inf'), 0  # 數量，最小面積、最大面積
### BFS ###
for i in range(n):  # 依序掃過每一格
    for j in range(m):
        if grid[i][j] == "#": continue  # 如果是 #，找下一格
        grid[i][j] = "#"  # 此格改成 #
        cnt += 1  # 數量加 1
        area = 0  # 這個水漥的面積
        que = deque([(i, j)])  # (i, j) 加入待走訪佇列 que
        while que:  # 如果 que 還有資料繼續執行
            r, c = que.popleft()  # 從 que 開頭取出座標 (r, c)
            area += 1  # 面積加 1
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
                nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                if grid[nr][nc] == "#": continue  # 如果是 #，找下一格
                grid[nr][nc] = "#"  # 此格改成 #
                que.append((nr, nc))  # (nr, nc) 加入 que
        imin = min(imin, area)  # 更新 imin
        imax = max(imax, area)  # 更新 imax
### 結束 BFS ###
if cnt == 0:  # 如果 cnt 等於 0，印出 0 0 0
    print("0 0 0")
else:  # 反之印出 imax, imin, cnt
    print(imax, imin, cnt)

ZeroJudge 解題筆記：f455. 詠竣的哀鳳12

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


ZeroJudge 題目連結：f455. 詠竣的哀鳳12

解題想法

這題是背包問題，用動態規畫處理，但是用 Python 好像沒辦法通過。

Python 程式碼

只能通過 60% 的測資。

t, n = map(int, input().split())  # 總時數 t，工作數量 n
dp = [0]*(t+1)  # 總時數 0 ~ t 對應的最大收入
work = ""  # 最高時薪的工作名稱
imax = 0.0  # 最高時薪
for _ in range(n):  # 執行 n 次
    s, m, h = input().split()  # 工作名稱，收入，需要的時間
    m = int(m); h = int(h)  # m, h 轉為 int
    mph = 1.0*m/h  # 時薪
    if mph > imax:  # 如果時薪較高，更新 imax, work
        imax = mph; work = s
    if h > t: continue  # 如時需要的時間大於 t，不能接工作，找下一筆
    for i in range(t, h-1, -1):  # 倒著更新 dp[t] ~ dp[h]
        dp[i] = max(dp[i], dp[i-h] + m)  # 如果接這個工作總收入變高則更新 dp[i]
print(dp[-1])  # 最高總收入在 dp[t-1], dp[-1]
print(work)  # 印出最高時薪的工作名稱

ZeroJudge 解題筆記：f418. Word Search Puzzle

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


ZeroJudge 題目連結：f418. Word Search Puzzle

解題想法

這題我用二維陣列儲存英文字謎資料，再依照測資給的 r1, c1 及 r2, c2 判斷要向右、向下或是向右下方找答案。

Python 程式碼

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

h, w, r1, c1, r2, c2 = map(int, input().split())
r1 -= 1; c1 -= 1; r2 -=1; c2 -= 1  # 題目的座標從 1 開始
grid = [list(input()) for _ in range(h)]
if r1 == r2:  # 同一列，向右找
    print("".join(grid[r1][c1:c2+1]))
elif c1 == c2:  # 同一欄，向下找
    print("".join([grid[i][c1] for i in range(r1, r2+1)]))
else:  # 向右下方找
    print("".join([grid[r1+i][c1+i] for i in range(r2-r1+1)]))

ZeroJudge 解題筆記：f410. 芝麻街的郵件投遞

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


ZeroJudge 題目連結：f410. 芝麻街的郵件投遞

解題想法

這題考排序，自訂比較式，先排單、雙號，雙號放前面、單號放後面，雙號門牌再由小到大排序，單號門牌再由大到小排序。

Python 程式碼

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

from functools import cmp_to_key

def mycmp(a, b):
    if a%2 == 0 and b%2 == 0:
        if a < b: return -1
        elif a > b: return 1
        else: return 0
    elif a%2 == 1 and b%2 == 1:
        if a > b: return -1
        elif a < b: return 1
        else: return 0
    elif a%2 == 0 and b%2 == 1: return -1
    elif a%2 == 1 and b%2 == 0: return 1
    else: return 0

n = int(input())
arr = list(map(int, input().split()))
arr.sort(key = cmp_to_key(mycmp))
print(*arr)

ZeroJudge 解題筆記：f408. 迷你蘋菓鎮

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


ZeroJudge 題目連結：f408. 迷你蘋菓鎮

解題想法

將所有的門牌依照絕對值排序，再依序掃過每一個門牌，如果跟相鄰的門牌相乘小於 0 則答案加 1。

Python 程式碼

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

n = int(input())
arr = list(map(int, input().split()))
arr.sort(key = lambda x : abs(x))
cnt = 0
for i in range(1, n):
    if arr[i-1] * arr[i] < 0:
        cnt += 1
print(cnt)

ZeroJudge 解題筆記：f376. 芝麻街的團購

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


ZeroJudge 題目連結：f376. 芝麻街的團購

解題想法

這題的測資不大，可以真的計算以每個點為中心的總距離，再找其中的最小值。實際上答案就是取中位數。

Python 程式碼

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

n = int(input())
psum = [0] + list(map(int, input().split()))
psum.sort()
for i in range(1, n+1): psum[i] += psum[i-1]
imin = float('inf')
ans = 0
for i in range(1, n+1):
    dis = (2*i-n-1)*(psum[i] - psum[i-1]) - psum[i-1] + psum[n] - psum[i]
    if dis < imin:
        imin = dis
        ans = psum[i] - psum[i-1]
print(ans)

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

n = int(input())
arr = sorted(list(map(int, input().split())))
print(arr[n//2] if n%2 else arr[n//2 - 1])

ZeroJudge 解題筆記：f348. 完全偶數

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


ZeroJudge 題目連結：f348. 完全偶數

解題想法

我先寫一個函式 check 判斷輸入的整數 n 是否每一位都是偶數；再寫另一個函式 solve，找最接近 n 的完全偶數距離。

Python 程式碼

簡單但較慢的寫法，循序搜尋，使用時間約為 30 ms，記憶體約為 3 MB，通過測試。

def check(n):  # 檢查輸入的整數是否每一位都是偶數
    while n:
        if n%10%2 == 1:
            return False
        n //= 10
    return True

def solve(n):  # 輸入整數，找最接近的完全偶數距離
    if check(n): return 0  # 特例，n 是完全偶數，回傳 0
    lower, upper, cnt = n-1, n+1, 0  # 往下找、往上找、次數
    while True:  # 找到答案為止
        cnt += 1  # 次數加 1
        if check(lower): return cnt  # 如果 lower 是完全偶數，回傳 cnt
        if check(upper): return cnt  # 如果 uper 是完全偶數，回傳 cnt
        lower -= 1; upper += 1  # lower 減 1，upper 加 1
    return -1  # 預設的回傳值，用不到

print(solve(int(input())))

ZeroJudge 解題筆記：f332. 貝瑞的鐵線體積

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


ZeroJudge 題目連結：f332. 貝瑞的鐵線體積

解題想法

如果函數為 $y = f(x)$，將此函數曲線以 $x$ 軸為轉軸旋轉，旋轉體體積為 $$ V = \pi \int_a^b y^2 dx $$

Python 程式碼

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

import math

t = int(input())  # 共 t 筆測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # 多項式最高次方
    poly = list(map(int, input().split()))  # 多項式由高到低次方各項係數
    square = [0]*(2*n + 1)  # 多項式平方各項係數
    for i in range(n+1):
        for j in range(n+1):
            square[i+j] += poly[i]*poly[j]
    integral = [0]*(2*n + 1)  # 平方後積分結果，忽略常數項
    for i in range(2*n + 1):  # 計算積分式
        integral[i] = 1.0 * square[i] / (2*n + 1 - i)
    ans = 0.0  # 積分結果
    a, b = map(int, input().split())  # 積分下限、上限
    for i, c in enumerate(integral):  # 代入積分下限、上限
        ans += c * (b**(2*n + 1 - i) - a**(2*n + 1 - i))
    print(f"{math.pi*ans:.2f}")  # 印出答案時再乘以 pi

ZeroJudge 解題筆記：f291. 試算表大小

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


ZeroJudge 題目連結：f291. 試算表大小

解題想法

先將讀到的字串拆成左側字母、右側數字兩個部分，再從字母最後面往回讀取，計算是第幾欄，再將欄數乘以列數就是答案。

Python 程式碼

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

s = input()  # 輸入的儲存格編號
left = ""  # 左半邊的欄位
row = 0  # 列數
for i, c in enumerate(s):  # 依序讀取 s 的字元
    if c.isdigit():  # 如果 c 是數字，取出左半邊，中止迴圈
        left = s[:i]
        row = int(s[i:])
        break
b = 1  # 計算欄位的基底
col = 0  # 欄位編號
for c in left[::-1]:  # 從 left 最後面讀取字元
    col += b*(ord(c) - ord('A') + 1)  # 計算欄位
    b *= 26  # 基底乘以 26
print(row*col)  # 答案是列、欄相乘

ZeroJudge 解題筆記：f260. 愛八卦的同學

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


ZeroJudge 題目連結：f260. 愛八卦的同學

解題想法

我用 BFS 找連通區塊數量，不過用 Python 的速度太慢，用 C++ 解題也要 0.3 s。

Python 程式碼

速度太慢，只能通過一筆測資。

import sys
from collections import deque

for line in sys.stdin:
    n, k = map(int, line.split())  # n 個人，k 組關係
    adj = [[] for _ in range(n)]  # 每個人與其它人的關係
    for _ in range(k):  # 讀取 k 行資料
        u, v = map(int, sys.stdin.readline().split())  # u, v 是朋友
        adj[u].append(v)
        adj[v].append(u)
    cnt = 0  # 小團體數量
    visited = [False]*n  # 是否已經檢查過
    for i in range(n):  # 依序讀取每一個人
        if visited[i]: continue  # 如果 i 已經檢查過，找下一個人
        visited[i] = True  # 設定為 True
        cnt += 1
        que = deque([i])
        while que:
            v = que.popleft()
            for u in adj[v]:
                if visited[u]: continue
                que.append(u)
                visited[u] = True
    print(cnt)

ZeroJudge 解題筆記：f257. 君王的處刑遊戲

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


ZeroJudge 題目連結：f257. 君王的處刑遊戲

解題想法

我是用二維陣列儲存每一個人的驚恐值，預設值為 0，-1 代表已淘汰，Python 的最右側、最下方加上 -1 當作哨兵，C++ 周圍加上 -1 當作哨兵。每次檢查位置 (x, y) 的人，如果還沒有淘汰就設定成 -1，再檢查周圍 8 格，遇到還沒有被淘汰的人就將驚恐值加 1。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 二維陣列 n*n
    grid = [[0]*n + [-1] for _ in range(n)]  # 最右側、最下方加 -1 當作哨兵
    grid.append([-1]*(n+1))
    k = int(sys.stdin.readline())  # 要淘汰的人數
    for _ in range(k):  # 執行 k 次
        x, y = map(int, sys.stdin.readline().split())  # 要淘汰的人位置 (y, x)
        if grid[y][x] == -1: continue  # 已淘汰，找下一個
        grid[y][x] = -1  # 已淘汰，設定成 -1
        # 搜尋四周的 8 格
        for dy, dx in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
            ny, nx = y+dy, x+dx  # 檢查 grid[ny][nx]
            if grid[ny][nx] == -1: continue  # 已淘汰，找下一個
            grid[ny][nx] += 1  # 周圍的人驚恐值加 1
    # 執行完畢，要印出答案，不能印出最右側、最下方的哨兵，-1 要換成 x
    for row in grid[:n]:
        print("".join([str(i) if i != -1 else "x" for i in row[:n]]))

ZeroJudge 解題筆記：f164. 萬球同心移位之章

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


ZeroJudge 題目連結：f164. 萬球同心移位之章

解題想法

這題絕對不要真的用鏈結串列解題，因為要找到鏈結串列中指定的值只能從頭開始依序往下找，一定會超時。用兩個陣列儲存每一個節點的左、右節點編號，移動節點時只要修改對應的節點編號即可。

Python 程式碼

最後一筆測資記憶體爆掉。

n, m, q = map(int, input().split())  # n 顆球，m 次操作，q 次查詢
pre = [(i-1+n)%n for i in range(n)]  # 每顆球的前一顆球
nxt = [(i+1)%n for i in range(n)]  # 每顆球的後一顆球
for _ in range(m):  # 執行 m 次
    d, a, b = input().split()  # 方向 d，a 球移到 b 球旁邊
    if a == b: continue  # 如果 a 等於 b，不移動
    a = int(a); b = int(b)  # 轉成整數
    nxt[pre[a]] = nxt[a]  # a 原來左側的球接到 a 原來右側的球
    pre[nxt[a]] = pre[a]  # a 原來右側的球接到 a 原來左側的球
    if d == 'R':  # 逆向
        le = pre[b]  # 暫存 b 原來左側的球
        nxt[le] = a  # b 原來左側的球接到 a
        pre[b] = a  # b 的左側接到 a
        pre[a] = le  # a 左側接到 le
        nxt[a] = b  # a 右側接到 b
    else:  # 順向
        ri = nxt[b]  # 暫存 b 原來右側的球
        pre[ri] = a  # b 原來右側的球接到 a
        nxt[b] = a  # b 的右側接到 a
        pre[a] = b  # a 的左側接到 b
        nxt[a] = ri  # a 的右側接到 ri
arr = tuple(map(int, input().split()))
for a in arr[:-1]: print(pre[a], nxt[a], end=" ")
print(pre[arr[-1]], nxt[arr[-1]])

ZeroJudge 解題筆記：e984. 連假時在做什麼？有沒有空？可以來打code嗎？

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


ZeroJudge 題目連結：e984. 連假時在做什麼？有沒有空？可以來打code嗎？

解題想法

用一個自訂函式 find_lln 找第 k 項的 LunlunNumber。在函式中用一個 deque 儲存待處理的數字，先放入 1 ~ 9，再用一個 while 迴圈，當 que 還有資料繼續執行；在迴圈中每次取出 que 開頭的數字存入 num，計數器 cnt 數量加 1，如果 cnt 等於 k，已經找到答案，回傳 num；如果 cnt 小於 k，取出 num 的個位數 last_digit，計算 last_digit 加減 1、不變、加 1 的數值 next_digit，如果 next_digit 在 1 到 9 之中，將新的數值加入 que 之中。

Python 程式碼

單筆測資，使用時間約為 2 s，記憶體約為 93.2 MB，通過測試。

from collections import deque

def find_lln(k):  # 找第 k 位的 Lunlun Number
    que = deque([i for i in range(1, 10)])  # 待處理的數字，先放入 1 ~ 9
    cnt = 0  # 計數器
    while que:  # 當 que 還有資料繼續執行
        num = que.popleft()  # 取出 que 開頭的數字
        cnt += 1  # 計數器加 1
        if cnt == k:  # 如果是第 k 位
            return num  # 回傳 num 並離開函式
        last_digit = num%10  # 取出個位數
        for delta in (-1, 0, 1):  # 個位數的差值 -1, 0, 1
            next_digit = last_digit + delta  # 下一個個位數值
            if 0 <= next_digit <= 9:  # 如果在 0 ~ 9 之間
                que.append(num*10 + next_digit)  # 新的數值加入 que
    return 0  # 預設的回傳值，理論上不會用到

print(find_lln(int(input())))

ZeroJudge 解題筆記：e698. OREOREO!

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


ZeroJudge 題目連結：e698. OREOREO!

解題想法

我先計算 O 的部分較寬及 RE 的部分較寬兩種狀況下，分別要印出的 O 及 RE 的字串。接下來讀取 n 塊餅乾的組成方式，依序輸出每一塊餅乾對應的形狀。

Python 程式碼

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

import sys

for line in sys.stdin:
    w1, h1 = map(int, line.split())
    w2, h2 = map(int, sys.stdin.readline().split())
    c1, c2 = sys.stdin.readline().split()
    if w1 > w2:  # O 的部分較寬
        O = c1*w1
        RE = " "*((w1-w2)//2) + c2*w2
    else:  # RE 的部分較寬
        O = " "*((w2-w1)//2) + c1*w1
        RE = c2*w2
    n = int(sys.stdin.readline())  # 接下來有 n 塊餅乾
    for _ in range(n):  # 執行 n 次
        cookie = sys.stdin.readline().strip()  # 餅乾的組成
        i = 0  # 從 cookie 讀取資料用的索引值
        while i < len(cookie):  # 如果 i 還沒有出界時繼續執行
            if cookie[i] == "O":  # 如果是 O
                for _ in range(h1): print(O)  # 印出 h1 行的 O
                i += 1  # i 加 1
            elif cookie[i] == "R":  # 如果是 RE
                for _ in range(h2): print(RE)  # 印出 h2 行的 RE
                i += 2  # i 加 2
        print()  # 跑完一塊餅乾要換行

ZeroJudge 解題筆記：e623. 2. PPAP

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


ZeroJudge 題目連結：e623. 2. PPAP

解題想法

先用一個 while 迴圈，計算序號 n 是第 m 輪領到東西，計算時每一輪會將 n 減去這一輪的數量。跑完 while 迴圈之後，如果 n 等於 0，代表是第 m 輪的最後一個人，印出 Pineapple pen； 反之進到下一輪，先將 m 加 1，計算 n 對 m 取整數除法的結果，輸出對應的物品名稱。

Python 程式碼

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

n = int(input())  # 編號
m = 0  # 第 m 輪
s = 0  # 第 m 輪的數量，每次加 4
while n >= s+4:  # 如果 n 的數量大於等於 s+4，還有下一輸，繼續執行
    m += 1; s += 4  # m 加 1；s 加 4
    n -= s  # n 減去 s

if n == 0:  # 剛好是第 m 輪的最後一個人
    print("Pineapple pen")  # 印出 Pineapple pen
else:  # 要再到下一輪
    m += 1  # m 加 1
    if n%m == 0: n -= 1
    item = n // m
    if item == 0: print("Pen")
    elif item == 1: print("Pineapple")
    elif item == 2: print("Apple")
    else: print("Pineapple pen")

ZeroJudge 解題筆記：e622. 3. 虛擬寵物大師 (Master)

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


ZeroJudge 題目連結：e622. 3. 虛擬寵物大師 (Master)

解題想法

我另外寫兩個函式，函式 ivcp 輸入 iv 值，回傳升級時增加的 cp 值；函式 upgrade 輸入原有的星塵沙子數量 star，iv 值、原來的 cp 值，計算升級後的 cp 值。

Python 程式碼

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

# 輸入 iv 值，回傳升級時增加的 cp 值
def ivcp(iv):
    if 0 <= iv <= 29: return 10
    elif 30 <= iv <=39: return 50
    elif 40 <= iv <= 45: return 100

# 輸入原有的星塵沙子數量 star，iv 值、原來的 cp 值，計算升級後的 cp 值
def upgrade(star, iv, cp):
    while star >= 1000:
        star -= 1000
        cp += ivcp(iv)
    return cp

# 解題過程
n, s = map(int, input().split())  # 寵物數量 n，原有的星塵沙子數量 s
imax, idx = 0, 0  # 升級後最高的 cp 值及寵物編號
for i in range(1, n+1):  # 讀取 n 行資料
    c, v = map(int, input().split())  # 讀取原來的 cp 值、iv 值
    re = upgrade(s, v, c)  # 呼叫 upgrade，代入 s, v, c，計算升級後的 cp 值
    if re > imax:  # 如果 re 大於 imax
        imax = re  # 更新 imax
        idx = i  # 更新 idx
print(f"{idx:d} {imax:d}")  # 印出答案

ZeroJudge 解題筆記：e621. 1. 免費停車 (Free Parking)

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


ZeroJudge 題目連結：e621. 1. 免費停車 (Free Parking)

解題想法

這題應該是多行測資，但是題目沒有說清楚。讀取測資中的 A、B、C 三個數字之後，用 for 迴圈跑 i = A-1 到 i = B-1，當 i 不能被 C 整除就加入答案之中。

Python 程式碼

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

import sys

for line in sys.stdin:
    N = int(line)
    for _ in range(N):
        A, B, C = map(int, input().split())
        ans = []
        for i in range(A+1, B):
            if i%C != 0: ans.append(i)
        if ans: print(*ans)
        else: print("No free parking spaces.")

ZeroJudge 解題筆記：e494. 無窮級數之和(二)

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


ZeroJudge 題目連結：e494. 無窮級數之和(二)

解題想法

這題考數學及大數運算，所以我只有寫 Python 版本。公式解 $$ \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots + \frac{1}{p} = \ln(\ln p) + M = \ln(\ln p) + 0.2614972128476427837554268386 $$ 由於輸出的小數位數很多，甚至要用到 decimal 函式庫的浮點數物件 Decimal 才行。

Python 程式碼

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

import sys, decimal

def solve(n):
    decimal.getcontext().prec = 1000  # 設定小數位數
    p = decimal.Decimal(n)  # 用 Decimal 格式的浮點數
    if p == decimal.Decimal(2):  # 特例，n 等於 2，回傳 0.5
        return decimal.Decimal('0.5')
    # 公式解，ln(ln(n)) + M
    ln_ln_p = p.ln().ln()
    M = decimal.Decimal('0.2614972128476427837554268386')
    return round(ln_ln_p + M, 3)

for line in sys.stdin:
    print(f"{solve(decimal.Decimal(line)):.3f}")

ZeroJudge 解題筆記：e484. 我是優質學生

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


ZeroJudge 題目連結：e484. 我是優質學生

解題想法

這題要判斷輸入的數字是否為 2 到 10000 之間的質數，由於輸入只有一行，不要建質數表，直接判斷這個數是否為質數就好。

Python 程式碼

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

def is_prime(n):  # 判斷是否為質數
    if n <= 1: return False  # 特例，小於等於1，回傳 False
    if n == 2 or n == 3: return True  # 特例，等於 2 或 3，回傳 True
    if n%2 == 0 or n%3 == 0: return False  # 特例，可以被 2 或 3 整除，回傳 False
    for i in range(5, int(n**0.5)+1, 6):  # 依序檢查 5 ~ sqrt(n)，每次加 6
        if n%i == 0 or n%(i+2) == 0:  # 如果可以被 i 或 i+2 整除，回傳 Fasle
            return False
    return True  # 最後回傳 True

print("yes" if is_prime(int(input())) else "no")

ZeroJudge 解題筆記：e470. 無窮級數之和(一)

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


ZeroJudge 題目連結：e470. 無窮級數之和(一)

解題想法

這題考數學，當 $n$ 很大時，有近似公式 $$ \sum_{i=1}^{n} \frac{1}{i} = \ln n + \gamma + \frac{1}{2n} $$ 其中 $\gamma = 5772156649$。

Python 程式碼

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

import sys, math

def harmonic_number(n):
    if n <= 20:  # 如果 n 小於等於 20，直接用迴圈計算
        isum = 0
        for i in range(1, n+1): isum += 1/i
        return isum
    gamma = 0.5772156649  # 反之，代近似公式
    return math.log(n) + gamma + 1.0 / (2 * n)

for line in sys.stdin:
    print(f"{harmonic_number(int(line)):.3f}")

ZeroJudge 解題筆記：e447. queue 練習

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


ZeroJudge 題目連結：e447. queue 練習

解題想法

這題就是考 queue 的操作，在 Python 要引入 collections 函式庫的 deque，在 C++ 要引入 queue 或是 deque 都可以。

Python 程式碼

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

from collections import deque

n = int(input())
arr = deque()
for _ in range(n):
    line = list(map(int, input().split()))
    if len(line) == 1:
        if line[0] == 2:
            if arr: print(arr[0])
            else: print(-1)
        elif line[0] == 3 and arr: arr.popleft()
    else:
        arr.append(line[1])

ZeroJudge 解題筆記：e446. 排列生成

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


ZeroJudge 題目連結：e446. 排列生成

解題想法

這題不論用 Python 還是 C++ 都可以用遞迴窮舉所有的排列方式。在 Python 也可以用 itertools.permutaions，在 C++ 也可以用 next_permutation。但主要的困難之處是輸出速度，要加速才能過關。

Python 程式碼

窮舉，用 print 輸出，超時。

def solve(arr, n, used):
    if len(arr) == n:
        print(*arr)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(input()), set())

窮舉，用 sys.stdout.write 輸出，超時。

import sys

def solve(arr, n, used):
    if len(arr) == n:
        s = " ".join(map(str, arr)) + "\n"
        sys.stdout.write(s)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(sys.stdin.readline()), set())

用 itertools.permutations，用 sys.stdout.write 最後再一次輸出所有結果，最後一筆測資超出記憶體上限。

import sys, itertools

result = []
n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm))
    result.append(f"{s}\n")
sys.stdout.write("".join(result))

用 itertools.permutations，用 sys.stdout.write 逐行輸出結果。使用時間約為 12.3 s，記憶體約為 3.4 MB，通過測試。

import sys, itertools

n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm)) + "\n"
    sys.stdout.write(s)

ZeroJudge 解題筆記：e420. 灰姑娘的新衣

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


ZeroJudge 題目連結：e420. 灰姑娘的新衣

解題想法

我用字典 color_idx 儲存各種顏色對應的衣服編號，另一個字典 idx_color 儲存各種衣服編號有的顏色，顔色不重複。最後再計算所有的組合數，輸出最多顔色的衣服，輸出完美搭配的顔色。

Python 程式碼

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

import sys
from collections import defaultdict

color_idx = defaultdict(list)  # 各種顏色對應的衣服編號，可重複
idx_color = defaultdict(set)  # 各種衣服編號有的顏色，不重複
cnt = 0  # 衣服編號
for line in sys.stdin:
    line = line.strip()  # 刪除最後的 \n
    cnt += 1  # 衣服編號加 1
    color_idx[line].append(cnt)  # 顏色 line 有的編號加上 cnt
    idx_color[cnt].add(line)  # 編號 cnt 有的顏色加上 line
    for s in sys.stdin:
        s = s.strip()  # 讀取一行字串，刪除最後的 \n
        if s == "@" or s == "#": break  # 讀到 # 或 @，中止迴圈
        color_idx[s].append(cnt)  # 顏色 s 有的編號加上 cnt
        idx_color[cnt].add(s)  # 編號 cnt 有的顏色加上 s，不重複
comb = 1  # 組合數
for v in idx_color.values(): comb *= len(v)
print(comb)
most_color = []
n = len(idx_color)  # 編號數量
perfect = []
imax = max([len(v) for v in color_idx.values()])
for k, v in color_idx.items():
    if len(v) == imax:
        most_color.append(k)
    if len(set(v)) == n:
        perfect.append(k)
print(",".join(sorted(most_color)))
print(",".join(sorted(perfect)))

ZeroJudge 解題筆記：e293. 花開花落，雨初臨

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


ZeroJudge 題目連結：e293. 花開花落，雨初臨

解題想法

這題的題目敘述根本就是在寫小說，重點只有「要找出給定的數字在 100 以內的質因數」。解題時要先建表 primes，列出 0 到 100 之間的質數，只有 25 個，直接打進程式碼就好。接下來計算這些質數相乘的結果 pq，假設要檢查的數字為 $m$，如果 $s = gcd(m, pq)$ 等於 1，則 $m$ 在 0 到 100 之間沒有質因數；反之，從 primes 之中依序取出質數 prime，檢查 prime 是否為 s 的因數即可。不過這題的輸出最大會到 5000 位，要用大數運算，所以我只有用 Python 解題。

Python 程式碼

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

import sys, math

# 建表，2 ~ 100 之間的質數
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
          31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
          73, 79, 83, 89, 97}
# pq，2 ~ 100 所有的質數相乘
pq = 1
for prime in primes: pq *= prime
# 主要的解題過程
result = []  # 儲存結果用的空串列
lines = sys.stdin.readlines()
for line in lines[1:]:
    m = int(line)  # 轉成整數 m
    res = []  # 儲存 m 的答案用的空串列
    s = math.gcd(m, pq)
    if s == 1:  # m 在 0 到 100 之間沒有質因數
        result.append("Terrible Silence...\n")
    else:
        for prime in primes:  # 依序由 primes 中取出質數，檢查是否為 s 的因數
            if s%prime == 0:  # 如果 prime 是因數
                res.append(f"{prime:d}")  # prime 轉成字串加入 res
        result.append(" ".join(res) + "\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：e284. 放暑假了!!!!!

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


ZeroJudge 題目連結：e284. 放暑假了!!!!!

解題想法

這題主要考輸入、輸出優化，因為測資數量極大，如果沒有優化輸入、輸出會超時。在 Python 我習慣用 sys.stdin.readlines() 一次讀取所有的測資，並將所有的輸出存在串列 result 之中，最後再用 sys.stdout.write("".join(result)) 一次印出所有答案。在 C++ 如果要用 cin 及 cout，必須加上 ios::sync_with_stdio(0); cin.tie(0);，不然就是改用 scanf 及 printf。事先用字典或集合建表，儲存 $2^0$ 到 $2^31$ 對應的值，讀取測資之後再判斷這個數字是否在表格之中，這樣速度會比較快。但是經過實測之後發現，C++ 的 map 及 unordered_map 都很慢，要用 set 才能過關； Python 的 dict, defaultdict, set 都能過關。

Python 程式碼

用 dict 建表，使用時間約為 4.2 s，記憶體約為 413.6 MB，通過測試。

import sys

table = dict()
x = 1
for _ in range(32):
    table[x] = True
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))

用 set 建表，使用時間約為 4.1 s，記憶體約為 418.2 MB，通過測試。

import sys

table = set()
x = 1
for _ in range(32):
    table.add(x)
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：e272. gcd(Fm,Fn)

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


ZeroJudge 題目連結：e272. gcd(Fm,Fn)

解題想法

這題考數學，必須運用費氏數列的特性 $$ gcd(F_m, F_n) = F_{gcd(m, n)} $$ 如果直接計算 $F_m, F_n$ 的數值再取 $gcd$，在 $m, n$ 極大的狀況下會超時。

Python 程式碼

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

import sys, math

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

for line in sys.stdin:
    a, b = map(int, line.split())
    print(fib[math.gcd(a, b)])

ZeroJudge 解題筆記：e128. 新北100-1貪食蛇

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


ZeroJudge 題目連結：e128. 新北100-1貪食蛇

解題想法

這題要找位置的數學規律，如果模擬移動的過程一定會超時。

Python 程式碼

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

import math, sys

def find_position(t):  # 輸入目前的時刻計算位置
    if t == 1: return (1, 1)  # 特例，t 等於 1，回傳 (1, 1) 並結束函式
    
    ring = math.floor(math.sqrt(t))  # 已走完的圈數
    #ring = math.isqrt(t)    # 已走完的圈數，Python 3.8 之後才有 math.isqrt
    
    t -= ring * ring  # t 扣掉已走完的圈數平方，換成位移量
    if t == 0:  # 如果 t 等於 0，剛好在這圈結束的位置
        if ring%2: return (1, ring)  # 如果是奇數圈，回傳 (1, ring) 並結束函式
        else: return (ring, 1)  # 如果是偶數圈，回傳 (ring, 1) 並結束函式
    else: ring += 1  # 其它狀況，圈數加 1
    
    x, y = 0, 0  # 座標 (x, y)
    if ring%2:  # 奇數圈
        if t > ring:  # 在底部向左移動
            x = 2*ring - t  
            y = ring
        else:  # 在右側向下移動
            x = ring
            y = t
    else:  # 偶數圈
        if t > ring:  # 在右側向上移動
            x = ring
            y = 2*ring - t
        else:  # 在底部向右移動
            x = t
            y = ring
    
    return (x, y)

for line in sys.stdin:
    t = int(line)
    if t == 0: break
    print(*find_position(t))

ZeroJudge 解題筆記：d985. Gran Turismo 5

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


ZeroJudge 題目連結：d985. Gran Turismo 5

解題想法

依序讀取每一圈的時間，將單位換成 s，更新最短秒數、計算總秒數，最後輸出所有圈數的最短秒數及平均。

Python 程式碼

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

track = 0  # 圈數
N = int(input())  # N 組測資
for _ in range(N):  # 執行 N 次
    track += 1  # 圈數加 1
    print(f"Track {track:d}:")
    M = int(input())  # M 行資料
    best = float('inf')  # 最短秒數
    total = 0  # 總秒數
    for _ in range(M):  # 執行 M 次
        m, s = map(int, input().split())  # 單圈時間 m's"
        t = m*60 + s  # 換成秒數
        best = min(best, t)  # 新的最短秒數
        total += t  # 更新總秒數
    average = total // M  # 平均值
    print(f"Best Lap: {best//60:d} minute(s) {best%60:d} second(s).")
    print(f"Average: {average//60:d} minute(s) {average%60:d} second(s).")
    print()

ZeroJudge 解題筆記：d984. 棄保效應

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


ZeroJudge 題目連結：d984. 棄保效應

解題想法

我用三層 if 解題，討論 A、B、C 三個人分別為最高票的狀況下，第一名票數減去第三名的票數之後是否仍大於第二名的票數。

Python 程式碼

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

import sys

for line in sys.stdin:
    a, b, c = map(int, line.split())  # 三個人的票數
    if a > b and a > c:  # A 最高票
        if b > c:  # B 第二名
            if a-c > b: print("A")  # A 減 C 的票數還贏
            else: print("B")  # 反之 B 贏
        else:  # C 第二名
            if a-b > c: print("A")  # A 減 B 的票數還贏
            else: print("C")  # 反之 C 贏
    elif b > a and b > c:  # B 最高票
        if a > c:  # A 第二名
            if b-c > a: print("B")  # B 減 C 的票數還贏
            else: print("A")  # 反之 A 贏
        else:  # C 第二名
            if b-a > c: print("B")  # B 減 A 的票數還贏
            else: print("C")  # 反之 C 贏
    else:  # C 最高票
        if a > b:  # A 第二名
            if c-b > a: print("C")  # C 減 B 的票數還贏
            else: print("A")  # 反之 A 贏
        else:  # B 第二名
            if c-a > b: print("C")  # C 減 A 的票數還贏
            else: print("B")  # 反之 B 贏

ZeroJudge 解題筆記：d881. 作業苦多

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


ZeroJudge 題目連結：d881. 作業苦多

解題想法

這題可以寫迴圈直接跑，也可以先推導數學公式之後再代公式求解。

Python 程式碼

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

import sys

for line in sys.stdin:
    d = int(line)  # 公差的增量
    dp = [0]*51  # 儲存第 0 ~ 50 項的串列
    dp[1] = 1  # 第 1 項為 1
    b = 1  # 公差，預設為 1
    isum = 1  # 加總，先加第 1 項
    for i in range(2, 51):  # 計算第 2 到 50 項
        dp[i] = dp[i-1] + b  # 第 i 項為第 i-1 項加上 b
        isum += dp[i]  # 更新 isum
        b += d  # 更新 b
    print(isum)  # 印出 isum

只要用到前一項，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    d = int(line)  # 公差的增量
    last = 1  # 第 1 項為 1
    b = 1  # 公差，預設為 1
    isum = 1  # 加總，先加第 1 項
    for i in range(2, 51):  # 計算第 2 到 50 項
        last += b  # 第 i 項為第 i-1 項加上 b
        isum += last  # 更新 isum
        b += d  # 更新 b
    print(isum)  # 印出 isum

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

import sys

for line in sys.stdin:
    print(1275 + int(line)*19600)

ZeroJudge 解題筆記：d732. 二分搜尋法

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


ZeroJudge 題目連結：d732. 二分搜尋法

解題想法

可以自訂二分搜尋法的函式，也可以用 Python 的 bisect.bisect_left 或是 C++ algorithm 函式庫的 lower_bound 解題。注意，這題的位數是從 1 開始計算，搜尋到的索引值要加 1 才是答案。

Python 程式碼

自己寫二分搜尋法，使用時間約為 1.1 s，記憶體約為 20.9 MB，通過測試。

def binary_search(arr, target):  # 自己寫二分搜尋法，代入串列 arr 及目標 target
    low, high = 0, len(arr)-1  # 索引值的下限、上限
    while low <= high:  # 如果 low 小於等於 high 繼續執行
        mid = (high - low) // 2 + low  # 計算中間值 mid
        if arr[mid] == target: return mid+1  # 找到目標，回傳 mid，離開函式
        if arr[mid] > target:  # 目標在左半邊，降低 high
            high = mid - 1
        else:  # 目標在右半邊，提升 low
            low = mid + 1
    if arr[low] != target: return 0  # 如果沒有找到目標，回傳 0

if __name__ == "__main__":
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    for t in map(int, input().split()):
        print(binary_search(arr, t))

bisect_left，使用時間約為 0.3 s，記憶體約為 20.9 MB，通過測試。

from bisect import bisect_left

n, k = map(int, input().split())
arr = list(map(int, input().split()))
for x in map(int, input().split()):
    idx = bisect_left(arr, x)
    if arr[idx] == x: print(idx+1)
    else: print(0)

ZeroJudge 解題筆記：d710. parking lot

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


ZeroJudge 題目連結：d710. parking lot

解題想法

這題用字典儲存資料很方便，一個儲存廠牌對應的顏色，另一個儲存顏色對應的廠牌，最後再依照測資從字典中讀取資料並輸出。

Python 程式碼

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

import sys
from collections import defaultdict

for line in sys.stdin:
    if not line.strip(): continue  # 跳過空行
    n, m = map(int, line.split())  # n 輛車， m 個指示
    brands = defaultdict(list)  # 廠牌對應的顏色
    colors = defaultdict(list)  # 顏色對應的廠牌
    for _ in range(n):  # 讀取 n 行資料
        b, c = input().split()  # 廠牌 b，顏色 c
        brands[b].append(c)
        colors[c].append(b)
    for _ in range(m):  # 讀取 m 個指示
        x, y = input().split()
        if x == "brand":  # 如果 x 等於 brand
            for c in brands[y]:  # 依序取出 brands[y] 的顏色
                print(f"{y:s} {c:s}")
        elif x == "color":  # 如果 x 等於 color
            for b in colors[y]:  # 依序取出 colors[y] 的廠牌
                print(f"{b:s} {y:s}")
    print()  # 空一行