Editorial for 贏家預測 (APCS 2022-01 中級)

簡潔題意

\(n\) 位選手排成一列，每輪由前往後兩兩比賽：前面的選手（戰力 \(a\)、應變力 \(b\)）對上後面的選手（戰力 \(c\)、應變力 \(d\)），\(ab \ge cd\) 時前面的獲勝（乘積相同算前面的贏），比賽後四項能力依題目公式更新，公式裡用的都是比賽前的數值、除法一律無條件捨去。該輪人數是奇數時，最後一人輪空直接晉級、能力不變。下一輪的隊列＝依序放入全部勝者（輪空者接在勝者最後），再依序放入還沒累積到 \(m\) 敗的敗者；累積第 \(m\) 敗立刻淘汰。模擬到只剩一人，輸出他的編號（\(2 \le n \le 1000\)、\(1 \le m \le 5\)、\(1 \le S_i, T_i \le 100\)，過程中任兩項能力相乘保證不超過 \(2^{60}\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(50\) 分）：\(n \le 100\) 且 \(m = 1\)。
  • 子題組 2（\(50\) 分）：無額外限制。

動手模擬前，先做對三個決定

這題沒有演算法，就是照題目一輪一輪模擬；寫不寫得順，取決於動手前的三個決定。

能力跟著編號走，不跟著隊列位置走。隊列每輪都會重排，把能力綁在「隊列的第幾個」上，等於每輪都要搬家。正確做法：s[id]、t[id]、losses[id] 用選手編號當索引——題目編號 \(1\) 到 \(n\)，就多開一格從 \(1\) 用起（6.3）；隊列 order 是一個只放編號的 vector（10.2）。

四個新值全部用舊值算。題目特別粗體強調：公式裡的 \(a, b, c, d\) 都是比賽開始前的數值。這跟 13.7 的「讀舊表、寫新表」是同一個原則，只是規模從一張表縮成四個變數：每場比賽先把四個舊值抄出來，再一口氣算四個新值。邊算邊改的話，第二條公式的分母裡已經是改過的新戰力，整數除法差一點點，勝負就從此走岔——而且兩個範例都抓不到這種錯（見自測表）。

下一輪＝先放完全部勝者，再放全部敗者。不是每組比完就讓勝者、敗者手牽手進下一輪。每輪開兩個 vector：winners 收勝者（輪空者接在最後）、losers 收還沒滿 \(m\) 敗的敗者，輪末把兩串接起來當新隊列。

先拿下子題組 1（50 分）：\(m = 1\)，輸一場就回家

\(m = 1\) 時敗者一輸就淘汰——不用記失敗次數、也不用敗者隊列，每輪只收 winners：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;                          // 子題組 1 保證 m 一定是 1
    vector<long long> s(n + 1), t(n + 1);   // 能力用「編號」當索引（1 ～ n）
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    vector<int> order(n);                   // 隊列裡只放選手編號
    for (int i = 0; i < n; i++) {
        cin >> order[i];
    }

    while (order.size() > 1) {
        vector<int> winners;
        for (int i = 0; i + 1 < (int)order.size(); i += 2) {
            int x = order[i], y = order[i + 1];
            long long a = s[x], b = t[x], c = s[y], d = t[y];   // 先抄下比賽前的四個舊值
            if (a * b >= c * d) {           // 平手時，前面的選手獲勝
                winners.push_back(x);
                s[x] = a + c * d / (2 * b);
                t[x] = b + c * d / (2 * a);
            } else {
                winners.push_back(y);
                s[y] = c + a * b / (2 * d);
                t[y] = d + a * b / (2 * c);
            }
        }
        if (order.size() % 2 == 1) {        // 輪空：直接晉級，能力不變
            winners.push_back(order.back());
        }
        order = winners;                    // m = 1：敗者輸一場就淘汰，不用留
    }
    cout << order[0] << endl;
}

(int)order.size() 的轉型是 10.4 的無號整數陷阱——size() 是無號的，先轉回 int 再比較最安心。

這份程式範例 1（\(m = 1\)）本來就該過；連範例 2（\(m = 5\)）也剛好過——那只是這筆測資恰巧選出同一位冠軍，別因此以為它已經是滿分解。逐筆給分之下，子題組 1 的 \(50\) 分穩穩到手。

從 50 分到 100 分：補上失敗次數與敗者隊列

跟子題組版比只差三件事：每場比賽的敗者 losses[loser]++、還沒滿 \(m\) 敗才加進 losers、輪末 winners 接上 losers 當新隊列。另外敗者這回不會馬上消失，他的能力也要照公式更新。

