問題

C: 双子と○×ゲーム - AtCoder Beginner Contest 025 | AtCoder

解答

全探索またはメモ化DPする。 (現在どちらのターンか, ターン数) を引数にして、直大または直子の点数を最大化する。状態の引数より、メモ化で $O(2^ N)$ で解ける。本問題は状態数が少ないので、メモ化せずに $O(N!)$ でも解ける。再帰関数の戻り値はstd::pair<int, int>としたが、直大を最大化、直子を最小化とすれば1変数で可能。

int B[2][3], C[3][2];
int board[3][3];

pair<int, int> dfs(bool is_man, int cnt) {
  if (cnt == 9) {
    int man = 0, woman = 0;
    rep(i, 2) rep(j, 3) {
      (board[i][j] == board[i + 1][j] ? man : woman) += B[i][j];
    }
    rep(i, 3) rep(j, 2) {
      (board[i][j] == board[i][j + 1] ? man : woman) += C[i][j];
    }
    return {man, woman};
  }

  pair<int, int> ret = {-1, -1};
  rep(i, 3) rep(j, 3) {
    if (board[i][j] == -1) {
      board[i][j] = is_man;
      auto r = dfs(!is_man, cnt + 1);
      if (ret.first < 0) {
        ret = r;
      } else {
        bool cond = is_man ?
          ret.first < r.first : ret.second < r.second;
        if (cond) {
          ret = r;
        }
        cond = is_man ?
          (ret.first == r.first && ret.second > r.second) :
          (ret.second == r.second && ret.first > r.first);
        if (cond) {
          ret = r;
        }
      }
      board[i][j] = -1;
    }
  }
  return ret;
}

int main() {
  rep(i, 3) rep(j, 3) board[i][j] = -1;
  rep(i, 2) rep(j, 3) cin >> B[i][j];
  rep(i, 3) rep(j, 2) cin >> C[i][j];
  auto r = dfs(true, 0);
  std::cout << r.first << "\n" << r.second << "\n";
}