ところでint memo[2][51][51][51][51][3];みたいなのの初期化をrep (p,2) rep (i,50) rep (j,50) rep (k,50) rep (l,50) rep (q,3) { ... }とするとWAる。気付きにくい。

## solution

メモ化全探索。$O(N^2M^2)$。

## implementation

#include <iostream>
#include <vector>
#include <map>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
struct state_t {
vector<int> const & deck;
int used;
int stack;
};
bool operator < (state_t const & s, state_t const & t) {
return make_tuple(&s.deck, s.used, s.stack) < make_tuple(&t.deck, t.used, t.stack);
}
int score(state_t const & s) {
int acc = 0;
repeat (i, s.stack) {
int card = s.deck[s.used-1 - i];
if (card != -1) acc += card;
}
return acc;
}
const int inf = 1e9+7;
typedef tuple<state_t, state_t, int> key_type;
int dfs(state_t const & s, state_t const & t, int pass_count, map<key_type,int> & memo) {
auto key = make_tuple(s, t, pass_count);
if (memo.count(key)) return memo[key];
int use_score = - inf;
if (s.used < s.deck.size()) {
state_t ns = { s.deck, s.used + 1, s.stack + 1 };
state_t nt = { t.deck, t.used, s.deck[s.used] == -1 ? 0 : t.stack };
use_score = - dfs(nt, ns, 0, memo);
}
int pass_score;
if (pass_count + 1 == 3) {
pass_score = 0;
} else {
state_t ns = { s.deck, s.used, 0 };
state_t nt = { t.deck, t.used, 0 };
pass_score = score(s) - score(t) - dfs(nt, ns, pass_count + 1, memo);
}
return memo[key] = max(use_score, pass_score);
}
int main() {
int n, m; cin >> n >> m;
vector<int> a(n); repeat (i,n) cin >> a[i];
vector<int> b(m); repeat (i,m) cin >> b[i];
state_t s = { a, 0, 0 };
state_t t = { b, 0, 0 };
map<key_type,int> memo;
int ans = dfs(s, t, 1, memo);
cout << ans << endl;
return 0;
}