(問題 11) NGABCOverゲーム step.1 C編（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 に対して、以下のように行動していきます。
Aliceさんから始め、先に行動が出来なくなった方が負けです。2 人が最適戦略を行ったときにどちらが勝つかを求めてください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N P Q R
a_1 b_1 c_1
a_2 b_2 c_2
...
a_N b_N c_N
1 行目には 1 つの整数 N が与えられます
i + 1 (1 ≦ i ≦ N) 行目には 3 つの整数 a_i,b_i,c_i が与えられます。
入力は合計で 1 + N 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを 1 行で出力してください。
Aliceさんが勝つ場合にはAを、Bobさんが勝つ場合にはBを出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
- 1 ≦ N ≦ 10
- 1 ≦ P, Q, R ≦ 75
- 0 ≦ a_i ≦ P (1 ≦ i ≦ N)
- 0 ≦ b_i ≦ Q (1 ≦ i ≦ N)
- 0 ≦ c_i ≦ R (1 ≦ i ≦ N)
- a_i + b_i + c_i > 0 (1 ≦ i ≦ N)
- 入力例1
-
3 3 3 3
1 2 1
2 1 0
2 2 2
- 出力例1
-
A
- 入力例2
-
3 75 75 74
1 0 0
0 1 0
0 0 1
- 出力例2
-
B
- 入力例3
-
1 73 73 73
9 4 13
- 出力例3
-
A
