Let be the player who moves when the number of remaining floors is odd, and the player who moves when it is even.
We can compute 's final score using the following greedy algorithm.
The monkeys on the topmost floor are guaranteed to be scored by . Process the remaining floors in pairs from top to bottom. Insert the monkey counts of the two newly considered floors into a max-priority queue, then extract the maximum and add it to 's score. Leave all unselected values in the queue. If is even, the bottommost floor is ignored.
If is odd, is Ishigami; otherwise, is Iino. Since every monkey is eventually scored by exactly one player, 's score is the total number of monkeys minus 's score.
The time complexity is , and the space complexity is .
Proof
Consider the floors in bottom-to-top order. Represent a floor assigned to by ( and a floor assigned to by ).
For the first parentheses, define
Solution written by GPT-6
When the number of remaining floors is even, it is 's turn, and we consider a balanced parenthesis sequence satisfying
When the number of remaining floors is odd, it is 's turn, and we consider a sequence satisfying
In both cases, the inequality must hold for every prefix. We call such sequences valid.
First, we show that can guarantee the total weight assigned to ) in any valid sequence.
On 's turn, the current sequence satisfies and .
Let be the first position where the height reaches .
). removes the bottommost floor and scores its monkeys.)). removes the floor at position , merging it into the floor immediately below, and marks the merged floor with ).In either case, the resulting sequence is balanced, and no weight assigned to ) is lost. In the second case, all preceding prefix heights remain nonnegative, while all subsequent heights increase by one.
Now consider 's turn, when the current sequence is balanced.
We distinguish four possible moves by .
(. Removing it produces a sequence satisfying and , so can apply the previous strategy.((: Mark the merged floor with (. The resulting sequence satisfies the same height conditions, and the weight assigned to ) remains unchanged.() or )(: Mark the merged floor with ). The resulting sequence again satisfies the same height conditions. Moreover, some weight previously assigned to ( is now assigned to ), so the assigned score does not decrease.)): Mark the merged floor with ). We show that can restore a balanced sequence by merging a suitable pair of consecutive opening parentheses ((.For the last case, consider the substring beginning at the opening parenthesis matched with the second ) of the merged pair. This substring has the form
where and are balanced parenthesis sequences, possibly empty.
After merges the final )) and merges the initial ((, this substring becomes
which is again balanced. Since both floors merged by were assigned to (, the weight assigned to ) does not decrease.
Thus, regardless of 's move, can preserve a valid sequence without decreasing the assigned score. Repeating this strategy guarantees that eventually obtains at least the total weight initially assigned to ).
Conversely, can prevent from exceeding the maximum weight assigned to ) over all valid sequences.
Suppose always removes the bottommost remaining floor. Mark each original floor according to the player who removes it.
Among the bottommost original floors, the number removed by cannot exceed the number removed by , except that may have one extra removal if moves first. Indeed, whenever removes a floor in this prefix, the preceding move by must also have removed a floor in this prefix, unless moved first.
Therefore, the resulting parenthesis sequence is valid.
Moreover, every monkey initially on a floor removed by is scored by . Hence, 's actual score cannot exceed the total weight of floors marked with ).
Combining both directions, the optimal score of equals the maximum total weight assigned to ) over all valid parenthesis sequences.
It remains to maximize this weight.
In any valid sequence, the total number of closing parentheses is
The height conditions are equivalent to requiring that, among the topmost floors, at least
floors are marked with ). Together with the total count, these conditions completely characterize valid sequences.
In particular, we must select at least one floor among the topmost , at least two among the topmost , at least three among the topmost , and so on.
Therefore, we first select the topmost floor, then select one additional floor whenever two more floors are considered.
The optimal choice at each step is the largest value among all considered but unselected floors.
To prove this, consider an optimal solution that agrees with the greedy algorithm on all previous selections. Let be the current greedy choice.
If is not selected in this optimal solution, some other value among the floors considered so far must be selected instead, excluding the previously fixed selections.
By the greedy rule, . Replacing with cannot decrease the score. It also preserves feasibility: all earlier requirements are already satisfied by the fixed selections, while every later requirement contains both positions and therefore retains the same number of selected floors.
Thus, an optimal solution agreeing with the greedy choice always exists. Repeating this exchange proves that the greedy algorithm is optimal.
A max-priority queue implements these choices efficiently.