# APCS 2025 年 1 月 AA 競程 dreamoon 老師的參考作法


:::success
以下題目的講解都已假設大家已擁有 AA 競程 Level 0 所介紹過的所有語法知識，而 Level 0 的教學內容可參考以下兩個網頁提到的課程大綱：
1. [AA 競程 Level 0 語法班](https://aacpschool.com/2024-3-base2/)
2. [AA 競程 Level 0 競程入門班](https://aacpschool.com/2024-4-start/)
:::

## P1. [等紅綠燈](https://zerojudge.tw/ShowProblem?problemid=q181)

紅綠燈變換的週期為 $a+b$ 秒，若一個小朋友騎完一圈的時間剛好是落在某個週期的後 $b$ 秒，就得等到該週期結束，所以此題的重點就是算出每位小朋友騎完一圈時，是在紅綠燈一個週期裡的第幾秒，這和 C++ 裡的取餘運算子有關。把騎一圈的時間對 $a + b$ 取餘後的值(令其為 $x$)，若小於 $a$ 就代表不用等紅綠燈，也就是等待時間為 $0$，否則就要等到這個週期結束，也就是要等 $a+b-x$ 秒。

若真的有作答者對取餘運算不熟，使用 ``while(x >= a + b) x -= a + b;`` 的寫法來求餘數也是能通過此題。(但不建議這樣寫)

以下為參考程式碼：

#include<iostream>
#include<vector>
#include<algorithm>
#define SZ(X) ((int)(X).size())
using namespace std;
int need(int x, int a, int b) {
    x %= a + b;
    /* 這個部分寫成：
     * while(x >= a + b) x -= a + b;
     * 也能通過
     */
    if(x >= a) return b + a - x;
    return 0;
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    int n;
    cin >> n;
    int ans = 0;
    while(n--) {
        int x;
        cin >> x;
        ans += need(x, a, b);
    }
    cout << ans << '\n';
}

## P2. [字串操作](https://zerojudge.tw/ShowProblem?problemid=q182)

此題放在歷屆似乎會是個特別簡單的 P2，以前的 P2 要不是在二維陣列裡，要碼單個操作也要用到雙層以上的迴圈，但此題每個操作都可用一個迴圈就可以完成...請大家直接看參考程式碼吧！

#include<iostream>
#include<string>
#include<algorithm>
#define SZ(X) ((int)(X).size())
using namespace std;
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    string s;
    int k;
    cin >> s >> k;
    while(k--) {
        int ty;
        cin >> ty;
        if(ty == 0) {
            for(int i = 0; i < SZ(s); i += 2) swap(s[i], s[i + 1]);
        } else if(ty == 1) {
            for(int i = 0; i < SZ(s); i += 2) {
                sort(s.begin() + i, s.begin() + i + 2);
            }
        } else {
            string tmp;
            for(int i = 0; i < SZ(s) / 2; i++) {
                tmp += s[i];
                tmp += s[i + SZ(s) / 2];
            }
            s = tmp;
        }
    }
    cout << s << '\n';
}

## P3. [重組問題](https://zerojudge.tw/ShowProblem?problemid=q183)

:::info
在此題我們直接把「差的絕對值」簡稱為「差值」。
:::

這大概是歷屆裡最難的 P3 了(甚至比 P4 還難)，而且這是個有名字的問題，叫做：Turnpike Reconstruction Problem，也有論文在討論這個問題如：[ON THE TURNPIKE PROBLEM](https://sandbox.dodona.be/en/activities/1441444585/description/sKfgfbq-Wnx-ufBY/media/Dakic2000.pdf)，目前尚未有多項式時間的作法能解此題。(避免有人誤會以為此題難度趨近於不能做，補充說明一下：很多 30 幾年前的論文在對於現在的競賽選手來說都是能夠在短時間內解出來的題目，而且解出此題的方法也只是論文裡在討論的事情的小小一部分。這裡的難是指對於 APCS 來說很難，若是在一般演算法競賽，只能說並不是個簡單題，但難度也還好。)

但其實看題目給的 $n$ 最大只有 $25$，就可以猜此題並不是個能在多項式時間內解決的題目，不過在近 5 年來的 APCS 沒考過這樣的題目，所以有非常多人為了寫出一個多項式時間複雜度的方法，就使用了錯誤的貪心演算法，實在是非常可惜。

雖然上面把這題描述得非常難，但實際上，此題只需要使用 AA 競程 Level 1 (2024 暑期以前的 Level 1)教過的知識即可解出。只需使用到遞迴枚舉的技巧(此技巧在網路上的許多教材是稱它為「回溯法」)。

困難的地方在於到底要枚舉什麼以及用什麼順序枚舉。

先列一些能幫助我們解出此題的觀察：

:::success
(1) $a_n$ 的值就是輸入給定的「差值」中最大的那個
:::

有了 (1) 的觀察後，我們至少確定了頭尾兩個數，還剩下至多 23 個數不確定。

接著還剩下一個最重要的觀察：

:::success
(2) 若 $a_1, a_2, \ldots, a_{L-1}$ 的值與 $a_{R+1}, a_{R + 2}, \ldots, a_n$ 的值都知道，並把這 $L - 1 + (n - R)$ 個數字倆倆的「差值」從輸入給定的「差值」移除後，令沒被移除的數中最大的值為 $v$，那麼以下兩件事至少有一件事是成立的：
1. $a_L = a_n - v$
2. $a_R = v$

舉例來說，在第二個範例測試資料裡，輸入為：

5
1 2 3 3 5 5 6 8 10 11

若我們已經知道 $a_1 = 0, a_2 = 1, a_3 = 11$，那麼我們可以把 $a_2 - a_1 = 1, a_3 - a_1 = 11, a_3 - a_2 = 10$ 從輸入的「差值」移除，剩下的 $7$ 個數為：$2, 3, 3, 5, 5, 6, 8$，其中最大的數字是 $8$，那麼 $a_3 = 11 - 8 = 3$ 和 $a_4 = 8$ 中至少有一個成立。
:::

有了第二個觀察後，就可以發現若使用遞迴枚舉，根據「差值」中還沒用到的數裡的最大的值，就可以嘗試決定出最左邊尚未確定值的數或是最右邊尚未決定值的數，就算不使用「減枝」的技巧至多也只會枚舉到 $2^{23}$ 種情形，而根據你的細節的實作方式，最終的時間複雜度可能會是 $O(2^n \times C)$ ($C$ 是輸入中最大的數字，此也是最下方的範例程式碼的寫法)，或是使用 STL 容器裡的 set 可做到 $O(2^n \times n \log{n})$。

:::danger
另外補充一下，有非常多參加檢定的同學沒想清楚就使用了一些貪心思維的假解，那很可能會答錯以下測試資料：

Input:
4
1 2 2 3 3 5
Output:
0 2 3 5
0 2 3 5

以及有些人會以為至多只有 2 組數列 $a$ 能產生相同的「差值」多重集，但這是錯的，以下是最小的反例：

0 1 2 6 8 11 
0 1 6 7 9 11 
0 2 4 5 10 11 
0 3 5 9 10 11 

:::

:::info
再補充一個數學證明比較困難的觀察：

**字典序最大的解的差分數列會是字典序最小的解的差分數列的 reverse**

舉例來說：

範例測試資料二字典序最小的答案是：

0 1 3 6 11

它的差分數列(也就是相鄰兩項相減的結果)是：

1 2 3 5

把此差分數列 revese 後變成：

5 3 2 1

最後可根據此數列直接產生字典序最大的解：

0 5 8 10 11

有了這個觀察後，就能在找到第一組解時，直接輸出答案結束程式，如此一來幾乎找不到能讓程式碼執行時間達到 worst case 的測試資料。

這件事情似乎很多作答者都是直接猜測它是正確的，但應該要好好證明。若總是憑直覺猜測的話，總是會遇到吃虧的時候。

但這件事的證明並不簡單，筆者其實也沒能想出來，最後感謝皮皮大大在 APCS 模擬測驗團隊 discord 群提出一個 [證明方法](https://discord.com/channels/1193355290712748182/1193355291199291494/1325619663345811506)，我在這裡再把它重寫一次：

以下會使用反證法證明。

令 $d_1, d_2, \ldots, d_{n-1}$ 是字典序最小的解的差分數列。
假設存在另一個解的差分數列 $c_1, c_2, \ldots, c_{n-1}$ reverse 後的字典序比 $d$ reverse 還大，那麼必定有以下兩件事實：

1. 令 $x$ 是最小的滿足 $c_x \ne d_x$ 的正整數，那麼必有 $c_x > d_x$。
這是因為 $d$ 是字典序最小的解的差分數列，而這是字典序最小的定義。
2. 令 y 是最大的滿足 $c_y \ne d_y$ 的正整數，那麽必有 $c_y > d_y$。
這是因為 $c$ 的 reverse 字典序比 $d$ 的 reverse 還大。

定義 $DIF(d, i, j) = \sum\limits_{k=i}^j d_k$ 代表差分數列 $d$ 中，第 $i$ 項加至第 $j$ 項所構成的「差值」。

若 $i \le x$ 且 $j \ge y$，那麼 $DIF(d, i, j) = DIF(c, i , j)$，這是因為 $c$ 和 $d$ 的數字和是一樣的。

因為 $c$ 和 $d$ 都是解的差分數列，所以 $c$ 和 $d$ 兩個差分數列所構成的「差值」多重集應該要相同，而兩多重集相同的話必須能夠把兩個即合理的數字一一對應。

那我們可以先把所有 $i \le x$ 且 $j \ge y$ 的「差值」 $DIF(d, i, j)$ 對應到 $DIF(c, i, j)$，但這些「差值」對應完後，$c$ 裡剩下的還沒對應到的「差值」中，最大的數一定是 $DIF(c, 1, y - 1)$ 或 $DIF(c, x + 1, n - 1)$ 兩者之一，對於 $d$ 來說也一樣，還沒對應到的「差值」中最大的一定是 $DIF(d, 1, y - 1)$ 或 $DIF(d, x + 1, n - 1)$。

但事實 1 可推得 $DIF(c, x + 1, n - 1) < DIF(d, y + 1, n - 1)$，而事實 2 可推得 事實 2 可推得 $DIF(c, 1, y - 1) < DIF(d, 1, y - 1)$。

所以兩個差分數列還沒對應到的差值中最大的數字不可能一樣，所以一定無法一一對應，產生矛盾，所以最初的假設：
「存在另一個解的差分數列 $c_1, c_2, \ldots, c_{n-1}$ reverse 後的字典序比 $d$ reverse 還大」
是錯的。

:::

最後附上參考程式碼：

/* 此程式碼時間複雜度為 $O(C * 2^(n-2)) (C 是輸入中最大的數字)，但目前找不到能跑滿的測試資料*/
#include<iostream>
#include<vector>
#include<algorithm>
#define SZ(X) ((int)(X).size())
using namespace std;
const int MAX_V = 100;
int cnt[MAX_V + 1];
vector<int> mi, ma, now;
int n;
// 暴力找到還沒被用過的差值的最大值
int find_max() {
    for(int i = MAX_V; i >= 0; i--) {
        if(cnt[i]) return i;
    }
    return -1;
}
bool check(int v, int left_pos, int right_pos) {
    bool good = 1;
    for(int i = 0; i < left_pos; i++) {
        if(--cnt[abs(now[i] - v)] < 0) good = 0;
    }
    for(int i = right_pos + 1; i < n; i++) {
        if(--cnt[abs(now[i] - v)] < 0) good = 0;
    }
    return good;
}
void rollback(int v, int left_pos, int right_pos) {
    for(int i = 0; i < left_pos; i++) {
        ++cnt[abs(now[i] - v)];
    }
    for(int i = right_pos + 1; i < n; i++) {
        ++cnt[abs(now[i] - v)];
    }
}
// 遞迴枚舉整個數列，呼叫此遞迴函式時代表位置 left_pos 至 right_pos 的數字還沒決定
void dfs(int left_pos, int right_pos) {
    if(left_pos > right_pos) {
        mi = min(mi, now);
        ma = max(ma, now);
        return;
    }
    // 找到目前還沒用到的差的絕對值的最大值 ma_len，此值只可能是最大的數減去位置 left_pos 的數
    // 或是位置 right_pos 的數減去位置 0 的數
    int ma_len = find_max();
    
    // 先嘗試 ma_len 是最大的數減去位置 left_pos 的數的情況
    // 如此一來第一個找到的一定是字典序最小的解
    now[left_pos] = now[n - 1] - ma_len;
    if(check(now[left_pos], left_pos, right_pos)) dfs(left_pos + 1, right_pos);
    rollback(now[left_pos], left_pos, right_pos);
    
    // 再嘗試 ma_len 是位置 right_pos 的數減去位置 0 的數
    now[right_pos] = ma_len;
    if(check(now[right_pos], left_pos, right_pos)) dfs(left_pos, right_pos - 1);
    rollback(now[right_pos], left_pos, right_pos);
    
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> n;
    if(n == 1) {
        cout << "0\n0\n";
        return 0;
    }
    // 用 cnt[x] 記錄還有多少兩數的差值為 x 還沒被確認
    for(int i = 0; i < n * (n - 1) / 2; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    mi.assign(n, MAX_V);
    ma.assign(n, 0);
    now.assign(n, 0);
    
    // 最大的數一定是兩數差值中的最大值
    now[n - 1] = find_max();
    cnt[now[n - 1]]--;
    
    // 遞迴枚舉位置 1 至 n-2 的數的所有可能情形
    dfs(1, n - 2);
    
    for(int i = 0; i < n; i++) cout << mi[i] << (i + 1 < n ? ' ' : '\n');
    for(int i = 0; i < n; i++) cout << ma[i] << (i + 1 < n ? ' ' : '\n');
}

## P4. [分組開會](https://zerojudge.tw/ShowProblem?problemid=q184)

這次的 P4 老師認為是比較簡單的，前提是你練習時有做過以下知識(在 AA 競程課程的 Level 1 裡都曾介紹過)：

1. [CSES1074 Stick Lengths](https://cses.fi/problemset/task/1074)
2. [APCS325 P_4_12 一次買賣](https://judge.tcirc.tw/problem/d051)
3. 快速區間求和 ([CSES1646 Static Range Sum Queries](https://cses.fi/problemset/task/1646))
4. 貪心的概念

首先你要有貪心的概念，觀察到把所有人的座標排序後(後面都假設 $x_1, x_2, \ldots, x_n$ 已從小到大排序)，我們選的兩個組別一定都是連續 $k$ 個座標的一些人，若不這樣選，一定不會比較好，於是需要考慮的情形已經只剩下 $O(n^2)$。

接著，你要發現，若我們想計算$x_i, x_{i+1}, \ldots, x_{i+k-1}$ 這幾個人要聚集在哪最好，那一定是選它們的中位數，也就是 $x_{i+\lfloor\frac{k+1}{2}\rfloor - 1}$。接著，令 $half\_k = \lfloor\frac{k}{2}\rfloor$，我們會發現這 $k$ 個人到他們中位數位置集合的總距離就會是 $(x_{i+k-half\_k+1} + \ldots + x_{i+k-1}) - (x_i + \ldots, x_{half\_k - 1})$ 所以預處理數列 $x$ 的前綴和後，對於任意 $i$ 都可以 $O(1)$ 第 $i$ 個人到第 $i+k-1$ 個人聚集所需時間總和。

最後，類似於 [APCS325 P_4_12 一次買賣](https://judge.tcirc.tw/problem/d051) 的解法，不妨假設第一組的人的編號是 $i-k+1 \sim i$，第二組的人的編號是 $j+1 \sim j+k$，那麼我們只要由小到大枚舉 $j$，並找到小於等於 $j$ 的所有 $i$ 對應的分組方式中，哪個聚集所需時間最小，這樣就可以把整道題以 $O(n)$ 的時間計算了。

參考程式碼如下：

#include<iostream>
#include<vector>
#include<algorithm>
#define SZ(X) ((int)(X).size())
using namespace std;
using LL = long long;
const LL INF = 4e18;
vector<LL> prefix_sum;
LL get_sum(int low, int hi) {
    return prefix_sum[hi] - prefix_sum[low - 1];
};
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n, k;
    cin >> n >> k;
    
    vector<LL> x(n);
    for(LL &v: x) cin >> v;
    sort(x.begin(), x.end());
    
    prefix_sum.assign(n + 1, 0);
    for(int i = 0; i < n; i++) prefix_sum[i + 1] = prefix_sum[i] + x[i];
    
    int half_k = k / 2;
    LL ans = INF;
    LL now_min = INF;
    for(int i = k; i + k <= n; i++) {
        now_min = min(now_min, get_sum(i - half_k + 1, i) - get_sum(i - k + 1, i - k + half_k));
        ans = min(ans, now_min + get_sum(i + k - half_k + 1, i + k) - get_sum(i + 1, i + half_k));
    }
    
    cout << ans << '\n';
}