# APCS實作題2025年11月高級第1題：字母配對

> 第1版：2025年11月17日
> 第2版：2025年11月24日，更正標題，這題是 APCS **高級**實作題，不是中高級，我之前弄錯了。
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=r626)

<br />

## 解題想法

我一開如是用優先佇列儲存資料，內容為 **分數, 從每個堆疊讀取資料的索引值**，分數最高的資料放在最上面。由於 Python 的 heapq 是最小優先佇列，所以要把分數改成負值，儲存索引值的部分要用 tuple，並用一個 set 儲存已經測試過的狀態，避免重複計算同樣的狀態才不會超時。

後來又想到，這個題目要測試所有的移除方式找最高分，並不需要從當時的最高分組合往下找，可以用 BFS 就好。測試之後發現，這個寫法跟前一種寫法效率差不多。
<br /><br />

## Python 程式碼

heapq，使用時間約為 0.2 s，記憶體約為 8.3 MB，通過測試。

import heapq

m = int(input())  # m 個堆疊
piles = [[] for _ in range(m)]  # 堆疊, (字母, 分數)
for i in range(m):  # 讀取 m 行
    parts = input().split()
    n = int(parts[0])  # n 個物品
    for j in range(1, 2*n+1, 2):
        piles[i].append((parts[j], int(parts[j+1])))

initial_state = tuple([0]*m)  # 初始狀態，要用 tuple
visited = {initial_state}  # 已經檢查過的狀態
pq = [(0, initial_state)]  # 優先佇列，(分數負值, 從每個堆疊讀取資料的索引值)
imax = 0  # 最高分數
while pq:  # 如果 pq 有資料繼續執行
    score, heads = heapq.heappop(pq)  # 取出 pq 最上面的項目
    score = -score  # 分數換回正值
    imax = max(imax, score)  # 更新最高分數
    for i in range(m-1):  # 掃過第 0 ~ m-2 堆
        if heads[i] >= len(piles[i]): continue  # 已出界，找下一個
        a = piles[i][heads[i]]  # 物品 a
        for j in range(i+1, m):  # 掃過第 i+1 ~ m-1 堆
            if heads[j] >= len(piles[j]): continue  # 已出界，找下一個
            b = piles[j][heads[j]]  # 物品 b
            if a[0] == b[0]:  # 同字母
                new_score = score + a[1] + b[1]  # 新的分數
                new_heads_list = list(heads)  # 複製索引值
                new_heads_list[i] += 1  # i 的索引值加 1
                new_heads_list[j] += 1  # j 的索引值加 1
                new_heads = tuple(new_heads_list)  # 轉成 tuple
                if new_heads not in visited:  # 如果 new_heads 未走訪
                    visited.add(new_heads)  # new_heads 加入 visited
                    heapq.heappush(pq, (-new_score, new_heads))  # 加入 pq
print(imax)

<br />

BFS，使用時間約為 0.2 s，記憶體約為 8.8 MB，通過測試。

from collections import deque

m = int(input())  # m 個堆疊
piles = [[] for _ in range(m)]  # 堆疊, (字母, 分數)
for i in range(m):  # 讀取 m 行
    parts = input().split()
    n = int(parts[0])  # n 個物品
    for j in range(1, 2*n+1, 2):
        piles[i].append((parts[j], int(parts[j+1])))

initial_state = tuple([0]*m)  # 初始狀態，要用 tuple
visited = {initial_state}  # 已經檢查過的狀態
que = deque([(0, initial_state)])  # 佇列，(分數, 從每個堆疊讀取資料的索引值)
imax = 0  # 最高分數
while que:  # 如果 que 有資料繼續執行
    score, heads = que.popleft()  # 取出 que 最前面的項目
    imax = max(imax, score)  # 更新最高分數
    for i in range(m-1):  # 掃過第 0 ~ m-2 堆
        if heads[i] >= len(piles[i]): continue  # 已出界，找下一個
        a = piles[i][heads[i]]  # 物品 a
        for j in range(i+1, m):  # 掃過第 i+1 ~ m-1 堆
            if heads[j] >= len(piles[j]): continue  # 已出界，找下一個
            b = piles[j][heads[j]]  # 物品 b
            if a[0] == b[0]:  # 同字母
                new_score = score + a[1] + b[1]  # 新的分數
                new_heads_list = list(heads)  # 複製索引值
                new_heads_list[i] += 1  # i 的索引值加 1
                new_heads_list[j] += 1  # j 的索引值加 1
                new_heads = tuple(new_heads_list)  # 轉成 tuple
                if new_heads not in visited:  # 如果 new_heads 未走訪
                    visited.add(new_heads)  # new_heads 加入 visited
                    que.append((new_score, new_heads))  # 加入 que
print(imax)

<br /><br />

## C++ 程式碼

