【AtCoder】【C#】Typical DP Contest - B - ゲーム
Typical DP Contest - B - ゲームを解いてみました。
はじめに
本記事のテーマ
本記事は、Typical DP Contest - B - ゲームを解いてみて、ポイントになりそうな部分を考察してみます。
問題へのリンク
問題の概要
- A個の要素を持つ数列と、B個の要素を持つ数列が与えられる
- 先頭の要素から先攻・後攻の順で要素を一つずつ取り出し、その要素の値を点数として獲得する
- お互いが最善手をとった時、先攻の点数を最大化する
本題
実装
static void Main(string[] args) { int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray(); int A = input[0]; int B = input[1]; int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray(); int[] b = Console.ReadLine().Split().Select(int.Parse).ToArray(); int[,] DP = new int[A + 1, B + 1]; for (int l = A; l >= 0; l--) { for (int r = B; r >= 0; r--) { if (l == A && r == B) continue; if ((l + r) % 2 == 0) { // SENKO if (l == A) { DP[l, r] = DP[l, r + 1] + b[r]; } else if (r == B) { DP[l, r] = DP[l + 1, r] + a[l]; } else { DP[l, r] = Math.Max(DP[l + 1, r] + a[l], DP[l, r + 1] + b[r } } else { // KOUKO if (l == A) { DP[l, r] = DP[l, r + 1]; } else if (r == B) { DP[l, r] = DP[l + 1, r]; } else { DP[l, r] = Math.Min(DP[l + 1, r], DP[l, r + 1]); } } } } Console.WriteLine(DP[0, 0]); }
実装のリンク
実装への考察
この実装でポイントとなるのは下記3点です
DPテーブルの定義
DP[i, j]において i が示すのは、Aの数列から i 番目の要素までを取り出した時で、j が示すのはBの数列から j 番目の要素までを取り出した時です。
まとめるとDP[i, j]はAから i までの要素を取り出した時、Bからは j までの要素を取り出した時の先攻の点数とします。
DPの計算順
今回のように最後まで計算が完了しないと、選択した答えの正しさがわからないような問題は、最後から部分的に計算し、その和を求めるほうが良さそうです。ようは、最後がこの状態になっていることがベストという状態からスタートして、各時点における点数を漸化式で表せれば良いです。
for (int l = A; l >= 0; l--) { for (int r = B; r >= 0; r--) { (略) } }
先攻と後攻に分かれていること
先攻と後攻がわかれていることです。これは問題を読めばそのとおりなのですが、先攻は自分の点数を最大化しようとします。後攻は自分の点数を最小化しようとします。DPテーブルは先攻の点数なので、後攻の処理をしてもDPテーブルに新しい値は入りません。ただ、最小化するようにMin関数で値を選択します。
感想
上記に上げたような処理が本番でかけるような気がしないので、とりあえずは他のDP問題をたくさん解いていきたいですね