ZeroJudge 解題筆記：d623. 反方陣

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


ZeroJudge 題目連結：d623. 反方陣

解題想法

假設矩陣 $$ M = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} $$ 其行列式值 $det(M) = ad - bc$。如果 $det(M) \neq 0$，$M$ 是可逆的，其反矩陣 $$ M^{-1} = \frac{1}{det(M)} \begin{bmatrix} d & -b \\ -c & a \\ \end{bmatrix} $$ 另外要注意，題目的說明是4個0表示結束，實際測資以一個零表示結束。

Python 程式碼

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

while True:
    line = list(map(int, input().split()))
    if len(line) == 1 and line[0] == 0: break  # 只有一個 0，中止迴圈
    a, b = line  # 方陣 [[a, b], [c, d]]
    c, d = map(int, input().split())
    det = a*d - b*c  # 行列式值
    if det == 0:  # 沒有反方陣
        print("cheat!")
    else:  # 反方陣 (1/det)*[[d, -b], [-c, a]]
        print(f"{d/det:.5f} {-b/det:.5f}")
        print(f"{-c/det:.5f} {a/det:.5f}")

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

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    if lines[idx].strip() == "0": break  # 只有一個 0，中止迴圈
    a, b = map(int, lines[idx].split())  # 方陣 [[a, b], [c, d]]
    idx += 1
    c, d = map(int, lines[idx].split())
    idx += 1
    det = a*d - b*c  # 行列式值
    if det == 0:  # 沒有反方陣
        result.append("cheat!\n")
    else:  # 反方陣 (1/det)*[[d, -b], [-c, a]]
        result.append(f"{d/det:.5f} {-b/det:.5f}\n")
        result.append(f"{-c/det:.5f} {a/det:.5f}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d586. 哈密瓜美語

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


ZeroJudge 題目連結：d586. 哈密瓜美語

解題想法

這題用兩個字典建立數字轉英文、英文轉數字的對照表，再依照讀取到的測資開頭是數字或字母，判斷要從哪一個表格找答案。

Python 程式碼

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

s1 = "mjqhofawcpnsexdkvgtzblryui"  # 數字轉英文用的字串
s2 = "uzrmatifxopnhwvbslekycqjgd"  # 英文轉數字用的字串
ntoc, cton = dict(), dict()  # 數字轉英文、英文轉數字的對照表
for i, c in enumerate(s1, start=1): ntoc[str(i)] = c
for i, c in enumerate(s2, start=1): cton[c] = i
n = int(input())  # n 道謎題
for _ in range(n):  # 執行 n 次
    line = list(input().split())  # 讀取一行資料分割後存入串列
    m = int(line[0])  # 資料長度為 m
    if line[1].isalpha():  # 如果 line[1] 是字母
        print(sum(cton[c] for c in line[1:]))  # 依序讀取 line[1] ~ line[-1] 代入表中找數字求加總
    else:  # 如果 line[1] 是數字
        print("".join([ntoc[i] for i in line[1:]]))  # 依序讀取 line[1] ~ line[-1] 代入表中找字母組成字串

ZeroJudge 解題筆記：d584. 技能點數skill

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


ZeroJudge 題目連結：d584. 技能點數skill

解題想法

依照職業及當時的等級更新技能點數即可。

Python 程式碼

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

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    job, level = map(int, line.split())
    tot = 0
    if job == 2 and level >= 8:  # 如果是法師，8 級一轉
        tot += 1 + (level-8)*3  # 點數加上轉職的 1 及每升一級加的 3 點
    elif (job == 1 or job == 3 or job == 4) and level >= 10:  # 如果是劍士、弓箭手、盜賊，10 級一轉
        tot += 1 + (level-10)*3  # 點數加上轉職的 1 及每升一級加的 3 點
    if job != 0 and level >= 30: tot += 1  # 如果不是初心者，30 級二轉，點數加 1
    if job != 0 and level >= 70: tot += 1  # 如果不是初心者，70 級三轉，點數加 1
    if job != 0 and level >= 120: tot += 3  # 如果不是初心者，120 級四轉，點數加 3
    result.append(f"{tot:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d575. 末日審判

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


ZeroJudge 題目連結：d575. 末日審判

解題想法

這題看起來很簡單，只要計算兩個點之間的距離是否小於、等於半徑即可，但是用 Python 解題時需要用 sys.stdin.readlines() 及 sys.stdour.write() 加速，否則會超時；用 C++ 解題要使用 long long，否則會溢位。

Python 程式碼

第8筆測資超時。

import sys

for line in sys.stdin:
    x0, y0, x1, y1, r = map(int, line.split())
    if abs(x0-x1) + abs(y0-y1) <= r: print("die")
    else: print("alive")

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

import sys

lines = sys.stdin.read().splitlines()  # 一次讀取所有資料，減少讀取次數
results = []  # 儲存要輸出的結果
for line in lines:  # 從 lines 依序讀取資料 line
    x0, y0, x1, y1, r = map(int, line.split())  # 用 split 拆開 line，轉成 int，存入變數
    if abs(x0-x1) + abs(y0-y1) <= r: results.append("die\n")  # 先將要輸出的字串加到 results
    else: results.append("alive\n")
sys.stdout.write("".join(results))  # 將 results 合併成一個很長的字串再一次輸出

ZeroJudge 解題筆記：d574. 節約符咒

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


ZeroJudge 題目連結：d574. 節約符咒

解題想法

第4筆測資只有一行，用空格分隔數量與字串，用 Python 解題需要特別處理。依序讀取字串中每個字母，計算連續出現的相同字母數量，將數量與對應的字母組成字串。

Python 程式碼

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

line = list(input().split())  # 讀取一行資料並用空格分隔存成串列
n = int(line[0])  # 字串長度
if len(line) == 1: s = input().strip()  # 如果 line 只有一項，再讀取一行字串
else: s = line[1]  # 反之，字串在 line[1]
t = ""  # 儲存答案用的空字串
cnt = 1  # 連續相同字母的數量，預設為 1
last = s[0]  # 前一個字母，預設為 s[0]
for c in s[1:]:  # 依序讀取 s[1] ~ s[n-1]
    if c == last: cnt += 1  # 如果 c 等於 last，cnt 加 1
    else:  # 反之，結算之的連續相同字母數量
        t += str(cnt) + last  # cnt 轉成字串加上 last，接到 t 之後
        cnt = 1  # cnt 重置為 1
        last = c  # last 重置為 c
t += str(cnt) + last  # 最後要再結算一次 cnt 與 last
if len(t) < n: print(t)  # 如果 t 較短，印出 t
else: print(s)  # 反之，印出 s

ZeroJudge 解題筆記：d566. 秒殺率

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


ZeroJudge 題目連結：d566. 秒殺率

解題想法

這題要注意：

1. 此處的解題紀錄排在前面的資料代表時間越晚
2. 第 4 筆測資格式有問題，全部塞在同一行，用 Python 解題需要特別處理這筆測資。

Python 程式碼

理論上這樣寫應該要過關，但是第 4 筆測資格式有問題，全部塞在同一行，要再修改程式碼。

cnt = dict()  # 計數器，是否 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # AC 人數
n = int(input())  # n 筆資料
data = [input().split() for _ in range(n)]  # 先讀完所有的資料
for name, state in data[::-1]:  # 反向讀取資料，先讀取時間較早的資料
    if name not in cnt:  # 如果 name 不在 cnt 之中
        if state == "AC":  # 如果第一次就 AC
            fir += 1  # fir 加 1
            ac += 1  # ac 加 1
            cnt[name] = True  # cnt[name] 為 True
        else:  # 第一次沒有 AC
            cnt[name] = False  # cnt[name] 為 False
    elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
        ac += 1  # ac 加 1
        cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")

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

import sys

cnt = dict()  # 計數器，是否第一次就 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # 全部 AC 的人數
for line in sys.stdin:  # 讀資料直到 EOF 為止
    data = line.split()  # 先試著分割資料
    if len(data) == 1:  # 如果只有一筆，是 n
        n = int(data[0])
        data = [input().split() for _ in range(n)]  # 先讀完所有的資料
        for name, state in data[::-1]:  # 反向讀取資料，先讀取時間較早的資料
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
    else:  # 為了測資 4 全部塞在一行的狀況
        n = int(data[0])
        for i in range(2*n, 0, -2):  # 反向讀取資料，先讀取時間較早的資料
            name, state = data[i-1], data[i]
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")

ZeroJudge 解題筆記：d563. 等值首尾和

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


ZeroJudge 題目連結：d563. 等值首尾和

解題想法

題目敘述有兩個問題：

1. 題目雖然說有兩行測資，第一行為一個數字 N，代表第二行有 N 個用空格分隔的數字，但實際上只有一行，如果用 Python 解題會出事。
2. 範例的寫法看起來好像從左、右加總的數量要一樣，但其實不需要，只要前綴和、後綴和相等就好，不看數量。

Python 程式碼

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

arr = list(map(int, input().split()))[1:]  # 讀取一行資料轉成串列，不取首項
psum = 0  # 前綴和
cand = set()  # 可能的加總
for a in arr:  # 依序讀取 arr 的資料
    psum += a  # 更新 psum
    cand.add(psum)  # psum 加入 cand
ssum = 0  # 後綴和
cnt = 0  # 答案
for a in arr[::-1]:  # 反向讀取 arr 的資料
    ssum += a  # 更新 ssum
    if ssum in cand: cnt +=1  # 如果 ssum 在 cand 之中，cnt 加 1
print(cnt)  # 印出 cnt

ZeroJudge 解題筆記：d561. 被秒殺的四捨五入

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


ZeroJudge 題目連結：d561. 被秒殺的四捨五入

解題想法

這題在 Python 可以用 decimal 函式庫作弊，將數值存成 Decimal 格式的浮點數再四捨五入即可。比較正常的作法，是用字串格式儲存數字，依序判斷數字的正負號、整數位、小數點後第一位、小數點後第二位，最後再依照小數點後第三位的值判斷是否要捨去或進位。

Python 程式碼

用 decimal 函式庫作弊，使用時間約為 24 ms，記憶體約為 3.9 MB，通過測試。

from decimal import Decimal, ROUND_HALF_UP
import sys

for line in sys.stdin:
    # 將 line 轉成 Decimal 格式的十進位數字，4捨5入到小數點後第2位
    n = Decimal(line.strip()).quantize(Decimal('0.01'), rounding=ROUND_HALF_UP)
    if str(n) == "-0.00":
        print("0.00")  # -0.00 要輸出為 0.00
    else:
        print(n)

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

import sys

for line in sys.stdin:
    s = line.strip()  # 字串格式的數字
    negative = False  # 是否為負值，預設為 False
    if s[0] == '-':  # 如果 s[0] 是負號
        negative = True  # negative 設定為 True
        s = s[1:]  # 刪除 s[0]
    num = int(s[0])  # 取整數位加到 num
    s = s[2:]  # 刪除整數位、小數點
    if s and s[0] != '0':  # 處理小數點後第 1 位
        num += int(s[0])*0.1
    s = s[1:]  # 刪除 s[0]
    if s and s[0] != '0':  # 處理小數點後第 2 位
        num += int(s[0])*0.01
    s = s[1:]  # 刪除 s[0]
    if negative: num = -num  # 如果是負值，乘以 -1
    if s and s[0] in '56789':  # 如果 s[0] 大於等於 5，要 4 捨 5 入
        if negative: num -= 0.01  # 如果是負值，減 0.01
        else: num += 0.01  # 如果是正值，加 0.01
    if str(num) == "-0.0": print("0.00")  # 如果轉成字串等於 -0.0，要印出 0.00
    else: print(f"{num:.2f}")

使用 Python 及 C++ 産生重複數字的所有排列方式

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

前言

由於最寫連續寫到好幾個題目，需要從測資讀取一列數字，再産生這列數字的所有排列方式，例如 d762. 10344 - 23 out of 5。我之前都是用 Python 的 itertools.permutations 偷懶，但是為了準備之後的課程，還是來研究一下如何用遞迴及回溯産生所有的排列方式。

Python itertools.permutations

這是一個效率很好的迭代器，官方說明書在此 itertools.permutations，通常會搭配 for 迴圈一起使用，語法為

for [産生的數組名稱] in itertools.permutations(可以迭代的物件):

例如要産生 [1, 2, 3, 2, 1] 的所有排列方式可以這樣寫

from itertools import permutations

nums = [1, 2, 3, 2, 1]
for perm in permutations(nums):
    print(*perm)

如果只考慮 5 個數字的排列方式，總共會有 $5! = 120$ 種，以上的程式碼會輸出 120 行。但是這裡面有不少重複的結果，如果只想輸出不重複的結果，可以再稍微修改一下程式碼，用集合記錄已經産生過的結果，這樣就只會輸出 30 行。

from itertools import permutations

nums = [1, 2, 3, 2, 1]
used = set()
for perm in permutations(nums):
    if perm in used: continue
    used.add(perm)
    print(*perm)

ZeroJudge 解題筆記：d555. 平面上的極大點

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


ZeroJudge 題目連結：d555. 平面上的極大點

解題想法

先讀取所有點的座標存入二維串列 points，由大到小排序。用變數 max_y 記錄目前最高的 y 座標，預設值為負無窮大。從 points 之中依序讀取點的座標 x, y，如果符合以下兩種狀況，將 (x, y) 加入答案 ans 之中：

1. y 大於 max_y
2. ans 之中沒有任何一個點可以支配 (x, y)

最後將 ans 排序再印出。

Python 程式碼

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

import sys

ca = 0
for line in sys.stdin:
    ca += 1
    print(f"Case {ca:d}:")
    n = int(line)
    point = sorted([tuple(map(int, input().split())) for _ in range(n)], reverse=True)
    ans = []  # 答案
    max_y = -float('inf')  # 目前最高的 y 座標，預設為極小值
    for x, y in point:  # 從 point 依序讀取點的座標 (x, y)
        if y > max_y:  # y 大於 max_y
            ans.append((x, y))  # (x, y) 加入 ans
            max_y = y  # 更新 max_y
        # 另一種可能性，ans 之中沒有任何點可以支配 (x, y)
        elif not any(px >= x and py >= y for px, py in ans):
            ans.append((x, y))
    ans.sort()  # 由小到大排序
    print(f"Dominate Point: {len(ans):d}")
    for x, y in ans: print(f"({x:d},{y:d})")