perogram

C - 双子と○×ゲーム abc025_c

Quiz

https://atcoder.jp/contests/abc025/tasks/abc025_c

Submit

https://atcoder.jp/contests/abc025/submissions/4408334

Note

片方がスコアを最大にしようと動き、もう片方がスコアを最小にしようと動くとき、ミニマックス法で先読みする
- Wikipedia参照

書き方

1つの書き方ではあるが、私はdfsで書いた
最初は盤面が全て未決定の状態

* * *
* * * 
* * *

そこから1つ○をつけて次のdfsに渡す

* * *
* * o
* * *

この全てのシミュレーションをどう書くかは、以下のようにした
- 盤面を1コマ書き換える
- 1ステップ進んだ状態で再度dfsを呼ぶ
- dfsから戻ってきたら盤面を戻す
対応するコードは以下

    // chokudai's turn
    if(step%2==1){
        ll max_score = -inf;
        FOR(i, 0, 3){
            FOR(j, 0, 3){
                if(G[i][j]=='*'){
                    G[i][j] = 'o';
                    ll score = dfs(step+1);
                    max_score = max(max_score, score);
                    G[i][j] = '*';
                }
            }
        }
        ret = max_score;
    }

dfsではお決まりだが、最終盤面を終端として止まるようにしておく

最後にスコア分解

ここはちょっと見苦しい
score = 直大スコア - 直子スコア
として進めてきたが、提出すべきは双方のスコア
各コードをpair版にしてもいいが、最終盤面のパターンは雑に作っても2⁹なので、全て作ってscoreと比較
一致すればその盤面で双方のスコアを求めて提出、とした

学び

ミニマックス法を使った全探索

感想

C問題にしては難しい？
慣れている人(writer)はdfsを書くのにも慣れているので、簡単に思えるのかもしれない

Code

#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

ll B[2][3];
ll C[3][2];
char G[3][3];

pair<ll, ll> final_pair(){
    // point
    ll man = 0;
    ll woman = 0;

    FOR(i, 0, 3){
        FOR(j, 0, 3){
            char c = G[i][j];
            if(c!='o' && c!='x'){
                return {-1, -1};
            }
        }
    }

    // B
    FOR(i, 0, 2){
        FOR(j, 0, 3){
            if(G[i][j]==G[i+1][j]){
                man += B[i][j];
            }else{
                woman += B[i][j];
            }
        }
    }

    // C
    FOR(i, 0, 3){
        FOR(j, 0, 2){
            if(G[i][j]==G[i][j+1]){
                man += C[i][j];
            }else{
                woman += C[i][j];
            }
        }
    }

    return {man, woman};
}

ll final_score(){
    auto p = final_pair();
    return p.first - p.second;
}

ll dfs(ll step){
    if(step==10){
        return final_score();
    }

    ll ret;
    
    // chokudai's turn
    if(step%2==1){
        ll max_score = -inf;
        FOR(i, 0, 3){
            FOR(j, 0, 3){
                if(G[i][j]=='*'){
                    G[i][j] = 'o';
                    ll score = dfs(step+1);
                    max_score = max(max_score, score);
                    G[i][j] = '*';
                }
            }
        }
        ret = max_score;
    }

    // naoko's turn
    else{
        ll min_score = inf;
        FOR(i, 0, 3){
            FOR(j, 0, 3){
                if(G[i][j]=='*'){
                    G[i][j] = 'x';
                    ll score = dfs(step+1);
                    min_score = min(min_score, score);
                    G[i][j] = '*';
                }
            }
        }
        ret = min_score;
    }

    return ret;
}

// final scoreを与えたときのchokudai's score, naoko's scoreを返す
pair<ll, ll> devide(ll score){
    // 盤面総当たり
    FOR(f, 0, 1<<9){
        ll man = 0;
        ll woman = 0;

        FOR(keta, 0, 9){
            ll i = keta / 3;
            ll j = keta % 3;
            if(f >> keta & 1){
                G[i][j] = 'o';
                man++;
            }else{
                G[i][j] = 'x';
                woman++;
            }
        }

        if(man==5 && woman==4){
            if(score == final_score()){
                return final_pair();
            }
        }
    }
    return {-1L, -1L};
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    FOR(i, 0, 2){
        FOR(j, 0, 3){
            cin >> B[i][j];
        }
    }

    FOR(i, 0, 3){
        FOR(j, 0, 2){
            cin >> C[i][j];
        }
    }

    FOR(i, 0, 3){
        FOR(j, 0, 3){
            G[i][j] = '*';
        }
    }
    
    ll score = dfs(1);
    
    auto p = devide(score);
    p(p.first);
    p(p.second);
    
    return 0;
}