JAG Contest 2016 Domestic D - インビジブル

jag2016-domestic.contest.atcoder.jp

問題文

省略

解法(反転して表示)

よくあるゲーム木のmin-max探索，後手は差を最小化，先手は差を最大化するように実装する． 状態数がどれくらいになるのかを見積もるのが本質． 実際山札の残り枚数と，どの区間(※)がスタックに残ってるかみたいなのを考えると，状態として O(NM*(N+M)²)程度しか無い．実際はパスの回数とかどっちのターンかみたいな状態も持つんだけど，それはとても小さい定数倍だからまあ問題ない． 実装を複雑化させないために構造体とmapを用いて実装したので重いけど通る．

(※) 手札の引き方はパスを無視すれば一意で，a_1b_1a_2b_2 ,...というふうな列になるので，この列の区間を考える．

「スタックが空になってから」パスを2回が終了条件な注意しないとWAする．

ソース

#include <bits/stdc++.h>
using namespace std;
 
 
 
struct State{
    vector<int> p1,p2;
    vector< pair<int,int> > stack;
    int turn;
    int passed;
};
bool operator < (const State &a,const State &b){
    if( a.passed != b.passed ) return a.passed < b.passed;
    if( a.turn != b.turn ) return a.turn < b.turn;
    
    if( a.p1 != b.p1 ) return a.p1 < b.p1;
    if( a.p2 != b.p2 ) return a.p2 < b.p2;
    return a.stack < b.stack;
}
 
map<State,int> memo;
int dfs(const State s){
    if( s.passed == 2 ) return 0;
    if( memo.count(s) ) return memo[s];
    int ans;
    if( s.turn == 0 ){
        ans = -1e9;
        if( s.p1.size() ){
            State cpy = s;
            cpy.stack.push_back({cpy.p1.back(),s.turn});
            cpy.p1.pop_back();
            cpy.passed = 0;
            cpy.turn ^= 1;
            ans = max(dfs(cpy),ans);
        }
        {
            State cpy = s;
            int profit = 0;
            int coef1 = 1;
            int coef2 = 1;
            for(int i = cpy.stack.size() - 1 ; i >= 0 ; i--){
                if( cpy.stack[i].second != s.turn &&  cpy.stack[i].first == -1 ) coef1 = 0;
                if( cpy.stack[i].second == s.turn &&  cpy.stack[i].first == -1 ) coef2 = 0;
                
                if( cpy.stack[i].second == s.turn &&  cpy.stack[i].first != -1 )
                    profit +=  coef1 * cpy.stack[i].first;
                if( cpy.stack[i].second != s.turn &&  cpy.stack[i].first != -1 )
                    profit -=  coef2 * cpy.stack[i].first;
            }
            if( cpy.stack.size() == 0 ) cpy.passed++;
            cpy.stack.clear();
            cpy.turn ^= 1;
            ans = max(dfs(cpy)+profit,ans);
        }
    }else{
        ans = +1e9;
        if( s.p2.size() ){
            State cpy = s;
            cpy.stack.push_back({cpy.p2.back(),s.turn});
            cpy.p2.pop_back();
            cpy.passed = 0;
            cpy.turn ^= 1;
            ans = min(dfs(cpy),ans);
        }
        {
            State cpy = s;
            int profit = 0;
            int coef1 = 1;
            int coef2 = 1;
            for(int i = cpy.stack.size() - 1 ; i >= 0 ; i--){
                if( cpy.stack[i].second != s.turn &&  cpy.stack[i].first == -1 ) coef1 = 0;
                if( cpy.stack[i].second == s.turn &&  cpy.stack[i].first == -1 ) coef2 = 0;
                
                if( cpy.stack[i].second == s.turn &&  cpy.stack[i].first != -1 )
                    profit +=  coef1 * cpy.stack[i].first;
                if( cpy.stack[i].second != s.turn &&  cpy.stack[i].first != -1 )
                    profit -=  coef2 * cpy.stack[i].first;
            }
            if( cpy.stack.size() == 0 ) cpy.passed++;
            cpy.stack.clear();
            cpy.turn ^= 1;
            ans = min(dfs(cpy)-profit,ans);
            
        }
    }
    return memo[s] = ans;
    
}
 
int main(){
    int n,m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for(int i = 0 ; i < n ; i++) cin >> a[i];
    for(int i = 0 ; i < m ; i++) cin >> b[i];
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    
    State s = {a,b,{},0,0};
    cout << dfs(s) << endl;
    
}