(問題 11) NGABCOverゲーム step.1 COBOL(Beta)編（paizaランク S 相当）

問題 10 までとは違う問題についてここからは学習していきます。


3 つの変数 A, B, C がはじめすべて 0 で初期化されています。また、N 個の数字のトリオ (a_i, b_i, c_i) が与えられます。AliceさんとBobさんは変数 A, B, C に対して、以下のように行動していきます。

N 個の中から 1 つ数字のトリオ (a_i, b_i, c_i) を選び、A に a_i、B に b_i、C に c_i を加算する。ただし、加算後 A が P 以下、B が Q 以下、C が R 以下にならなければならない。

Aliceさんから始め、先に行動が出来なくなった方が負けです。2 人が最適戦略を行ったときにどちらが勝つかを求めてください。

まず、(A, B, C) = (D, E, F) であり、Aliceさんが先手の状況を考えましょう。

仮に数字のトリオ (d, e, f) を選んだとします。そのとき、(A, B, C) = (D + d, E + e, F + f) にかわり、AliceさんとBobさんのターンが入れ替わり、Aliceさんが後手の状態になります。もし、(D + d, E + e, F + f) が後手が勝てる盤面であるならば、この盤面を選ぶことにより、この時点で (d, e, f) を選ぶことによりAliceさんが勝つことが出来ます。



Bobさんが先手であった場合も同様のことが言えます。

このことより、AliceさんとBobさんは遷移先の盤面で後手が勝てるような盤面に遷移させるのが最適であることがわかります。

よって以下のDPを考えてみましょう。

DP[D][E][F] = ((A, B, C) = (D, E, F) からゲームを始めた時の先手の勝敗)

まず、D が P 以下、E が Q 以下、F が R 以下のいずれかを満たしていなければ、先手必勝です。

そうでないとき、N 個の選んだ手にたいして、それぞれ結果がわかっているならば、遷移後の盤面が先手が勝つ盤面しかなければ、先手が負け、そうでなければ、遷移後の盤面が後手が勝つ、つまり、先手が負ける盤面を選ぶことで先手が勝つことができます。

問題 7 で扱った後退解析を行うことにより、すべての盤面に対して先手の勝敗を求めることが出来ます。

では、実際に求めてみましょう。

問題

3 つの変数 A, B, C がはじめすべて 0 で初期化されています。また、N 個の数字のトリオ (a_i, b_i, c_i) (1 ≦ i ≦ N) が与えられます。AliceさんとBobさんは整数 A, B, C に対して、以下のように行動していきます。

N 個の中から 1 つ数字のトリオ (a_i, b_i, c_i) を選び、A に a_i、B に b_i、C に c_i を加算する。ただし、加算後 A が P 以下、B が Q 以下、C が R 以下にならなければならない。

Aliceさんから始め、先に行動が出来なくなった方が負けです。2 人が最適戦略を行ったときにどちらが勝つかを求めてください。