xxxasdfghjk999のブログ

iroiro

AtCoder-Typical DP Contest B問題をやりました

プログラミング備忘録

前回に続いてB問題も解いてみました。
問題文以下
B: ゲーム - Typical DP Contest | AtCoder

Problem Statement
すぬけ君とすめけ君がゲームをしている。最初に、二つの山がある。左の山には A 個の物が積まれており、上から i 番目のものの価値は ai である。左の山には B 個の物が積まれており、上から i 番目のものの価値は bi である。すぬけ君とすめけ君は、すぬけ君からはじめて交互に次の操作を繰り返す。

    両方の山が空であれば、ゲームを終了する。
    片方の山が空であれば、空でないほうの山の一番上のものをとる。
    両方の山が空でなければ、好きなほうの山を選び、一番上のものをとる。

両者が最善を尽くしたとき、すぬけ君の取るものの価値の合計を求めよ。
Constraints

    1≤A,B≤1000
    1≤ai,bi≤1000

Input Format
入力は以下の形式で標準入力から与えられる。

A B
a1…aA
b1…bB

ソースは続きから

    #include<stdio.h>
    int dp[1001][1001]={-1};
    int A;//left
    int B;//right
    int a[1001];
    int b[1001];
    // turn 1...先攻
    int DP(int left,int right,int turn)
    {
      if(left == 0 && right == 0)
        return 0;
      if(dp[left][right] != -1)
        return dp[left][right];
      if(turn == 1){
        if(left == 0)
          return dp[left][right] = DP(left,right-1,0) + b[B-right+1];
        else if(right == 0)
          return dp[left][right] = DP(left-1,right,0) + a[A-left+1];
        else{
          return dp[left][right] =
            (DP(left,right-1,0) + b[B-right+1]) > (DP(left-1,right,0) + a[A-left+1])
            ? (DP(left,right-1,0) + b[B-right+1]) : (DP(left-1,right,0) + a[A-left+1]);
        }
      }else{
          if(left == 0)
          return dp[left][right] = DP(left,right-1,1);
        else if(right == 0)
          return dp[left][right] = DP(left-1,right,1);
        else{
          return dp[left][right] =
            DP(left-1,right,1)  < DP(left,right-1,1)
            ? DP(left-1,right,1) : DP(left,right-1,1);
        }
      }
     
     
    }
     
    int main()
    {
      int i,j;
      for(i=0;i<1001;i++)
        for(j=0;j<1001;j++)
          dp[i][j] = -1;
      scanf("%d %d",&A,&B);
      for(i=1;i<=A;i++)
        scanf("%d",&a[i]);
      for(i=1;i<=B;i++)
        scanf("%d",&b[i]);
      printf("%d\n",DP(A,B,1));
      return 0;
    }

「お互いが最善を尽くす」を、互いが互いに点数を最大化しようしている、と考えるとなかなか難しいです。ここで視点を先手に固定してみると、先手は先手自身の点数を最大化しようとしますが、後手は先手の点数を最小化するようにゲームを進めるだろう、と考えることができます。この問題では、最終的に先手の点数を出力しなければならないので、先手に視点を固定して、動的計画法におけるdpを設定します。
ここでは
dp[left][right] = (左側にleft個、右側にright個残っているときの先手の点数の最大値）
と設定しました。残っている物の数でdpを設定してもよいと思います(その方が添え字は楽かな)。
このdpを利用して、動的計画法特有の漸化式を記述します。具体的には、dp[left][right]の添字を前後させるときの関係式です。
式だけ書くと、

left == 0 かつ right == 0のとき
dp[left][right] = 0;
>自分のターンのとき
left != 0 かつ right != 0 のとき
dp[left][right] = max{dp[left][right-1] + b[B-right+1] ,dp[left-1][right] + a[A-left+1]}
left == 0のとき
dp[left][right] = dp[left][right-1] + b[B-right+1]
right == 0のとき
dp[left][right] = dp[left-1][right] + a[A-left+1]
>相手のターンのとき
left != 0 かつ right != 0 のとき
dp[left][right] = min{dp[left][right-1] ,dp[left-1][right]}
left == 0のとき
dp[left][right] = dp[left][right-1]
right == 0のとき
dp[left][right] = dp[left-1][right]

dpの漸化式は上のようになります。後手のターンのときは先手の利益が最小となるように右か左から取ることになるので、そこは注意が必要です。左右で何もものがないときは価値が0となり、再帰の終点になります。実際の漸化式の実装はメモ化再帰を用いました。