priority_queue，使用時間約為 34 ms，記憶體約為 2.8 MB，通過測試。

#include <iostream>
#include <vector>
#include <queue>  // for priority_queue
#include <utility>  // for pair
#include <set>
#include <algorithm>  // for max
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m; cin >> m;  // m 個堆疊
    vector<vector<pair<char, int>>> piles (m);  // 堆疊, (字母, 分數)
    for(int i=0; i<m; i++) {  // 讀取 m 行
        int n; cin >> n;  // n 個物品
        for(int j=0; j<n; j++) {
            char name;
            int score;
            cin >> name >> score;
            piles[i].push_back(make_pair(name, score));
        }
    }
    vector<int> initial_state (m, 0);  // 初始狀態，要用 tuple
    set<vector<int>> visited;  // 已經檢查過的狀態
    visited.insert(initial_state);
    priority_queue<pair<int, vector<int>>> pq;  // 最大優先佇列，(分數, 從每個堆疊讀取資料的索引值)
    pq.push(make_pair(0, initial_state));
    int imax = 0;  // 最高分數
    while(!pq.empty()) {  // 如果 pq 有資料繼續執行
        int score = pq.top().first;  // 取出 pq 最上面的項目
        auto heads = pq.top().second;
        pq.pop();
        imax = max(imax, score);  // 更新最高分數
        for(int i=0; i<m-1; i++) {  // 掃過第 0 ~ m-2 堆
            if (heads[i] >= (int)piles[i].size()) continue;  // 已出界，找下一個
            auto a = piles[i][heads[i]];  // 物品 a
            for(int j=i+1; j<m; j++) {  // 掃過第 i+1 ~ m-1 堆
                if (heads[j] >= (int)piles[j].size()) continue;  // 已出界，找下一個
                auto b = piles[j][heads[j]];  // 物品 b
                if (a.first == b.first) {  // 同字母
                    int new_score = score + a.second + b.second;  // 新的分數
                    auto new_heads = heads;  // 複製索引值
                    new_heads[i]++;  // i 的索引值加 1
                    new_heads[j]++;  // j 的索引值加 1
                    if (visited.count(new_heads) == 0) {  // 如果 new_heads 未走訪
                        visited.insert(new_heads);  // new_heads 加入 visited
                        pq.push(make_pair(new_score, new_heads));  // 加入 pq
                    }
                }
            }
        }
    }
    cout << imax << "\n";
    return 0;
}

<br />

BFS，使用時間約為 37 ms，記憶體約為 2.9 MB，通過測試。

#include <iostream>
#include <vector>
#include <queue>
#include <utility>  // for pair
#include <set>
#include <algorithm>  // for max
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m; cin >> m;  // m 個堆疊
    vector<vector<pair<char, int>>> piles (m);  // 堆疊, (字母, 分數)
    for(int i=0; i<m; i++) {  // 讀取 m 行
        int n; cin >> n;  // n 個物品
        for(int j=0; j<n; j++) {
            char name;
            int score;
            cin >> name >> score;
            piles[i].push_back(make_pair(name, score));
        }
    }
    vector<int> initial_state (m, 0);  // 初始狀態，要用 tuple
    set<vector<int>> visited;  // 已經檢查過的狀態
    visited.insert(initial_state);
    queue<pair<int, vector<int>>> que;  // 待走訪佇列，(分數, 從每個堆疊讀取資料的索引值)
    que.push(make_pair(0, initial_state));
    int imax = 0;  // 最高分數
    while(!que.empty()) {  // 如果 que 有資料繼續執行
        int score = que.front().first;  // 取出 que 最前面的項目
        auto heads = que.front().second;
        que.pop();
        imax = max(imax, score);  // 更新最高分數
        for(int i=0; i<m-1; i++) {  // 掃過第 0 ~ m-2 堆
            if (heads[i] >= (int)piles[i].size()) continue;  // 已出界，找下一個
            auto a = piles[i][heads[i]];  // 物品 a
            for(int j=i+1; j<m; j++) {  // 掃過第 i+1 ~ m-1 堆
                if (heads[j] >= (int)piles[j].size()) continue;  // 已出界，找下一個
                auto b = piles[j][heads[j]];  // 物品 b
                if (a.first == b.first) {  // 同字母
                    int new_score = score + a.second + b.second;  // 新的分數
                    auto new_heads = heads;  // 複製索引值
                    new_heads[i]++;  // i 的索引值加 1
                    new_heads[j]++;  // j 的索引值加 1
                    if (visited.count(new_heads) == 0) {  // 如果 new_heads 未走訪
                        visited.insert(new_heads);  // new_heads 加入 visited
                        que.push(make_pair(new_score, new_heads));  // 加入 pq
                    }
                }
            }
        }
    }
    cout << imax << "\n";
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`C++`、`Python`