現在どちらの手番であるかと、それぞれのカードが高橋君の手札・青木君の手札・場札のどこにあるかの \(2\times 3^{N+M+L}\) 状態でゲームの局面を表現することができます。

行動を行うと、高橋君と青木君の手札に書かれた数の和が減少するため、局面がループすることはありません。よって、メモ化再帰などにより、各局面が手番のプレイヤーの必勝であるかを求めることで問題に答えることができます。

より詳細には、あるゲームの局面が手番のプレイヤーの必勝状態であるための必要十分条件は、手番のプレイヤーの取りうる行動であって、その行動後の局面が手番のプレイヤー必敗であるものが存在することです。この条件をを自然に再帰関数とすると以下のようになり、これをメモ化すればよいです。

function is_first_player_win(ゲームの状態, 手番のプレイヤー): // 手番のプレイヤーが必勝ならTrueを返す
  for each 取りうる行動:
    if is_first_player_win(行動後の状態, 相手プレイヤー) is False:
      return True
  return False

\(S=N+M+L\) として状態数が \(O(3^S)\)、遷移が \(O(S^2)\) 通りあることから、全体で \(O(3^S S^2)\) 時間でこの問題を解くことができました。

より基礎的なゲームの問題
ABC349E『Weighted Tic-Tac-Toe』
ABC354E『Remove Pairs』