ACM 競賽題解：北京 2006 E 題 - 競賽排名可能性判斷

題目背景

來源：ACM Beijing 2006 Regional Contest - Problem E

一場有 3 道題、n 名選手（n ≤ 16384）的比賽，每位選手 ID 為 1~n。最終排名按總分降序，同分按 ID 升序。已知每位選手每道題若非完全錯誤可獲得的分數（含兩位小數），但不知道實際是否得分。給定一個預測排名序列，判斷其是否可能，若可能輸出第一名的最高總分，否則輸出 "No solution"。

輸入輸出格式

輸入：多測試用例。每例首行 n，隨後 n 行每行三個實數 a,b,c（0 ≤ a,b,c < 1000），最後一行 n 個整數表示排名 1~n 的選手 ID。n=0 結束。

輸出：每例輸出 "Case X: Y.YY" 或 "Case X: No solution"。

樣例解析

輸入：
3
100 200 300
100 200 300
100 200 300
1 2 3
3
100 200 300
100 200 300
100 200 300
3 2 1
0

輸出：
Case 1: 600.00
Case 2: 400.00

案例 1：排名 1,2,3 符合 ID 順序，第一名可得滿分 600。
案例 2：排名 3,2,1 違反同分小 ID 優先，第一名（ID 3）必須嚴格大於第二名（ID 2），最大分為 400（300+100）。

核心算法思路

1. 分數預處理與排序

每位選手 3 道題的可能得分存入陣列並升序排列（插入排序），便於後續從小到大嘗試組合。

2. 排名可行性判斷與最大化第一名分數

遞推處理排名序列：

• 第一名分數初始化為其最大可能總分
• 對於第 i 名（i≥2）：
  • 若 rank[i] > rank[i-1]（ID 較大），允許分數 ≤ 前名分數
  • 若 rank[i] < rank[i-1]（ID 較小），要求分數 < 前名分數（同分時小 ID 必須在前）
• 在滿足約束下，選擇該選手可能的 最大分數 作為當前上界，繼續向後傳遞
• 若某選手無法滿足約束（即使得 0 分也不符合），則無解

3. 3 道題得分組合枚舉優化

3 道題每題「得分」或「0 分」，共 2³=8 種組合。預先計算 8 種可能總分並按升序排列：

0
c[0]
c[1]
min(c[0]+c[1], c[2])
max(c[0]+c[1], c[2])
c[0]+c[2]
c[1]+c[2]
c[0]+c[1]+c[2]

按排名約束從小到大遍歷，找到滿足條件的最大值。作者代碼中用 switch-case 硬編碼 8 種情況，雖能 AC 但擴展性差。

改進方向與代碼重構

問題 1：固定大小結果陣列

使用動態容器 std::vector<double> 替代 results[1000]。

問題 2：題目數硬編碼

將 8 種組合生成泛化為 2^PROBLEM_NUM 種子集和計算，支援任意題數。

問題 3：重複代碼

提取「在約束下尋找最大可行分數」為獨立函數，消除兩段相似 switch 邏輯。

重構核心邏輯（偽代碼）

vector<double> genScores(const array<double,3>& p) {
    vector<double> scores = {0};
    for (int mask = 1; mask < 8; ++mask) {
        double sum = 0;
        for (int i = 0; i < 3; ++i)
            if (mask & (1<