atcoder abc201 D - Game in Momotetsu World

問題

解法

DFSのような探索ではお互いの最適行動がわからないため解くことができない。

ポイントは、

最終地点(右下)から最適なスコアを決めていけばDPで処理できる。
takahashiくんはスコアを最大化、aokiくんはスコアを最小化するのが最適行動。お互いの手番は交互なのですでに決定している右隣、下隣のスコア値の正負を逆転させてmaxを取ることで最適行動となる。

公式解説ではメモ化再帰で解いていたのでDP解を載せる。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
const int INF = 1e9;

int h,w;
vector<string> a;

int solve() {
  int s[h][w];
  REP(i,h) REP(j,w) s[i][j] = a[i][j] == '+' ? 1 : -1;

  // dp[i][j] := i,j地点でのtakahashiのスコア - aokiのスコアの最良スコア
  int dp[h][w];
  REP(i,h) REP(j,w) dp[i][j] = -INF; // dp初期値
  dp[h-1][w-1] = 0; // 右下は0

  // 右下から順番にみていく
  for(int i = h-1; 0 <= i; i--) {
    for(int j = w-1; 0 <= j; j--) {
      if (i < h-1) dp[i][j] = max(dp[i][j], s[i+1][j] - dp[i+1][j]); // 下
      if (j < w-1) dp[i][j] = max(dp[i][j], s[i][j+1] - dp[i][j+1]); // 右
    }
  }
  return dp[0][0];
}

int main() {
  cin >> h >> w;
  a.resize(h);
  REP(i,h) cin >> a[i];

  int score = solve();
  if (0 < score) cout << "Takahashi" << endl;
  else if (score < 0) cout << "Aoki" << endl;
  else cout << "Draw" << endl;

  return 0;
}