🔗 🟡 2212. Maximum Points in an Archery Competition

Problem Statement

題目簡述

Alice 和 Bob 進行射箭比賽。比賽共有 12 個得分區域，分值為 00 到 1111。
給定箭的總數 numArrows\text{numArrows}，以及 Alice 在每個區域射中的箭數陣列 aliceArrows\text{aliceArrows}。

比賽規則如下：

  • 針對第 kk 個區域（分值為 kk），如果 Bob 射中的箭數大於 Alice（即 bobArrows[k]>aliceArrows[k]\text{bobArrows}[k] > \text{aliceArrows}[k]），則 Bob 獲得該區域的 kk 分；否則 Alice 獲得該區域的分數（若皆為 00 則無人得分）。
  • Bob 射出的箭總數必須恰好為 numArrows\text{numArrows}。

請返回一個陣列 bobArrows\text{bobArrows}，表示能讓 Bob 獲得最大總分的箭數分佈。如果有多種方案能獲得相同的最大分數，返回其中任意一種即可。

Constraints

約束條件

  • numArrows∈[1,105]\text{numArrows} \in [1, 10^5]
  • aliceArrows.length=12\text{aliceArrows.length} = 12
  • ∑aliceArrows[i]=numArrows\sum \text{aliceArrows}[i] = \text{numArrows}
  • aliceArrows[i]≥0\text{aliceArrows}[i] \ge 0

思路：決策優化與背包模型

核心觀察

關鍵決策：贏下還是放棄？

對於每一個得分區域 ii（分值為 ii），Bob 只有兩種理性決策：

  1. 爭奪並贏下：投入比 Alice 多 11 支的箭，即消耗代價 wi=aliceArrows[i]+1w_i = \text{aliceArrows}[i] + 1 支箭，獲得價值 vi=iv_i = i 的分數。
  2. 放棄：投入 00 支箭，消耗代價 00，獲得分數 00。

任何介於 11 到 aliceArrows[i]\text{aliceArrows}[i] 之間的投箭數都是不划算的，因為消耗了資源卻無法得分；同樣地，投入超過 aliceArrows[i]+1\text{aliceArrows}[i] + 1 支箭也是多餘的浪費。

因此，問題本質上是：我們要在總箭數限制下，選擇贏下哪些得分區域的集合，使總得分最大。

方法一：二進制枚舉 (Bitmask)

狀態壓縮與暴力搜尋

由於得分區域數量 n=12n = 12 非常小，所有可能贏下的區域子集只有 212=40962^{12} = 4096 種。
如此微小的搜尋空間，直接利用二進制狀態壓縮（Bitmask）進行暴力列舉是最直觀的做法。

由於只有 1212 個得分區域，我們可以把「要贏下哪些區域」的選擇狀態，壓縮在一個整數的二進制位中。在遍歷所有的選擇可能時，如果當前組合所需的總箭數沒有超過限制，且總得分比之前記錄的更大，我們就更新最優得分與對應的射箭方案。

剩餘箭的處理

題目要求必須射出恰好 numArrows\text{numArrows} 支箭。如果在確定了最優得分組合後，手裡還有剩餘的箭，我們可以直接把剩餘的箭全部分配到任意區域（例如分值為 00 的區域），這既滿足了題目規定的總箭數約束，又不會影響我們已經算好的得分。

複雜度分析

  • 時間複雜度：O(2n⋅n)\mathcal{O}(2^n \cdot n)，其中 n=12n = 12 是得分區域數量。總共列舉 212=40962^{12} = 4096 個狀態，每個狀態需要 O(n)\mathcal{O}(n) 時間計算得分與箭數分配。
  • 空間複雜度：O(n)\mathcal{O}(n)，用於存儲答案分配陣列。

方法二：0-1 背包 DP 與方案構造

1. 從遞迴到遞推：如何想到 0-1 背包？

核心觀察

雖然本題 n=12n = 12 極小，二進制枚舉足以過關。但如果 nn 擴大（例如 n=100n = 100），2n2^n 的指數級複雜度將會失效。

仔細思考，我們對每個得分區域 ii 的決策是獨立的：要麼不選（花費 00 支箭，得 00 分），要麼選（花費 aliceArrows[i]+1\text{aliceArrows}[i] + 1 支箭，得 ii 分）。
這是一個非常標準的 0-1 背包問題（0-1 Knapsack Problem）：

  • 背包容量：箭的總數 numArrows\text{numArrows}。
  • 物品：nn 個得分區域。
  • 物品體積（代價）：wi=aliceArrows[i]+1w_i = \text{aliceArrows}[i] + 1。
  • 物品價值（收益）：vi=iv_i = i。

2. 狀態定義與轉移

