想定誤解法

この問題を「各手番で石を取れるだけ取る」という貪欲法で解くことはできません。反例は例えば

10 3
1 3 4

です。実際にこれが貪欲法の反例になっていることを確かめましょう。 高橋君が貪欲法を使った場合、ゲームの進行の一例は次のようになります。(高橋君は貪欲法を使いますが、青木君はそうとは限らないため、あくまで一例です)

• 高橋君が \(4\) 個の石を取る
• 青木君が \(4\) 個の石を取る
• 高橋君が \(1\) 個の石を取る
• 青木君が \(1\) 個の石を取る

この例では、青木君の応手次第で高橋君は \(5\) 個の石しか取ることができません。しかし、高橋君が最初に \(3\) 個の石しか取らなかった場合、次に青木君が何個の石を取ったとしても、次の高橋君の手番で \(3\) 個以上の石を取ることができるため、必ず \(6\) 個以上の石を取ることができます。

このように、\(\{A_i\}\) と \(N\) の関係によっては、この問題は複雑な戦略を持ちえます。このことから、全探索ベースの解法を考えるという方針が立ちます。

想定解法

この問題は次のようなDPで解くことができます。

\(\mathrm{DP}[n]=\) 石が \(n\) 個残っている状態からゲームを始めたとき、先手が取ることのできる石の個数

遷移は

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

となります。この式の意味は次の通りです。先手番が \(A_i\) 個の石を取ったとき、最終的に取れる石の個数は、\(A_i+\) 「石が \(n-A_i\) 個 残っている状態からゲームを始めたとき、後手が取ることのできる石の個数」なので、これを全ての \(i\) について調べて max を取ったものが求める値です。
（※ \(A_1=1\) であることから石は必ず取り尽くすことができ、特に「石が \(n\) 個残っている状態からゲームを始めたとき、後手が取ることのできる石の個数」は \(n-\mathrm{DP}[n]\) となります）

このDPは状態数が \(O(N)\) であり、遷移が \(O(K)\) 時間で計算できるので、\(O(NK)\) で \(\mathrm{DP}[N]\) を求めることができます。

実装例(C)