ZeroJudge 解題筆記：d192. 11351 - Last Man Standing

作者：王一哲
日期：2026年4月30日


ZeroJudge 題目連結：d192. 11351 - Last Man Standing

解題想法

輸入的測資範圍應該是 $0 < n \leq 10^5$ 及 $0 < k < 10^9$，如果模擬整個淘汰的過程會超時。 從最後的贏家逆推𠩤來的編號。

1. 為了方便運算，成員的編號由0開始，最後輸出結果時再加1。
2. 先假設幸運者的編號 $idx_{0} = 0$，最後剩下 1 個人。
3. 第 $n-1$ 次（最後1次）運作時，參與的人數為 $2$，幸運者原來的編號為 $idx_{n-2} = k \% 2$。
4. 第 $n-2$ 次（倒數第2次）運作時，參與的人數為 $3$，幸運者原來的編號為 $idx_{n-3} = (idx_{n-2} + k) \% 3$。
5. 第 $n-3$ 次（倒數第3次）運作時，參與的人數為 $4$，幸運者原來的編號為 $idx_{n-4} = (idx_{n-3} + k) \% 4$。
6. 若 $i = 1、2、\dots、n$，則第 $n-i$ 次（倒數第 $i$ 次）運作時，參與的人數為 $1 + i$，幸運者原來的編號為 $idx_{i} = (idx_{i-1} + k) \% (1+ i)$。
7. 輸出幸運者的編號，由於題目的編號從 $1$ 開始，需要將 $idx$ 加 $1$。

Python 程式碼

模擬過程，超時。

t = int(input())
for i in range(1, t+1):
    n, k = map(int, input().split())
    arr = list(range(1, n+1))  # 目前還存活的人
    idx = 0  # 從 1 號、索引值 0 開始
    while n > 1:  # 人數大於 1 繼續執行
        idx = (idx+k-1) % n  # 更新淘汰者的索引值
        del arr[idx]  # 移除 arr[idx]
        n -= 1  # 人數減 1
        idx %= n  # 更新 idx，有可能歸零
    print(f"Case {i:d}: {arr[0]:d}")  # 印出答案

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

t = int(input())
for i in range(1, t+1):
    n, k = map(int, input().split())
    idx = 0  # 最後剩下的人，索引值 0
    for j in range(1, n):  # 1 到 n-1
        idx = (idx + k) % (1+j)
    print(f"Case {i:d}: {idx+1:d}")  # 印出答案

C++ 程式碼

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

#include <cstdio>

int main() {
    int t; scanf("%d", &t);
    for(int i=1; i<=t; i++) {
        int n, k; scanf("%d %d", &n, &k);
        int idx = 0;  // 最後剩下的人，索引值 0
        for(int j=1; j<n; j++) {  // 1 到 n-1
            idx = (idx + k) % (1+j);
        }
        printf("Case %d: %d\n", i, idx+1);  // 印出答案
    }
    return 0;
}