Intended wrong answer

You cannot solve this problem with a greedy approach of “remove as many stones as they can in each turn.” The counterexample is:

10 3
1 3 4

Let us check that this is indeed the counterexample of the greedy algorithm. If Takahashi uses greedy approach, an example of the progression of the game is as follows. (Here, Takahashi greedily remove stones, but Aoki doesn’t, so this is merely an example)

• Takahashi removes \(4\) stones.
• Aoki removes \(4\) stones.
• Takahashi removes \(1\) stones.
• Aoki removes \(1\) stones.

In this example, Takahashi is forced to remove \(5\) stones due to Aoki’s move. However, if Takahashi removes \(3\) stones, no matter how many stones Aoki remove in the next turn, Takahashi can remove \(3\) or more stones in the next turn, so he can remove at least \(6\) stones.

Thus, depending on \(\{A_i\}\) and \(N\), this problem may require a complex strategy. Therefore, we came up with using exhaustive-search algorithm.

Intended answer

This problem can be solved with the following DP (Dynamic Programming):

\(\mathrm{DP}[n]=\) the number of stones that the first player can take if the game starts with a pile with \(n\) stones.

The transition is:

\(\mathrm{DP}[n]=\max \{A_i+(n-A_i)-\mathrm{DP}[n-A_i] \mid A_i\leq n\}.\)

The semantics of this equation is: if the first player removes \(A_i\) stones, he will end up with removing \(A_i+\) (the number of stones that the second player can remove if the game starts with a pile with \(n-A_i\)) stones, so the desired value is the maximum over all \(i\).

This DP has \(O(N)\) states, each transition of which is processed in an \(O(K)\) time, so we can find \(\mathrm{DP}[N]\) in a total of \(O(NK)\) time.

Sample code (C)