AOJ 2741 D - インビジブル

AOJ 競技プログラミング

確かに、確かに大事なんですがね？
★つくのか～これ。

問題

インビジブル | Aizu Online Judge

感想

問題文を４回くらい読みましょう。分かりつらい。

サンプル2を見てみるとすっごい悩みますが、おそらくこれは最初っからどちらもパスして終わる or どちらも一枚ずつ出したのちパスして終わる感じなのかな？

さて、方針ですが、「プレイヤーは二人ともすべてのカードが見えている(これ大事)」ので、すべての可能性を探索したのち、行動ができます。(できます、じゃないんだよなあ、私は出来ません)

したがって、

「各状態で、今手番のプレイヤーがカードを置いた時と、パスしたときの結果を両方見て、大きいほうを選ぶ。」

というdfsを書きます。n,mは50までと小さいので適当に描いても大丈夫そうです(私は係数の小さいO(n^5)くらい))(適当に書くとバグります)

気を付けるべき個所は

  • スタックに何もない状態で二人ともパスするとゲームが終わる。
  • -1のカードを置くとそれより下においてある相手のカードは無効になる。

という二点、

dp[type][x1][y1][x2][y2] := 状態がtypeで、プレイヤー１のx2枚目、プレイヤー２のy2枚目からスタックにおいてあり、プレイヤー１がx1枚目、プレイヤー２がy1枚目まで場に出した時から始めた際の答え。(1-index)

でメモ化をしました。

typeに関しては0がプレイヤー1の手番、1がプレイヤー2の手番、2がストックに一枚もない状態でプレイヤー2がパスをしたのちのプレイヤー1の手番、3がストックに一枚もない状態でプレイヤー1がパスしたのちのプレイヤー2の手番です。

答えはdp[0][0][0][0][0]です。

実装力ー

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG_MODE
    #define DBG(n) n;
#else
    #define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
 
typedef long long ll;
typedef pair<ll,ll> P;
 
ll dp[4][55][55][55][55];
ll n,m;
vector<ll> a;
vector<ll> b;
 
ll check(ll hoge,ll x1,ll y1,ll x2,ll y2){
    ll ret = 0;
    for(ll i = x1-1;i >= x2;i--){
        if(a[i] != -1)ret += a[i];
    }
    for(ll i = y1-1;i >= y2;i--){
        if(b[i] != -1)ret -= b[i];
    }

    return ret;
}
 
ll dfs(ll type,ll x1,ll y1,ll x2,ll y2){
    if(dp[type][x1][y1][x2][y2] != LLINF)return dp[type][x1][y1][x2][y2];
    ll ret;
    //A
    if(type % 2 == 0){
        ret = -LLINF;
        //置く
        if(x1 < n){
            if(a[x1] == -1){
                ret = max(ret,dfs(1,x1+1,y1,x2,y1));
            }
            else{
                ret = max(ret,dfs(1,x1+1,y1,x2,y2));
            }
        }
        //置かない
        if(type == 2)ret = max(ret,0LL);
        else if(x1 == x2 && y1 == y2){
            ret = max(ret,dfs(3,x1,y1,x2,y2));
        }
        else{
            ll tmp = check(type,x1,y1,x2,y2);
            ret = max(ret,dfs(1,x1,y1,x1,y1)+tmp);
        }
    }
    //B
    else{
        ret = LLINF;
        //置く
        if(y1 < m){
            if(b[y1] == -1){
                ret = min(ret,dfs(0,x1,y1+1,x1,y2));
            }
            else{
                ret = min(ret,dfs(0,x1,y1+1,x2,y2));
            }
        }
        //置かない
        if(type == 3)ret = min(ret,0LL);
        else if(x1 == x2 && y1 == y2){
            ret = min(ret,dfs(2,x1,y1,x2,y2));
        }
        else{
            ll tmp = check(type,x1,y1,x2,y2);
            ret = min(ret,dfs(0,x1,y1,x1,y1)+tmp);
        }
    }
     
    return dp[type][x1][y1][x2][y2] = ret;
}
 
int main(){
     
    cin >> n >> m;
    REP(i,n){
        ll tmp;cin >> tmp;a.PB(tmp);
    }
    REP(i,m){
        ll tmp;cin >> tmp;b.PB(tmp);
    }
     
    REP(i,55)REP(j,55)REP(k,55)REP(l,55){
        dp[0][i][j][k][l] = LLINF;
        dp[2][i][j][k][l] = LLINF;
        dp[1][i][j][k][l] = LLINF;
        dp[3][i][j][k][l] = LLINF;
    }
     
    cout << dfs(0,0,0,0,0) << endl;
 
    return 0;
}

なぜdpの初期化こんな書き方しているの？
添え時に困ったからです(これは罠で、最初初期化の値がtypeによって違っていた(結局取りえない値であればよいことに気がついた))