ARC085 D. ABS

問題

N枚の山札が与えられる。上からi番目のカードの数字はa_i。
XさんとYさんが、この山札を使ってゲームをする。最初にXさんはZが書かれたカード、YさんはWが書かれたカードを持っている。
2人は交互に「山札の上から1枚以上のカードを取り除く。最後にひいたカード以外は捨てる」という行動を繰り返す。
山札がなくなるとゲーム終了で、最後のスコアは両者のカードの数値の差の絶対値となる。

Xさんは最終スコアが最大化するように、Yさんは最終スコアが最小化するように行動する場合、最終スコアはどうなるか？

制約

• 入力はすべて整数
• 1 <= N <= 2000
• 1 <= Z,W,a_i <= 10^9

解法1

ゲームの先読み。

Yさんがi番目までカードを引いたとする。
Xさんはi+1番目から何枚かのカードを引くことになるが、このとき、最終スコアがどのようになるかがそれぞれの枚数の時でわかっていれば、それで最適な枚数を引けばよい。(Xさんは最大化したいので、最終スコアが最大になる枚数を引くことになる)

int dp[pos][turn] := turnさんの番で、相手がposまでカードを引いてる場合の最終スコア

として、メモ化再帰すればO(N^2)で求められる。

// ZとWはカードの数値を入れた配列vの最初2つに入れておく
int dp[2005][2];

int dfs(int pos, int turn){
  if(dp[pos][turn] != -1) return dp[pos][turn];

  int ret = (turn==0)?MIN:INF;
  REP(i,pos+1,N){
    int tmp;
    if(i == N-1){
      tmp = abs(v[pos]-v[i]);
    }else{
      tmp = dfs(i,1-turn);
    }

    if(turn == 0){
      ret = max(ret, tmp);
    }else{
      ret = min(ret, tmp);
    }
  }
  return dp[pos][turn] = ret;
}


// dfs(1,0)が答え

解法2

想定解法はO(1)。

最初、Xさんが取れる行動はいくつかあるが、「全部取る」「1枚残す」だけ考えればよい。
全部取る場合、Xさんはa_N、YさんはWになる。最終スコアはabs(a_N - W)。
1枚残す場合、Xさんはa_{N-1}、Yさんはa_Nになる。最終スコアはabs(a_{N-1} - a_N)。

2枚以上残した場合、Yさんは1枚残して最終スコアをabs(a_{N-1} - a_N)にすることができる。
なので、Xさんの最終スコアはabs(a_{N-1} - a_N)より大きくはならない。(そうできる場合はYさんによってabs(a_{N-1} - a_N)にされてしまう)
結局、Xさんは、abs(a_N - W)かabs(a_{N-1} - a_N)かの2つしか選ぶことができないので、どちらか大きい方になるように行動するしかない。

反省

コンテスト中は無駄な状態を考えて、
dp[i][j][turn]:=Xさんが最後に取ったのがi番目でYさんが最後に取ったのがj番目でturnさんの番が回ってきたときの最大スコア
を考えてしまっていた。
けど、「1枚以上取る必要がある」ので、自分の持ってたカードの数字は保持しておいても意味がなく、結局i,jの2つ区別して持つは必要ない。

一応、メモリの持ち方をdp[N][N]にして考えることもできて(turnの部分はiとjを見て決められるので不要)、dp[i][j]として、
dp[i][j]:=Xさんが最後に取ったのがi番目でYさんが最後に取ったのがj番目のときの最大スコア
として考える。
i,jを見てどちらの手番かがわかり、かつ、手番の方のiまたはjの値は依存しないので、i,jで小さい方がiだった場合、0～j-1までのdp[i][j]の値は同じなので、1回だけ計算すればよい。

  for(int i=N-1; i>=0; i--){
    for(int j=N-1; j>=0; j--){
      if(i == j) continue; //あり得ないパターンなので無視
      if(i == N-1 || j == N-1){ //最後のカードを取った場合
        dp[i][j] = abs(v[i]-v[j]);
      }
      else{
        int ret = (i<j)?MIN:INF;
        if(i<j){//Xさんの手番
          if(i == j-1){
            REP(k,j+1,N){
              ret = max(ret, dp[k][j]);
            }
          }else{
            ret = dp[j-1][j]; //前に持っていたカードに依存しないので、すでに計算済みの値をコピー
          }
        }else{//Yさんの手番
          if(j == i-1){
            REP(k,i+1,N){
              ret = min(ret, dp[i][k]);
            }
          }else{
            ret = dp[i][i-1]; //前に持っていたカードに依存しないので、すでに計算済みの値をコピー
          }
        }
        dp[i][j] = ret;
      }
    }
  }

//dp[0][1]が答え