- ゲーム系の最善手は逆算
- 木のDFSだが「間違えて元の局面に戻る」ようなDFSが絶対に発生しないので根への遷移かどうかのチェックは不要
- 問題文を誤読しないよう注意、直大さんのスコアは「マス[i][j] = o かつ マス[i][j] = マス[i+1][j]」でなく単純に「マス[i][j] = マス[i+1][j]」
https://atcoder.jp/contests/abc025/submissions/27466506
マスが 3x3 しかないので直感的に全探索できそうという気持ちになる。少し考えてみると全探索したときの計算量は であると分かる。ゲーム系の最善手は最終局面から逆算するのが定跡。直大さんのターンでは直大さんのスコアを最大化したくて直子さんのターンでは直子さんのスコアを最大化したい。所謂ミニマックス法と呼ばれているアルゴリズムである。score = T - Nとして「直大さんはスコアが最大となる局面を選び、直子さんはスコアが最小となる局面を選ぶ」と工夫しても良いし、図のように工夫せず直大さんと直子さんのスコアを両方返すようにしても良い。局面評価自体は最終局面（９ターン目）でしか計算しない。最終局面以外の１～８ターンでは最終局面から貰った評価値のうちMAXを現局面の評価値として採用し、そのまま返すだけで良い。スコアが「T=0、N=100」のような可能性もあるので maxscore = {-1,-1}; で初期化して maxscore = max(maxscore, res[y][x]); のようにする必要がある（ maxscore = {0,0} で初期化しないよう注意）。
具体的なDFSの実装方法だが慣れてないと悩みやすいと思う。自分は木のDFSのとき以下のテンプレートを毎回貼っている。
auto GTL_NyaaTreeDFS = [&] (auto self, std::vector<std::vector<long long>>& g, long long now, long long root = -1ll) -> void { for (auto af : g[now]) { if (af == root) continue; self(self, g, next, now); } };
しかし、今回は「間違えて元の局面に戻る」ようなDFSが絶対に発生しないのでrootという引数は不要であり、入力を隣接リストの代わりに局面の二次元配列にしてしまって良い（グラフを陽に持つ必要すらない）。範囲for文のところは候補手 3x3 通りのグリッド二重ループになる。現局面nowのうち空白マス1つ選んで書き込み、DFSを呼び出して遷移の評価値を戻り値から貰う。図のように現局面に戻してから別の候補手を処理する必要があるため、DFS呼び出し後に元に戻す処理を忘れずに書くようにする。
auto GTL_NyaaTreeDFS = [&] (auto self, vvll& now, ll times) -> pll { if (times == 9) return f(now); vvpll res; MakeVV(3, 3, res, {-1,-1}); rep(y, 0, 3) rep(x, 0, 3) { if (now[y][x] != -1) continue; now[y][x] = times % 2; res[y][x] = self(self, now, times + 1); now[y][x] = -1; } // 略 return maxres; };
感想: DFSに慣れてなくて苦労した上に問題文を誤読して二重に苦労した...
