\(N \le 30,\ M \le 900,\ K \le 10\) と制約が小さいことに注目し、

\(dp[\) 残っている宝石の集合 \(][\) ターンプレイヤーの位置 \(][\) 非ターンプレイヤーの位置 \(] = {}\)(ターンプレイヤーの取る宝石の価値) \(-\) (非ターンプレイヤーの取る宝石の価値)

の動的計画法を行いたいです。しかし、この計算の依存関係にはループがあり、簡単には値を決定できません。

ループのあるゲームの解析方法といえば、後退解析です。通常後退解析は勝敗・引き分けを決定するものですが、これに価値の差分を載せることにします。

計算の依存関係にループがある場合、そのループの中で「残っている宝石の集合」は変化しません。したがって、「残っている宝石の集合」の下位集合から順に後退解析で価値を決定することができます。

つまり、以下を行えばよいです。

• 「残っている宝石の集合」の下位集合から順に、後退解析を \(2^K\) 回行う。
  1. 行き先の価値が全て決定した頂点があれば、その頂点の価値を確定する。
  2. 未決定の頂点の全ての行き先の中で最も価値が高いものを調べ、正であればそれを採用して頂点の価値を確定する。
  3. それでも確定しない状態の価値は \(0\) である。

計算量は \(O(2^KN(N + M)\log N)\) です。

実装例 (C++)