型態要用 long long（2.3）：初始能力最多 \(100\) 看起來很安全，但能力每場都在漲，題目明說乘積可能超過 \(2^{32}\)、保證不超過 \(2^{60}\)——int 的上限約 \(21\) 億早就爆了，long long（上限約 \(9.2 \times 10^{18}\)）才裝得下。至於題目的 \(\lfloor \, \rfloor\)：全程都是正整數，C++ 的整數除法本來就是無條件捨去，直接除即可。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> s(n + 1), t(n + 1);   // 能力用「編號」當索引（1 ～ n）
    vector<int> losses(n + 1, 0);           // 每位選手目前累積的失敗次數
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    vector<int> order(n);                   // 隊列裡只放選手編號
    for (int i = 0; i < n; i++) {
        cin >> order[i];
    }

    while (order.size() > 1) {
        vector<int> winners, losers;
        for (int i = 0; i + 1 < (int)order.size(); i += 2) {
            int x = order[i], y = order[i + 1];
            long long a = s[x], b = t[x], c = s[y], d = t[y];   // 先抄下比賽前的四個舊值
            int loser;
            if (a * b >= c * d) {           // 平手時，前面的選手獲勝
                winners.push_back(x);
                loser = y;
                s[x] = a + c * d / (2 * b);
                t[x] = b + c * d / (2 * a);
                s[y] = c + c / 2;
                t[y] = d + d / 2;
            } else {
                winners.push_back(y);
                loser = x;
                s[x] = a + a / 2;
                t[x] = b + b / 2;
                s[y] = c + a * b / (2 * d);
                t[y] = d + a * b / (2 * c);
            }
            losses[loser]++;
            if (losses[loser] < m) {        // 這是第 m 敗＝立刻淘汰，不進下一輪
                losers.push_back(loser);
            }
        }
        if (order.size() % 2 == 1) {        // 輪空：放在勝者隊列最後，能力不變
            winners.push_back(order.back());
        }
        for (int id : losers) {             // 先放完全部勝者，再放全部還活著的敗者
            winners.push_back(id);
        }
        order = winners;
    }
    cout << order[0] << endl;
}

for (int id : losers) 是 12.4 的範圍 for；order = winners 整條 vector 直接指派是 10.6。速度不用擔心：每場比賽恰好讓一個人多一敗，每人淘汰前最多輸 \(m\) 次，所以總比賽場數不到 \(nm \le 5000\) 場。

測過再交：範例放行了五種錯裡的四種

範例 2 其實不差——模擬途中隊列多次變成奇數人（輪空真的有發生），「平手讓後面的贏」它也抓得到。但實測下面這幾種常見錯法，兩個範例全部照樣通過：邊算邊改、勝者敗者交錯排、太晚淘汰、輪空者放錯位置。缺口自己補：

輸入 正確輸出 這一筆在測什麼
2 1／2 3／3 2／1 2 1 平手：\(2 \times 3 = 3 \times 2\)，前面的選手獲勝。寫成 > 的程式印 2（最小重現；範例 2 也抓得到這種錯）
2 2／2 3／3 2／2 1 2 邊算邊改：第一場平手、\(2\) 號獲勝，若算應變力時分母用了剛更新的戰力，整數除法少 \(1\)、第二輪就反轉，這種程式印 1
3 2／4 2 2／1 3 2／1 3 2 1 勝者要先放完才輪到敗者：每組比完就「勝者、敗者」交錯放的程式印 3
3 2／2 1 1／2 6 2／1 2 3 2 輪空者接在「勝者」的最後：忘了把輪空者放回、或把他排到敗者後面的程式都印 1
2 1／1 2／4 2／1 2 1 第 \(m\) 敗「立刻」淘汰：寫成超過 \(m\) 敗才淘汰的程式讓 \(2\) 號多活了幾輪、反過來獲勝，印 2

五筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 全部用 int：能力每場都在漲，乘積會衝破 \(2^{32}\)。兩個範例的乘積最大只到 \(860\)、照樣全過，本站 \(20\) 筆計分測資會掉 \(4\) 筆——自測表也堵不了它（小測資養不出大乘積），型態宣告自己看一眼。
  • 邊算邊改（沒先抄舊值）：例如算 t[x] 時分母用了剛更新完的 s[x]。兩個範例全過；自測表第 2 列印 1。
  • 每組比完就把勝者、敗者依序放回：正確順序是先放完全部勝者、再放全部敗者。兩個範例全過；自測表第 3 列印 3。
  • 輪空者忘了放回，或放到敗者後面：輪空者接在勝者隊列的最後、能力完全不變。兩種寫法兩個範例都全過；自測表第 4 列都印 1。
  • 累積超過 \(m\) 敗才淘汰：第 \(m\) 敗當場淘汰，不進下一輪。兩個範例全過；自測表第 5 列印 2。
  • 平手讓後面的選手獲勝：\(ab \ge cd\) 是前面的贏，等號歸前面。範例 2 抓到（印 4）；自測表第 1 列印 2。