ZeroJudge 解題筆記：r580.10432 - Polygon Inside A Circle

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


ZeroJudge 題目連結：r580.10432 - Polygon Inside A Circle

解題想法

題目有多筆測資。每一列有 2 個數字，分別代表半徑 $r$，於圓內畫出正 $n$ 邊形，題目要回傳這個正 $n$ 邊形的面積。這題考數學，可以將正 $n$ 邊形以圓心為頂點，分割成 $n$ 個等腰三角形，等長的兩個邊之間的夾角為 $\theta = 2 \pi / n$，三角形面積為 $$ a = \frac{1}{2} r^2 \sin \theta $$ 因此正 $n$ 邊形面積為 $area = a \times n$。

Python 程式碼

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

def solve():
    import sys, math
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield float(part)

    tokens = get_tokens()

    while True:
        try:
            r = next(tokens)
            n = next(tokens)
        except StopIteration:
            break
        
        theta = 2.0 * math.pi / n
        area = 0.5 * r * r * math.sin(theta) * n
        sys.stdout.write(f"{area:.3f}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：729. My Calendar I

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


LeetCode 題目連結：729. My Calendar I

解題想法

中等難度題，題目給一個 class 部分的程式碼，及一個包含行程開始、結束時間的串列，要求我們完成 class 之中的函式 book，於函式中先檢查這個行程是否與原有行程時間重複，如果重複回傳 False；如果不重複，更新資料並回傳 True。

由於這題的測資不多，可以用一層 for 迴圈逐一檢查新的時間 $startTime$ 及 $endTime$ 是否與原有行程重疊。如果想要再更快速一點，可以用字典儲存每一個排入的行程開始時刻及對應的結束時刻，再用另一個陣列 $starts$ 儲存行程開始時間，並用二分搜尋法找新的時間 $startTime$ 於 $starts$ 之中插入的索引值，檢查 $startTime$ 及 $endTime$ 是否與前、後的行程重疊。

Python 程式碼

Runtime: 179 ms, beats 50.25%. Memory: 20.30 MB, beats 24.38%.

class MyCalendar:
    def __init__(self):
        self.intervals = []  # (start, end)

    def book(self, startTime: int, endTime: int) -> bool:
        # 逐一檢查時間時否重疊
        for s, e in self.intervals:
            if startTime < e and endTime > s:
                return False
        self.intervals.append((startTime, endTime))
        return True


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)

Runtime: 19 ms, beats 98.17%. Memory: 20.17 MB, beats 58.06%.

from bisect import bisect_right

class MyCalendar:
    def __init__(self):
        self.intervals = dict()  # start: end
        self.starts = []

    def book(self, startTime: int, endTime: int) -> bool:
        # 用二分搜尋法找 starts 之中插入 startTime 的右側位置
        idx = bisect_left(self.starts, startTime)
        # 前面有別的行程，檢查時間是否重疊
        if idx > 0:
            prev_end = self.intervals[self.starts[idx - 1]]
            if startTime < prev_end:
                return False
        # 後面有別的行程，檢查時間是否重疊
        if idx < len(self.starts):
            next_start = self.starts[idx]
            if endTime > next_start:
                return False
        # 於 starts 之中插入新資料並保持排序
        self.intervals[startTime] = endTime
        self.starts.insert(idx, startTime)
        return True


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)

LeetCode 解題筆記：3483. Unique 3-Digit Even Numbers

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


LeetCode 題目連結：3483. Unique 3-Digit Even Numbers

解題想法

簡單題，題目給一個包含正整數或零的陣列 $digits$，從 $digits$ 之中取出 $3$ 個數字組合成沒有前導零 $3$ 位數的偶數，回傳這樣的數總共有幾種組合。這是我一開始的寫法是用三層 for 迴圈從 $digits$ 之中取數字，最外層的 for 迴圈跑第一位 $x$，如果取出的數字為 $0$ 就跳過；第二層的 for 迴圈跑第二位 $y$，這個位數沒有限制；最內層的 for 迴圈跑第三位 $z$，這個位數只能是偶數。將 $100 x + 10 y + z$ 存入集合 $ans$ 之中，答案為 $ans$ 的長度。因為題目只有 $3$ 位數，這個寫法的速度還算快。

另一個寫法是用三層 for 迴圈枚舉所有的 $3$ 位數偶數，計算這個偶數需要的數字數量，如果 $digits$ 之中可以提併足夠的數字，就將答案 $ans$ 數量加 1。

Python 程式碼

