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