たくあんポリポリ

勉強したことを載せていきます。( 主に、C#/ Algorithm / AtCoder / Unity / 最近はKaggleとPython )

【AtCoder】【C#】Typical DP Contest - B - ゲーム

f:id:c_taquna:20200115005201p:plain

Typical DP Contest - B - ゲームを解いてみました。

はじめに

本記事のテーマ

本記事は、Typical DP Contest - B - ゲームを解いてみて、ポイントになりそうな部分を考察してみます。

問題へのリンク

atcoder.jp

問題の概要

  • 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]);
}

実装のリンク

github.com

実装への考察

この実装でポイントとなるのは下記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問題をたくさん解いていきたいですね