使用集合。Runtime: 15 ms, beats 69.45%. Memory: 19.21 MB, beats 72.53%.

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        n = len(digits)
        ans = set()
        for i in range(n):
            x = digits[i]
            if x == 0: continue
            for j in range(n):
                if i == j: continue
                y = digits[j]
                for k in range(n):
                    if k == i or k == j: continue
                    z = digits[k]
                    if z % 2 == 0:
                        ans.add(x*100 + y*10 + z)
        return len(ans)

字典計數。Runtime: 412 ms, beats 7.47%. Memory: 19.28 MB, beats 72.53%.

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        cnt = Counter(digits)  # 各種數字的數量
        ans = 0  # 答案
        # 枚舉所有不含前導 0、3 位數的偶數
        for i in range(1, 10):  # 1 ~ 9
            for j in range(10):  # 0 ~ 9
                for k in range(0, 10, 2):  # 2, 4, 6, 8
                    need = Counter([i, j, k])  # 需要的數字數量
                    # digits 之中有足夠的數字，答案加 1
                    if need[i] <= cnt[i] and need[j] <= cnt[j] and need[k] <= cnt[k]:
                        ans += 1
        return ans

ZeroJudge 解題筆記：r581.10489 - Boxes of Chocolates

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


ZeroJudge 題目連結：r581.10489 - Boxes of Chocolates

解題想法

每筆測資第 $1$ 列只有一個整數 $T$，代表接下來有 $T$ 組測資。第 $2$ 列有兩個整數 $n, b$，分別代表朋友人數、收到的禮物盒數量。接下來 $b$ 列，每列開頭有 $1$ 個數字代表這列的後方有幾個數字，第 $1$ 到倒數第 $2$ 個數字為每一層盒子的數量，最後一個數字為最內層盒子內的巧克力數量。先計算拿到的巧克力總數 $total$，輸出 $total$ 除以 $n$ 的餘數。為了計算每一個盒子內的巧克力數量，可以先設定變數 $t = 1$，接下來依序讀取每層的盒子數量及最內層盒子內的巧克力數量，將 $t$ 乘上這些數字就是這個盒子內的巧克力總數。最後再將所有盒子的巧克力數量相加，對 $n$ 取餘數就是答案。

用 C 或 C++ 解題要很小心，計算盒子內巧克力數量時，每次相加或相乘都要對 $n$ 取餘數，否則數值會超出 int 的上限。

Python 程式碼

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

T = int(input())
for _ in range(T):
    n, b = map(int, input().split())
    total = 0
    for __ in range(b):
        parts = list(map(int, input().split()))
        m = parts[0]
        t = 1
        for i in range(1, m + 1):
            t *= parts[i]
        total += t
    print(total % n)

LeetCode 解題筆記：2265. Count Nodes Equal to Average of Subtree

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


LeetCode 題目連結：2265. Count Nodes Equal to Average of Subtree

解題想法

中等難度題，這題考二元樹及 dfs。題目給一棵二元樹的根節點 $root$，要找出有幾個節點本身及其子節點的平均值與節點的值相等，主要的解題過程在於如何設計一個遞迴函式，從代入的節點一路往下走，計算所有子節點的加總及數量，請看程式碼會比較清楚。

Python 程式碼

Runtime: 46 ms, beats 85.47%. Memory: 19.64 MB, beats 33.89%.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfSubtree(self, root: TreeNode) -> int:
        ans = 0

        def dfs(node):
            # ans 要設定成非區域變數，才能在函式中修改數值
            nonlocal ans
            
            # 遞迴出口，沒有節點，回傳 (加總, 數量) (0, 0)
            if not node: return (0, 0)
            
            # 遞迴，代入左子樹、右子樹，求各自的加總及子節點數量
            lsum, lcnt = dfs(node.left)
            rsum, rcnt = dfs(node.right)
            # 合併，左、右子數的加總及數量，加上這個節點的值及數量 1
            total = lsum + node.val + rsum
            cnt = lcnt + 1 + rcnt
            # 如果這個節點以下的平均等於這個節點的值，答案加 1
            if total // cnt == node.val:
                ans += 1
            # 回傳這個節點的加總及節點數量
            return (total, cnt)
        # 呼叫 dfs，代入根節點找答案，最後回傳答案
        dfs(root)
        return ans

ZeroJudge 解題筆記：r582.10491 - Cows and Cars

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


ZeroJudge 題目連結：r582.10491 - Cows and Cars

解題想法

題目是多筆測資。每組測資有 $3$ 個數字，分別代表牛的數量、汽車的數量、主持人打開門的數量，假設這 $3$ 個數分別存入變數 $cows$、$cars$、$show$，門的數量 $total = cows + cars$。觀眾先選一扇問，主持人打開 $show$ 扇後面是牛的門，計算觀眾換門且選中汽車的機率，答案輸出到小數點後第 5 位。

