AtCoder Beginner Contest ABC025 C - 双子と○×ゲーム

C - 双子と○×ゲーム

問題へのリンク

解説

まず、置く順番は通りありますが、すべて試していいだろうとわかります。順列の列挙は、簡単に行う場合はnext_permutationを使いますが、今回は順列の生成とともにゲーム木を構成したいので、自前で実装します。基本的なDFSです。

木が構成されたとき、偶奇によって先攻と後攻どちらに意思決定権があるかが変わります。ゲーム木が葉までいったとき、順番が決まるわけですが、その順番で置いたときの先攻と後攻の得点を計算します。そして、意思決定権のある方の得点が最大になるような手のみを親に伝播させていくことで、最初にどちらの手を打つべきかがわかり、このゲームにおける最適な行動がわかるというわけです。

より簡単に考えると、2人の得点の和は一定なので、両方を保持する必要はなく、先攻の得点のみを記録し、先攻が決める場合は最大、後攻が決める場合は最小のように実装しても同様の結果になります。

以上のような実装で、計算回数は回ほどで終わり、間に合います。

実装

• 提出へのリンク

int b[10][10], c[10][10];
int d[10][10];
bool visited[10];
// 順列が与えられるので、計算する
i_i calc(vector<int> &v){
    int sz = v.size();// = 9
    rep(i,sz){
        int x = v[i] % 3;
        int y = v[i] / 3;
        d[x][y] = i&1;
    }
    int l = 0, r = 0;
    rep(i,2)rep(j,3){
        if(d[i][j] == d[i+1][j])l += b[i][j];
        else r += b[i][j];
    }
    rep(i,3)rep(j,2){
        if(d[i][j] == d[i][j+1])l += c[i][j];
        else r += c[i][j];
    }
    return make_pair(l,r);
}
i_i dfs(vector<int> &v){
    if(v.size() == 9)return calc(v);
    int sz = v.size();
    int maxx = -1;
    i_i res;
    rep(i,9){
        if(visited[i])continue;
        v.emplace_back(i);
        visited[i] = true;
        auto p = dfs(v);
        int l = p.first;
        int r = p.second;
        v.pop_back();
        visited[i] = false;
        if(sz&1){ // lをmaxにする手を選ぶ
            if(chmax(maxx, r))res = p;
        }
        else{ // rをmaxにする手を選ぶ
            if(chmax(maxx,l))res = p; 
        }
    }
    return res;
}
int main() {

    rep(i,2)rep(j,3)cin >> b[i][j];
    rep(i,3)rep(j,2)cin >> c[i][j];
    rep(i,10)visited[i] = false;
    vector<int> v;
    auto ans = dfs(v);
    cout << ans.first << endl;
    cout << ans.second << endl;
}