ZeroJudge 解題筆記：h033. 雜訊移除 (Noise)

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



ZeroJudge 題目連結：h033. 雜訊移除 (Noise)

解題想法

這題在 Python 可以用 replace 將不要的字元取代成空字串。

Python 程式碼

用 replace 可以取代字串中指定的字元，取代為空字串就可以移除特定字元。使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def is_palindrome(s):  # 檢查 s 是否為迴文字串
    n = len(s)  # s 的長度 n
    for i in range(n//2):  # 依序檢查從頭尾兩端往中間檢查
        if s[i] != s[n-i-1]: return False  # 如果字元不相同回傳 False
    return True  # 如果可以跑完 for loop，回傳 True

for line in sys.stdin:
    s, n = line.split()  # 要分析的字串 s，要移除的字元 n
    s = s.replace(n, "")  # 將 s 之中的 n 取代為空字串
    print("Yes" if is_palindrome(s) else "No")  # 印出答案

如果不使用 replace，也可以遍歷字串，將要留下來的字元存到另一個空字串裡。使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def is_palindrome(s):  # 檢查 s 是否為迴文字串
    n = len(s)  # s 的長度 n
    for i in range(n//2):  # 依序檢查從頭尾兩端往中間檢查
        if s[i] != s[n-i-1]: return False  # 如果字元不相同回傳 False
    return True  # 如果可以跑完 for loop，回傳 True

for line in sys.stdin:
    s, n = line.split()  # 要分析的字串 s，要移除的字元 n
    t = ""  # 儲存 s 移除 n 之後的空字串
    for c in s:  # 依序由 s 讀取字元 c
        if c != n: t += c  # 如果 c 不等於 n，接到 t 之後
    print("Yes" if is_palindrome(t) else "No")  # 印出答案

ZeroJudge 解題筆記：g798. 帶動商機 (Business)

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



ZeroJudge 題目連結：g798. 帶動商機 (Business)

解題想法

這題按照題目敘述操作陣列即可，不需要用複雜的寫法。

Python 程式碼

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

import sys

for line in sys.stdin:
    arr = list(map(int, line.split()))[:-1]  # 讀取一開始的人數，刪掉最後的 0
    m = len(arr)  # 店家數量
    n = int(input())  # 更新 n 天
    for _ in range(n):  # 執行 n 次
        tmp = arr.copy()  # 暫存更新後的人數
        for i in range(m):  # 依序掃過 0 ~ m-1 家店
            if i == 0:  # 最左邊的店家
                if arr[i] > arr[i+1]:  # 如果人數大於右邊的店家
                    tmp[i+1] += arr[i]//10  # 右邊的店家人數增加量
            elif i == m-1:  # 最右邊的店家
                if arr[i] > arr[i-1]:  # 如果人數大於左邊的店家
                    tmp[i-1] += arr[i]//10  # 左邊的店家人數增加量
            else:  # 中間的店家
                if arr[i] > arr[i-1]:  # 如果人數大於左邊的店家
                    tmp[i-1] += arr[i]//20  # 左邊的店家人數增加量
                if arr[i] > arr[i+1]:  # 如果人數大於右邊的店家
                    tmp[i+1] += arr[i]//20  # 右邊的店家人數增加量
        arr, tmp = tmp, arr  # 交換 arr、tmp
    print(*arr)  # 印出答案

ZeroJudge 解題筆記：g797. 洗牌 (Cards)

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



ZeroJudge 題目連結：g797. 洗牌 (Cards)

解題想法

這題考陣列操作，可以將陣列先拆開成上、下兩半再合併，或是用另一個陣列儲存洗牌後的資料。

Python 程式碼

寫法1，用串列切片先找出上、下兩半的內容，再合併資料。使用時間約為 26 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 張牌，洗牌 m 次
    deck = list(map(int, input().split()))  # 讀取牌面數值
    upp, bot = deck[:n//2], deck[n//2:]  # 分成上、下兩半
    for _ in range(m):  # 執行 m 次
        for i in range(n//2):  # 執行 n//2 次
            deck[2*i] = upp[i]  # 從 upp 及 bot 依序取值放入 deck
            deck[2*i+1] = bot[i]
        upp, bot = deck[:n//2], deck[n//2:]  # 更新 upp、bot
    print(*deck)  # 印出答案

寫法2，滾動串列，將洗牌後的資料先存入另一個串列。使用時間約為 28 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 張牌，洗牌 m 次
    deck = list(map(int, input().split()))  # 讀取牌面數值
    for _ in range(m):  # 執行 m 次
        tmp = [0]*n  # 暫存洗牌後的資料
        for i in range(n//2):  # 執行 n//2 次
            tmp[2*i] = deck[i]  # 從 deck 前半取值放入 tmp
            tmp[2*i+1] = deck[n//2 + i]  # 從 deck 後半取值放入 tmp
        deck, tmp = tmp, deck  # 交換 deck、tmp
    print(*deck)  # 印出答案

ZeroJudge 解題筆記：g541. 類題:兔子跳躍(TOIP)

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



ZeroJudge 題目連結：g541. 類題:兔子跳躍(TOIP)

解題想法

雖然看起來是g498. 兔子跳躍 (Rabbit)的加強版，但其實用相同的寫法跑迴圈測試是否能走到 $d$ 一定會超時，即使用字典儲存已經跑過的值還是會超時，需要從數學上分析題目才行。如果兩種步數 $m$、$n$ 的最大公因數為 $G$、最小公倍數為 $L$，則所有 $L + kG, k = 0, 1, 2, 3, \dots$ 的數皆可以用大於等於 0 個 $m$、$n$ 組合而成，若以 $m = 9$、$n = 12$ 為例，$G = 3$、$L = 36$，則

1. $36 = 4 \times 9 = 3 \times 12$
2. $39 = 3 \times 9 + 1 \times 12$
3. $42 = 2 \times 9 + 2 \times 12$
4. $45 = 1 \times 9 + 3 \times 12$
5. $48 = 0 \times 9 + 4 \times 12$
6. $51 = 3 \times 9 + 2 \times 12$
7. $54 = 2 \times 9 + 3 \times 12$
8. $57 = 1 \times 9 + 4 \times 12$
9. $60 = 0 \times 9 + 5 \times 12 = 4 \times 9 + 2 \times 12$
10. $63 = 3 \times 9 + 3 \times 12$

Python 程式碼

寫法1，根據g498. 兔子跳躍 (Rabbit)的寫法改寫而成，第2筆測資開始超時。

import sys

def solve(m, n, d):  # 自訂函式，測是是否能走到 d
    for i in range(0, d+1, m):  # 依序測試 0, m, 2m, 3m, ...
        if (d-i)%n == 0: return True  # 如果 d-i 可以被 n 整除，能走到 d
    return False  # 如果能跑完 for 迴圈，走不到 d

for line in sys.stdin:
    m, n, q = map(int, line.split())  # 可跳距離 m、n，詢問次數 q
    for d in list(map(int, input().split())):  # 執行 q 次
        print("YES" if solve(m, n, d) else "NO")  # 印出答案

寫法2，根據以上的寫法並改用 map 儲存已經測試過的值，第2筆測資開始超時。

import sys

for line in sys.stdin:
    m, n, q = map(int, line.split())  # 可跳距離 m、n，詢問次數 q
    memo = dict()  # 記憶已經算過的數據
    def solve(d):  # 自訂函式，測是是否能走到 d
        if d in memo: return memo[d]
        for i in range(0, d+1, m):  # 依序測試 0, m, 2m, 3m, ...
            if (d-i)%n == 0:
                memo[d] = True
                return True  # 如果 d-i 可以被 n 整除，能走到 d
        memo[d] = False
        return False  # 如果能跑完 for 迴圈，走不到 d
    for d in list(map(int, input().split())):  # 執行 q 次
        print("YES" if solve(d) else "NO")  # 印出答案

ZeroJudge 解題筆記：g498. 兔子跳躍 (Rabbit)

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



ZeroJudge 題目連結：g498. 兔子跳躍 (Rabbit)

解題想法

這題測資不大，用 for 迴圈依序檢測每一個值就能過關。

Python 程式碼

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

import sys

for line in sys.stdin:
    m, n, d = map(int, line.split())  # 可跳距離 m、n，目標距離 d
    def solve():  # 自訂函式，測是是否能走到 d
        for i in range(0, d+1, m):  # 依序測試 0, m, 2m, 3m, ...
            if (d-i)%n == 0: return True  # 如果 d-i 可以被 n 整除，能走到 d
        return False  # 如果能跑完 for 迴圈，走不到 d
    print("YES" if solve() else "NO")  # 印出答案

C++ 程式碼

使用時間約為 2 ms，記憶體約為 84 kB，通過測試。

#include <cstdio>
using namespace std;

bool solve(int m, int n, int d) {  // 自訂函式，測是是否能走到 d
    for(int i=0; i<=d; i+=m) {  // 依序測試 0, m, 2m, 3m, ...
        if ((d-i)%n == 0) return true;  // 如果 d-i 可以被 n 整除，能走到 d
    }
    return false;  // 如果能跑完 for 迴圈，走不到 d
}

int main() {
    int m, n, d;  // 可跳距離 m、n，目標距離 d
    while(scanf("%d %d %d", &m, &n, &d) != EOF) {
        if (solve(m, n, d)) printf("YES\n");  // 印出答案
        else printf("NO\n");
    }
    return 0;
}

ZeroJudge 解題筆記：g497. 電梯 (Elevator)

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



ZeroJudge 題目連結：g497. 電梯 (Elevator)

解題想法

注意：電梯一開始在 1 樓。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 升降次數
    arr = [1] + list(map(int, input().split()))  # 停留的樓層，開頭加上 1
    tot = 0  # 耗電量
    for i in range(n):  # 依序掃過 0 ~ n-1
        d = arr[i+1] - arr[i]  # 樓層變化
        if d > 0: tot += 3*d  # 上升一層耗 3 度電
        else: tot -= 2*d  # 下降一層耗 2 度電
    print(tot)  # 印出答案

C++ 程式碼

使用時間約為 2 ms，記憶體約為 96 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n;  // 升降次數
    while(scanf("%d", &n) != EOF) {
        int pre = 1, now, tot = 0;  // 原來的樓層，預設值為 1；現在的樓層；耗電量
        for(int i=0; i<n; i++) {  // 執行 n 次
            scanf("%d", &now);  // 讀取現在的樓層
            int d = now - pre;  // 樓層變化
            if (d > 0) tot += 3*d;  // 上升一層耗 3 度電
            else tot -= 2*d;  // 下降一層耗 2 度電
            pre = now;  // 更新 pre
        }
        printf("%d\n", tot);  // 印出答案
    }
    return 0;
}

ZeroJudge 解題筆記：g496. 彗星列車 (Comet)

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



ZeroJudge 題目連結：g496. 彗星列車 (Comet)

解題想法

注意：這題每組測資有多筆測試資料，而且每筆測試資料之間似乎有空行，如果用 Python 解題要忽略空行，否則會出錯。

Python 程式碼

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

import sys

for line in sys.stdin:
    if len(line.strip()) == 0: continue  # 忽略空行
    a, s = map(int, line.split())
    if s%a == 0: print(s//a)
    else: print(s//a + 1)

C++ 程式碼

用 cmath 函式庫的 ceil，先計算 s/a 的值再取 ceil，計算時及回傳值是浮點數，要再轉回整數，但是這樣無法通過第8筆測資。

#include <cstdio>
#include <cmath>  // for ceil
using namespace std;

int main() {
    int a, s;
    while(scanf("%d %d", &a, &s) != EOF) {
        printf("%d\n", int(ceil((float)s/(float)a)));
    }
    return 0;
}

還是回來用標準寫法，使用時間約為 6 ms，記憶體約為 96 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int a, s;
    while(scanf("%d %d", &a, &s) != EOF) {
        if (s%a == 0) printf("%d\n", s/a);
        else printf("%d\n", s/a + 1);
    }
    return 0;
}

ZeroJudge 解題筆記：g006. 密碼備忘錄 (Password)

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



ZeroJudge 題目連結：g006. 密碼備忘錄 (Password)

解題想法

這題我用字典計數，再用 cmp_to_key 或 lambda function 自訂比較式。

Python 程式碼

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

import sys
from collections import Counter
from functools import cmp_to_key

def mycmp(a, b):  # (key, val)
    if a[1] > b[1]: return -1  # 如果 a[1] > b[1]，a 往前放
    elif a[1] < b[1]: return 1  # 如果 a[1] < b[1]，a 往後放
    else:  # 如果 a[1] == b[1]
        if a[0] < b[0]: return -1  # 如果 a[0] < b[0]，a 往前放
        elif a[0] > b[0]: return 1  # 如果 a[0] > b[0]，a 往後放
        else: return 0

for s in sys.stdin:
    cnt = Counter(s.strip())  # 刪除 s 結尾的 \n，用 Counter 計算各字母數量
    ans = sorted([(k, v) for k, v in cnt.items()], key=cmp_to_key(mycmp))  # 排序
    print("".join([k for k, v in ans]))  # 將 k 取出組成字串再印出

ZeroJudge 解題筆記：g005. 倒置文章 (Inversion)

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



ZeroJudge 題目連結：g005. 倒置文章 (Inversion)

解題想法

這題考字串處理，從頭開始依序讀取字串的內容，先暫存內容到另一個字串，如果讀到 + 或 - 再結算之前暫存的內容，儲存到最後要輸出的字串之中。

Python 程式碼

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

import sys

for s in sys.stdin:
    s = s.strip()  # 刪除讀到的字串結尾的 \n
    rev = False  # 是否反轉，預設為否
    a, t = "", ""  # a 儲存答案，t 儲存反轉字串
    for c in s:  # 依序由 s 讀取字元 c
        if c == '+':  # 如果 c 是 +
            a += t; t = ""  # 結算之前儲存的 t，將 t 接到 a 之後再清空 t
            rev = False  # 順向
        elif c == '-':  # 如果 c 是 -
            a += t; t = ""  # 結算之前儲存的 t，將 t 接到 a 之後再清空 t
            rev = True  # 反向
        else:  # 如果 c 是其它字元
            if rev: t = c+t  # 如果目前是反向，將 c 接到 t 之前
            else: a += c  # 如果目前是順向，將 c 接到 a 之後
    a += t  # 最後再結算一次 t
    print(a)  # 印出答案

ZeroJudge 解題筆記：g004. 社區熱門度 (Popularity)

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



ZeroJudge 題目連結：g004. 社區熱門度 (Popularity)

解題想法

處理這種類型的題目時，我習慣在周圍或是最後面多加一些資料，可以避免在四方位檢查時出界。

Python 程式碼

可以先將答案存入另一個二維串列，使用時間約為 19 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    m, n = map(int, line.split())  # 地圖 m*n
    grid = [list(map(int, input().split())) + [0] for _ in range(m)]  # 地圖資料，最後加上 0
    grid.append([0]*(n+1))  # 最後加上 n+1 個 0
    ans = [grid[r][:-1] for r in range(m)]  # 儲存答案用的二維串列
    for r in range(m):  # 依序掃過每一格
        for c in range(n):
            if grid[r][c] != 0: continue  # 如果 (r, c) 這個不等於 0，找下一格
            cnt, tot = 0, 0  # 右下左上 4 格非 0 的格子數量，熱門度加總
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 檢查周圍 4 格
                v = grid[r+dr][c+dc]
                if v != 0:
                    cnt += 1; tot += v
            if tot != 0: ans[r][c] = tot//cnt  # 如果 tot 不等於 0，更新 ans[r][c]
    for row in ans: print(*row)  # 印出答案