這題考數學。換門且選中汽車的狀況有 2 種，第 1 種是先選中後面是牛的門，再換到後面是汽車的門，機率為 $$ P_1 = \frac{cows}{total} \times \frac{cars}{total - show - 1} $$ 上式中第 2 項的分母要減 1，扣掉一開始選的門。第 2 種是先選中後面是汽的門，再換到後面是汽車的門，機率為 $$ P_2 = \frac{cars}{total} \times \frac{cars - 1}{total - show - 1} $$ 上式中第 2 項的分子、分母都要減 1，扣掉一開始選的門。兩種機率相加就是答案。

Python 程式碼

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

def solve():
    import sys

    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield(int(part))

    tokens = get_tokens()
    
    while True:
        try:
            cows = next(tokens)
            cars = next(tokens)
            show = next(tokens)
        except StopIteration:
            break
        
        # 先選到牛的機率 * 剩下的門有車的機率 + 先選到車的機率 * 剩下的門有車的機率
        total = cows + cars
        ans = cows / total * cars / (total - show - 1) + cars / total * (cars - 1) / (total - show - 1)
        sys.stdout.write(f"{ans:.5f}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3871. Count Commas in Range II

作者：王一哲
日期：2026年9月9日


LeetCode 題目連結：3871. Count Commas in Range II

解題想法

中等難度題，3870. Count Commas in Range 的加強版。題目給一個正整數 $n$ $(1 \leq n \leq 10^{15})$，計算 $1$ 到 $n$ 共有幾個分隔數字的逗號，小於 $1000$ 的數字不需要加逗號，大於等於 $1000$ 的數字，每隔 $3$ 位數加 $1$ 個逗號。由於 $n$ 最大到 $10^{15}$，可以分成 $5$ 組計算答案：

1. $10^3 \leq x < 10^6$，每個數字加 $1$ 個逗號，答案加上範圍內的數字個數。
2. $10^6 \leq x < 10^9$，每個數字加 $2$ 個逗號，答案加上範圍內的數字個數乘以 $2$。
3. $10^9 \leq x < 10^{12}$，每個數字加 $3$ 個逗號，答案加上範圍內的數字個數乘以 $3$。
4. $10^{12} \leq x < 10^{15}$，每個數字加 $4$ 個逗號，答案加上範圍內的數字個數乘以 $4$。
5. 如果 $n = 10^{15}$，答案再加上 $5$ 個逗號。

這題如果用 C++ 解題，在使用 min 取最小值時，手動輸入的常數要在最後面加上 LL，標記為 long long 格式，否則 min 之中兩個整數格式不同，無法比較。如果用 C 語言解題，因為 C 語言沒有內建的 min 能用，要在最前面用 define 自己定義 min。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.31 MB, beats 13.61%.

class Solution:
    def countCommas(self, n: int) -> int:
        ans = 0
        if n >= 10**3:  # 10**3 ~ 10**6 - 1
            ans += min(n - 10**3 + 1, 10**6 - 10**3)
        if n >= 10**6:  # 10**6 ~ 10**9 - 1
            ans += min(n - 10**6 + 1, 10**9 - 10**6) * 2
        if n >= 10**9:  # 10**9 ~ 10**12 - 1
            ans += min(n - 10**9 + 1, 10**12 - 10**9) * 3
        if n >= 10**12:  # 10**12 ~ 10**15 - 1
            ans += min(n - 10**12 + 1, 10**15 - 10**12) * 4
        if n >= 10**15:  # 10**15 ~ 10**18 - 1
            ans += min(n - 10**15 + 1, 10**18 - 10**15) * 5
        return ans

ZeroJudge 解題筆記：r775.Let's go on a trip

作者：王一哲
日期：2026年9月9日


ZeroJudge 題目連結：r775.Let's go on a trip

解題想法

題目第一列給一個整數 $n$，代表共有 $n$ 座城市，編號為 $1$ 到 $n$。第二列給一個整數 $m$，代表要走訪 $m$ 座城市。接下有 $n$ 列，每列 $n$ 個數字，第 $i$ 列、第 $j$ 欄如果是 $1$，代表城市 $i, j$ 之間有道路連接，題目保證 $j, i$ 之間也有道路連接；反之，如果數字為 $0$，代表城市 $i, j$ 之間沒有道路連接。最後一列有 $m$ 個整數，代表要走訪的城市編號。這題只要回答是否能走訪這 $m$ 個城市，同一個城市可以多次走訪。

可以將城市當成節點，道路當成邊，只要檢查最後一列的城市是否相連，這樣的題目很適合用併查集處理。我習慣用 class 自訂併查集物件，這次在 class 之中再自訂一個函式 is_unite，檢查代入的兩個節點是否連通。先取第一個要走訪的城市，以這個城市的父節點 $root$ 為準，如果其它要走訪的城市父節點不是 $root$，答案為 NO；如果這 $m$ 個城市的父節點都是 $root$，答案為 YES。

Python 程式碼

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

class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.sz = [1] * (n + 1)
    
    def rfind(self, x):
        if x == self.parent[x]:
            return x
        self.parent[x] = self.rfind(self.parent[x])
        return self.parent[x]
    
    def unite(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        if root_u != root_v:
            if self.sz[root_u] < self.sz[root_v]:
                root_u, root_v = root_v, root_u
            self.sz[root_u] += self.sz[root_v]
            self.parent[root_v] = root_u
            return True
        return False

    def is_unite(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        return root_u == root_v

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        m = int(data[ptr + 1])
        ptr += 2
        dsu = DisjointSetUnion(n)
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                x = int(data[ptr])
                ptr += 1
                if x == 1:
                    dsu.unite(i, j)
        
        ans = True
        root = int(data[ptr])
        ptr += 1
        for _ in range(m - 1):
            x = int(data[ptr])
            ptr += 1
            if not dsu.is_unite(root, x):
                ans = False
                break
        result.append("YES\n" if ans else "NO\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3870. Count Commas in Range

作者：王一哲
日期：2026年9月8日


LeetCode 題目連結：3870. Count Commas in Range

解題想法

困難題。題目給一個正整數 $n$ $(1 \leq n \leq 10^5)$，計算 $1$ 到 $n$ 共有幾個分隔數字的逗號，小於 $1000$ 的數字不需要加逗號，大於等於 $1000$ 的數字，每隔 $3$ 位數加 $1$ 個逗號。由於 $n$ 最大只到 $10^5$，因此答案只有兩種：

1. $n < 1000$，答案 $0$。
2. $n \geq 1000$，答案 $n - 999$，因為 $1000$ 也要加逗號。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 46.53%.

class Solution:
    def countCommas(self, n: int) -> int:
        if n < 1000: return 0
        return n - 999

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.57 MB, beats 51.38%.

class Solution {
public:
    int countCommas(int n) {
        if (n < 1000) return 0;
        return n - 999;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 9.14 MB, beats 64.94%.

int countCommas(int n) {
    if (n < 1000) return 0;
    return n - 999;
}

ZeroJudge 解題筆記：r768.10622 - Perfect Pth Powers

作者：王一哲
日期：2026年9月8日


ZeroJudge 題目連結：r768.10622 - Perfect Pth Powers

解題想法

題目給一個整數 $x$，如果 $x = b^p$，找出最大的 $p$，如果 $x = 0$ 代表測資結尾，不需要計算。題目保證 $x$ 可以用 32-bit 的整數儲存。這題考質因數分解，假設 $x = 2^4 \times 3^2 = 144 = 12^2$，答案會被 $3^2$ 限制，答案為 $2$。先對 $x$ 質因數分解，找出所有質因數次方的最大公因數設為答案 $p$。用 while 迴圈從 $i = 2$ 開始測試，直到 $i^2 > x$ 為止，這個條件很重要，可以節省很多運算時間。如果跑完 while 迴圈之後 $x > 1$，代表 $x$ 是質數，答案 $p = 1$。

這題還有一個陷阱，當 $x < 0$ 時，$p$ 不能是偶數，這樣會使 $x$ 變為正值，必須將 $p$ 除以 $2$ 直到 $p$ 變成奇數為止。

Python 程式碼

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

from math import gcd

while True:
    x = int(input()) 
    if x == 0: break  # 結束
    if x == 1 or x == -1:  # 特例
        print(1)
        continue
        
    pm = 1  # 正負
    if x < 0:  # 處理負值
        pm = -1
        x = -x
    
    p = -1  # 答案先設為 -1
    i = 2  # 質因數從 2 開始往上找
    while x >= i * i:  # 重點，只要測試到 i = sqrt(x)
        m = 0  # 次方
        while x % i == 0:  # 不斷除以 i 找次方
            m += 1
            x //= i
        i += 1  # 因數加 1

        if m > 0:  # 次方大於 0
            if p == -1: p = m  # 第一個質因數，p 設定為 m
            else: p = gcd(p, m)  # 取 p, m 的最大公因數
    
    # 如果 x 大於 1，x 是質數，p 只能是 1
    if x > 1: p = 1
    
    # 如果 n 是負值，p 除以 2 直到 p 變為奇數
    if pm < 0:
        while p % 2 == 0:
            p //= 2
    # 印出答案
    print(p)