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)