問題概要
$3 \times 3$ のグリッド状の盤面があって，$i$ 行目第 $j$ 列には整数 $A_{ i, j }$ が書かれている．$A$ の総和は奇数である．
この盤面を使って Tic-tac-toe をする．Tic-tac-toe で勝敗が付いた場合は，その勝者の勝ちとする．引き分けだった場合は，それぞれのプレイヤーについて当該プレイヤーがマークしたセルに書かれている整数の和を得点とし，より大きい得点を獲得したプレイヤーの勝ちとする．
両者が最適にプレイしたときの勝者はどちらか？
制約
- $| A_{ i, j } | \leq 10^9$
解法
両者が最適にプレイすると Tic-tac-toe は引き分けになるので，終局まできっちり読み切る必要がありそうです．プレイヤーがマークできるセルの数はゲーム開始時点では $9$ 個あって，ターンが進行するごとに $1$ ずつ減っていくので，すべてのセルが埋まるまでの進行方法の総数は $9 \times 8 \times \dots \times 1 = 9! = 362{,}880$ 通りです．これは（現代の）計算機で十分扱える個数で，各盤面で不必要に時間をかけたりしなければ TL に間に合います．
とはいえ，単に「読み切る」と言っても，どのように勝敗を決定すればよいかは自明ではないかもしれません．今回のゲームは零和ゲームなので，先手の得＝後手の損となっています．先手の立場で考えれば，初期状態でどう着手すれば得点を最大化できるかが分かればよいです*1．これを求める方法として名前の付いた手法があるのですが，まず前提としてゲーム木というものがあります．これはざっくり言えば，
- ゲームに出現する各盤面を頂点に対応付けた根付き木である．
- 根は初期状態に対応する．
- 各盤面（に対応する頂点）から合法手で遷移できる盤面（に対応する頂点）に向かう辺（のみ）がある．
- 終局に対応する状態は葉となる．
という木構造です．この木の各頂点に対して，「そこ（に対応する盤面）から始めて両者が最適にプレイしたときの先手の最大得点」を求めれば，根の値を読むことで先手の最大得点が分かります．各頂点の値を求める方法として Minimax 法というのがあります．これまたざっくり言えば，
- 葉の値はゲームルールから定まる．
- 内部ノードの値は先手番か後手番かによって次のように決定する．
- 先手番のとき，遷移先すべての頂点の値の内の最大値とする．
- 後手番のとき，遷移先すべての頂点の値の内の最小値とする（先手にとっての損の最大化）．
というものです．
こうして得られる「初期状態から得られる先手の得点の最大値」を $s$ とすれば，後手にとっての最大得点は $\sum A - s$ と求まるので，両者を比較することで勝敗を決定できます．なお，（プレミによって？）Tic-tac-toe の勝敗で決まるような状態については得点を $\infty$ や $-\infty$ とすることで処理を統一できます．
計算量については上の方で書いたように，状態数の最大である $9!$ に，各盤面でかかるステップ数（$3 \times 3 = 9$ の定数倍ぐらい）をかけたものが上界となります．盤面サイズを変数にしたりして無理くりオーダー表記する意味はあまり無い気がするので，それはやりません．
コード
以下の実装はコンテスト中に書いたものがベースですが，状態数の上界を $9^9$ とガバガバに見積もったのでメモ化をしています．やらなくても通りますが，実行時間は $30$ 倍ぐらい違います．
constexpr auto INF = LIM< LL >::max() / 2; LL dp[ 1 << 18 ]; bool visited[ 1 << 18 ]; VVI decode( const int state ) { const int colored = state >> 9; const int red = state & 0x1FF; VVI res( 3, VI( 3 ) ); REP( i, 9 ) { if ( colored & 1 << i ) { res[ i / 3 ][ i % 3 ] = red & 1 << i ? 1 : 2; } } return res; } LL score( const VVI &A, const VVI &C ) { LL s = 0; VVI counts( 3, VI( 8 ) ); REP( i, 3 ) { REP( j, 3 ) { if ( C[i][j] == 1 ) { s += A[i][j]; } ++counts[ C[i][j] ][i]; ++counts[ C[j][i] ][ 3 + i ]; } ++counts[ C[i][i] ][6]; ++counts[ C[ 2 - i ][i] ][7]; } if ( find( ALL( counts[1] ), 3 ) != end( counts[1] ) ) { return INF; } else if ( find( ALL( counts[2] ), 3 ) != end( counts[2] ) ) { return -INF; } return s; } LL minimax( const VVI &A, const int state ) { if ( visited[ state ] ) { return dp[ state ]; } visited[ state ] = true; const int colored = state >> 9, red = state & 0x1FF; const VVI C = decode( state ); if ( const LL s = score( A, C ); abs( s ) == INF || colored == 0x1FF ) { return dp[ state ] = s; } const int T = __builtin_popcount( colored ) % 2; dp[ state ] = T == 0 ? -INF : INF; REP( i, 9 ) { if ( colored & 1 << i ) { continue; } const int ncolord = colored | 1 << i; const int nred = T == 0 ? red | 1 << i : red; const int nstate = ( ncolord << 9 ) | nred; if ( T == 0 ) { chmax( dp[ state ], minimax( A, nstate ) ); } else { chmin( dp[ state ], minimax( A, nstate ) ); } } return dp[ state ]; } int main() { const int H = 3, W = 3; VVI A( H, VI( W ) ); cin >> A; LL s = 0; FOR( row, A ) { s += accumulate( ALL( row ), 0LL ); } const LL takahashi = minimax( A, 0 ); const LL aoki = s - takahashi; cout << ( takahashi > aoki ? "Takahashi" : "Aoki" ) << endl; return 0; }
*1:そのためにはその他の局面での最適手も必要になりますが．
