AtCoderの Typical DP Contestを解いてみた (B ゲーム)

今回もTypical DP Contestを解いたのでアウトプットします.

今回解いた問題はB ゲームです

前回までの記事は以下の通りです.

1. A コンテスト

B ゲーム

今回は「B ゲーム」という問題を解きました.

問題の概要

(問題自体はAtCoderで確認してください.) 二人のプレイヤーがゲームをしている.

山が二つ用意されていて、左の山には個の物が、右の山には個の物が積まれている.

それぞれ上から番目の物の価値はである.

二人のプレイヤーは交互に以下の操作を繰り返す.

• 両方の山が空であれば、ゲーム終了
• 片方の山が空であれば、もう片方の山の一番上の物を取る.
• 両方の山が空でなければ、好きな方の山を選び、一番上の物を取る.

両者が最善を尽くした時の先攻の獲得した物の価値の合計を求めよ.

解法

: 左の山が個、右の山が個残っている状態でゲームをはじめた時の先攻が得られる最大の価値

最終的な出力はです. (左の山に個, 右の山に個残っている状態がゲーム開始時点なので)

今回の問題は、各プレイヤーが最善を尽くすので、先攻のターンと後攻のターンで場合分けをする必要があります.

先攻のターンのとき

先攻は残っている山の中で、一番価値の高いものを取ろうとします.

したがって、 $$ dp[i][j] = max(dp[i - 1][j] + a[A - i], dp[i][j - 1] + b[B - j]) $$ となります.

後攻のターンのとき

後攻のプレイヤーにはなるべく価値の低いものを選んでもらうようにするのが最善手です.

なお、相手が物を取っても、先攻の得点には関係ないので加算しません. $$ dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) $$

初期値

は左に山が残っておらず、右の山からしか物を取れないことを表しています.

したがって右の山の一番上を取った得点を初期値として格納します.

右の山が残っていない時も同様です.

$$ \begin{cases} dp[0][j] = dp[0][j - 1] + b[B - j] & (先攻) \\ dp[i][0] = dp[i - 1][0] + a[A - i] & (先攻) \\ dp[0][j] = dp[0][j - 1] & (後攻) \\ dp[i][0] = dp[i - 1][0] & (後攻) \end{cases} $$

ソース

使用言語はC++です.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B;
    cin >> A >> B;
    int N = A + B;
    ll a[A], b[B];
    rep(i, 0, A) cin >> a[i];
    rep(i, 0, B) cin >> b[i];
    ll dp[A + 1][B + 1];

    dp[0][0] = 0;

    rep(i, 0, A + 1) {
        rep(j, 0, B + 1) {
            if(i == 0 && j == 0) continue;
            if((N - i - j) % 2 == 0) {
                if(i == 0) dp[0][j] = dp[0][j - 1] + b[B - j];
                else if(j == 0) dp[i][0] = dp[i- 1][0] + a[A - i];
                else dp[i][j] = max(dp[i - 1][j] + a[A - i], dp[i][j - 1] + b[B - j]);
            } else {
                if(i == 0) dp[0][j] = dp[0][j - 1];
                else if(j == 0) dp[i][0] = dp[i - 1][0];
                else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[A][B] << endl;
}