My solution consists of two parts: 1) generating an initial solution using a greedy algorithm, and 2) refining it with simulated annealing.

1. Initial Solution (Greedy Algorithm)

Repeat the following steps until all treasure boxes are opened:

• If there are available weapons, choose the weapon–box pair \((w, b)\) that maximizes the damage value \(A_{w,b}\) among all available weapons and unopened boxes. Then, attack box \(b\) using weapon \(w\).
• If no weapons are available, choose the box with the lowest remaining hardness and attack it with bare hands.

2. Simulated Annealing

(If you’re not familiar with simulated annealing, refer to Wikipedia or the Editorial of Introduction to Heuristic Contest (in Japanese).)

To efficiently update the solution, I maintain the following state variables:

• \(o_b\) (\(b \in [0, N)\)): the order in which box \(b\) is opened.
• \(a_{w,k}\) (\(w \in [0, N), k \in [0, C_w)\)): the box attacked in the \(k\)-th (\(0\)-indexed) attack by weapon \(w\). If \(a_{w,k} = N\), the \(k\)-th attack of weapon \(w\) is unused.
• \(l_b\) (\(b \in [0, N)\)): the list of weapons that attack box \(b\).
• \(d_b\) (\(b \in [0, N)\)): the total damage dealt to box \(b\) by weapons (excluding bare hands). This value may exceed the box’s hardness \(H_b\).

The total number of attacks \(T\) is given by: $$\( T = \underbrace{\sum_{b = 0}^{N-1} \max\{0, H_b - d_b\}}_{\text{attacks by bare hands}} + \underbrace{\sum_{w = 0}^{N-1} \left(C_w - \sum_{k=0}^{C_w - 1} 1\{a_{w,k} = N\} \right)}_{\text{attacks by weapons}}.\)$$

I use two types of neighborhood transitions:

1. (75%) Randomly select a weapon \(w \in [0, N)\), an attack index \(k \in [0, C_w)\), and a new target \(t \in [0, N]\), such that the box for weapon \(w\) is opened before \(t\) (i.e., \(o_w < o_t\)) if \(t < N\). Then, change \(a_{w,k}\) to \(t\). In this case, the change in score \(T\) can be computed efficiently.
2. (25%) Randomly select two boxes \(i, j \in [0, N)\) and swap their opening order if possible (this can be easily verified using \(o_b\), \(a_{w,k}\), and \(l_b\)). This operation does not affect the score \(T\).

In my final submission (C++), the loop runs approximately 40 million times, achieving a score of 8.75 million, which placed 14th.