ABC025 C : 双子と○×ゲーム
http://abc025.contest.atcoder.jp/tasks/abc025_c
競プロの問題を解き始めた頃に解けなかった問題だったので、すんなり解けて安心しました。
二人対戦ゲームの問題で、min-max法を使ってときます。このとき、直大くんの点が分かれば直子さんの点もわかるとか、選べる手が一種類しかないなどの初心者用安心仕様になっているのでそれらの点に気をつけてメモ化再帰をします。再帰には簡便のためturnを渡していますが、「選べる手が決まっている」「先手が決まっている」という情報があるので、○×ゲームを書いている紙(?)だけでメモに必要な情報は足りています。なのでmapに配列を渡してメモにしました。もっと状態が多いとマップだと重いのでビット列等にエンコードして配列に入れたりすると良さそうですが、まあ普通に大丈夫ですね。
typedef vector<vector<int> > mat; int b[2][3], c[3][2]; map<mat, int> memo; int calc_point(mat fld){//直大くんの得点だけ計算 int res = 0; rep(i, 2) rep(j, 3) if(fld[i][j] == fld[i + 1][j]) res += b[i][j]; rep(i, 3) rep(j, 2) if(fld[i][j] == fld[i][j + 1]) res += c[i][j]; return res; } int dfs(mat fld, int turn){ if(turn == 9) return memo[fld] = calc_point(fld); if(memo.count(fld)) return memo[fld]; int tm = turn % 2; int res = tm ? INF : -1; rep(i, 3) rep(j, 3){ if(fld[i][j] != -1) continue; mat temp = fld; temp[i][j] = tm; if(tm) res = min(res, dfs(temp, turn + 1)); else res = max(res, dfs(temp, turn + 1)); } return memo[fld] = res; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int sum = 0; rep(i, 2) rep(j, 3){ cin >> b[i][j]; sum += b[i][j]; } rep(i, 3) rep(j, 2){ cin >> c[i][j]; sum += c[i][j]; } mat fld(3, vector<int>(3, -1)); int ans = dfs(fld, 0); cout << ans << endl; cout << sum - ans << endl; return 0; }
前はこういう問題がすごく苦手だったのですが、最近メモ化再帰が好きです(できるとは言っていない)。木のてっぺん(根)を与えると下から計算してくれるというのがとてもきれいだし、
return memo[hoge] = res;
というのがなんとなく好きです。ただ下から計算しなくてもいい問題(遷移がわりと自明な問題)は普通にループでいっかなってなっちゃいますね。