設 f[i][j]f[i][j] 表示考慮前 ii 個得分區域，在剩餘 jj 支箭時能獲得的最大得分。
對於第 ii 個區域（成本 w=aliceArrows[i]+1w = \text{aliceArrows}[i] + 1，價值 v=iv = i）：

  • 不選：f[i+1][j]=f[i][j]f[i + 1][j] = f[i][j]
  • 選（前提是 j≥wj \ge w）：f[i+1][j]=f[i][j−w]+vf[i + 1][j] = f[i][j - w] + v
  • 兩者取最大值：

    f[i+1][j]={max⁡(f[i][j],f[i][j−w]+v),if j≥wf[i][j],if j<wf[i + 1][j] = \begin{cases} \max(f[i][j], f[i][j - w] + v), & \text{if } j \ge w \\ f[i][j], & \text{if } j < w \end{cases}

其中 f[0][j]=0f[0][j] = 0。最終的最大得分為 f[n][numArrows]f[n][\text{numArrows}]。

3. 方案重構（路徑回溯）

方案構造套路

對於需要輸出具體方案的背包問題，通常保留二維 DP 陣列更方便。原因是每個狀態 f[i+1][j]f[i + 1][j] 都記錄了它是從「不選第 ii 個區域」還是「選第 ii 個區域」轉移過來的，我們可以沿著這條轉移路徑倒推出答案。

具體做法是從終點 f[n][numArrows]f[n][\text{numArrows}] 往回走。設當前剩餘箭數為 rem=numArrowsrem = \text{numArrows}，倒序枚舉 ii 從 n−1n-1 到 00：

  • 若 rem≥wrem \ge w 且 f[i+1][rem]==f[i][rem−w]+vf[i + 1][rem] == f[i][rem - w] + v，說明最優解中選了第 ii 個區域，令 bobArrows[i]=w\text{bobArrows}[i] = w，並更新 rem←rem−wrem \gets rem - w。
  • 否則，說明第 ii 個區域沒有被選，bobArrows[i]\text{bobArrows}[i] 保持為 00。

最後如果還有剩餘箭數 remrem，直接加到第 00 個區域即可。第 00 個區域本身不貢獻分數，所以這一步只負責滿足「恰好射出 numArrows\text{numArrows} 支箭」的要求，不會改變最優得分。

複雜度分析

  • 時間複雜度：O(n⋅numArrows)\mathcal{O}(n \cdot \text{numArrows})，其中 n=12n = 12。DP 狀態數為 12×numArrows12 \times \text{numArrows}，每個狀態轉移只需 O(1)\mathcal{O}(1)，方案構造只需 O(n)\mathcal{O}(n)。
  • 空間複雜度：O(n⋅numArrows)\mathcal{O}(n \cdot \text{numArrows})，需要完整的二維 DP 陣列來支持路徑回溯。

Code

方法一：二進制枚舉 (Bitmask)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
        n = len(aliceArrows)

        ans = [0] * n
        mx = 0
        # 共有 12 個區域，使用 12 位二進制整數 msk 列舉所有得分區域組合 (2^12 = 4096)
        for msk in range(1 << n):
            cur = 0
            rem = numArrows
            for i, a in enumerate(aliceArrows):
                if (msk >> i) & 1:
                    cur += i
                    rem -= a + 1   # 消耗成本：Alice 的箭數 + 1
            
            # 若剩餘箭數大於等於 0，且總得分高於歷史最大值，則更新最優解
            if rem >= 0 and cur > mx:
                mx = cur
                # 重新根據當前最優選擇 msk 構造 Bob 的射箭方案
                for i, a in enumerate(aliceArrows):
                    ans[i] = a + 1 if (msk >> i) & 1 else 0
                # 將剩餘所有的箭（無論多少）全部射往分值為 0 的區域以滿足「射出箭數恰好為 numArrows」的規定
                ans[0] += rem
        return ans

方法二：0-1 背包 DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
        n = len(aliceArrows)

        # f[i][j] 表示前 i 個得分區域，在剩餘 j 支箭時能獲得的最大總分
        f = [[0] * (numArrows + 1) for _ in range(n + 1)]
        for i, a in enumerate(aliceArrows):
            v = i      # 當前區域分值（價值）
            w = a + 1  # 贏下該區域所需的箭數（成本）
            for j in range(numArrows + 1):
                # 這裡的分支寫法相比於一律先複製 f[i + 1][j] = f[i][j] 再比較大小的寫法，可以帶來不錯的常數優化
                if j >= w:
                    f[i + 1][j] = max(f[i][j], f[i][j - w] + v)
                else:
                    f[i + 1][j] = f[i][j]

        # 藉由 DP 陣列反向回溯，重建 Bob 的投箭配置
        ans = [0] * n
        rem = numArrows  # 追蹤當前剩餘的箭數
        for i in range(n - 1, -1, -1):
            v = i
            w = aliceArrows[v] + 1
            # 若滿足轉移方程中的選擇分支，說明 Bob 在此區域射了 w 支箭並得分
            if rem >= w and f[i + 1][rem] == f[i][rem - w] + v:
                ans[i] = w
                rem -= w
        # 將回溯後依然剩餘的箭數，全部塞給分值為 0 的區域
        ans[0] += rem
        return ans