慣れないと頭がごっちゃになるけど、一度慣れればもう機械的に解ける系！！
問題概要
のグリッドがある。各マスには '+' か '-' のいずれかの文字が書かれている。
最初、左上マスにコマが置かれている。高橋君と青木君は交互に、次の操作を行う。
- コマを 1 つ右、または 1 つ下に動かす
- ただし、コマを盤上外に動かすことはできない
- コマを動かした人は、移動後のマスが '+' ならば 1 点を得て、'-' ならば 1 点を失う
どちらかが操作できなくなった時点でゲームは終了する。ゲームの結果は、終了時の 2 人の得点が異なるならば得点の大きい方が勝ち、同じならば引き分けとなる。
双方最善を尽くした場合の結果を求めよ。
制約
解法
いわゆる「ゲームを DP で解く」系の問題ですね！
そのタイプの問題にまったく馴染みのない方は、次の記事を読んでみてください。
さて、ゲームを解く DP のうち、特に「相手との得点差」も最大化したい場合には、次のような再帰関数を組んで解ける場合が多いです。
// 盤面の状態が state である状態からスタートして、 // その状態で手番であるプレイヤーの得られる得点から、 // 相手プレイヤーの得られる得点を引いた値の最大値を返す int dfs(State state) { // 終端条件 if (state が終局である) return (終局に応じた得点); // 打てる手をすべて試す int res = -INF; for (state2 : state から遷移できる局面全て) { int score = -dfs(state2); // dfs(state2) は相手視点の得点なので、-1 倍する int add = (その手を打つこと自体の得点変化); // 0 であることも多い res = max(res, score + add); } return res; }
なお、このような形式の再帰関数を用いたゲーム探索は、ネガマックス法などとも呼ばれます。ゲーム探索手法として有名なミニマックス法に対して、手番の対称性を考慮することで、シンプルな実装にしたものです。
競プロでは、基本的にミニマックス法よりも、それを改良したネガマックス法を用いた方が実装が簡潔になってよいと思います。
また、競プロでは、この再帰関数をこのまま実装するだけだと TLE になることが多いです。それは、同一局面を何度も何度も探索し得ることが原因です。
そこで、メモ化しましょう。いわゆる、メモ化再帰と呼ばれる DP ですね！
今回の問題
今回の問題では、「盤面の状態」はコマの置いてあるマスの座標 で表現できます。
よって、次のような再帰関数で解けます。この再帰関数では、メモ化も実施しています。
// コマがマス (i, j) にある状態からスタートして、 // その状態で手番であるプレイヤーの得られる得点から、 // 相手プレイヤーの得られる得点を引いた値の最大値を返す int dfs(int i, int j, vector<vector<int>> &dp) { if (dp[i][j] が更新済み) return dp[i][j]; // 終端条件 if (マス (i, j) が右下マスである) return 0; // 打てる手をすべて試す int res = -INF; if (コマを下に動かせるとき) { int score = -dfs(i+1, j); int add = (マス (i+1, j) に応じた値); res = max(res, score + add); } if (コマを右に動かせるとき) { int score = -dfs(i, j+1); int add = (マス (i, j+1) に応じた値); res = max(res, score + add); } // メモ化しながら答えを返す return dp[i][j] = res; }
計算量は、 です。
コード
上に書いた再帰関数の細部を詰めることで AC できます。dfs(0, 0, dp) の値が正ならば先手勝ち、負ならば後手勝ち、0 ならば引き分けです！
#include <bits/stdc++.h> using namespace std; // 入力 int H, W; vector<string> A; // コマがマス (i, j) にある状態からスタートして、 // その状態で手番であるプレイヤーの得られる得点から、 // 相手プレイヤーの得られる得点を引いた値の最大値を返す int dfs(int i, int j, vector<vector<int>> &dp) { if (dp[i][j] != -1) return dp[i][j]; // 終端条件 if (i == H-1 && j == W-1) return 0; // 打てる手をすべて試す int res = -(1<<29); if (i+1 < H) { res = max(res, -dfs(i+1, j, dp) + (A[i+1][j] == '+' ? 1 : -1)); } if (j+1 < W) { res = max(res, -dfs(i, j+1, dp) + (A[i][j+1] == '+' ? 1 : -1)); } // メモ化しながら答えを返す return dp[i][j] = res; } int main() { // 入力 cin >> H >> W; A.resize(H); for (int r = 0; r < H; ++r) cin >> A[r]; // メモ化再帰 vector<vector<int>> dp(H, vector<int>(W, -1)); int res = dfs(0, 0, dp); // 出力 if (res > 0) cout << "Takahashi" << endl; else if (res < 0) cout << "Aoki" << endl; else cout << "Draw" << endl; }
メモ化再帰でなくても解ける！
なお、普通の for 文を回す DP でも解けます！
その場合は「終局から逆算していく」という考え方を用いると書きやすいと思います！
#include <bits/stdc++.h> using namespace std; const int INF = 1<<29; // chmax template<class T> void chmax(T& a, T b) { if (a < b) a = b; } int main() { // 入力 int H, W; cin >> H >> W; vector<string> A(H); for (int i = 0; i < H; ++i) cin >> A[i]; // DP vector<vector<int>> dp(H, vector<int>(W, -INF)); // 終局状態 dp[H-1][W-1] = 0; // 終局から逆算していく！ for (int i = H-1; i >= 0; --i) { for (int j = W-1; j >= 0; --j) { // コマを下に動かす場合 if (i+1 < H) { chmax(dp[i][j], -dp[i+1][j] + (A[i+1][j] == '+' ? 1 : -1)); } // コマを右に動かす場合 if (j+1 < W) { chmax(dp[i][j], -dp[i][j+1] + (A[i][j+1] == '+' ? 1 : -1)); } } } if (dp[0][0] > 0) cout << "Takahashi" << endl; else if (dp[0][0] < 0) cout << "Aoki" << endl; else cout << "Draw" << endl; }
