AtCoder Beginner Contest 270D

ABC270D
min-max法．
まず，簡単な問題を考える．何個取れるのかは無視して， 先手が必勝か必敗か引き分けかを判定する． 先に判定問題を解いて，それを改良する手法はよくある．

判定問題
:= (先手の取った石の個数) - (後手の取った石の個数)
を考える． 最善を尽くすとは，先手は を最大化して，後手は最小化すること． ゲームが終わった段階で なら先手必勝， なら必敗， なら引き分け，と判定できる．

最大値問題
判定問題では，最善を尽くしたときに という情報しか持っていないから，判定しかできなかった． そこで，先手の石の個数 と，後手の石の個数 も持っておくことにする． tuple を使って遷移する．
これが局面の情報になる． 2つのtuple に対する和を，成分毎の和と定義する．

今の局面をtuple とする．

• 先手が石 個とって局面が変化するということは， に を足すことにあたる．
• 後手が石 個とって局面が変化するということは， に を足すことにあたる．

あとは普通にmin-max．

使っている記号

using T = tuple<ll,ll,ll>;

T operator + (T a, T b){

  auto [x0,y0,z0] = a;

  auto [x1,y1,z1] = b;

  return make_tuple<ll,ll,ll>(x0+x1, y0+y1, z0+z1);

}

int main() {

  ll n, m, k, q;

  cin >> n >> k;

  vll a(k); rep(i,k) { cin >> a[i]; }

  vvll vis(n+1, vll(2));

  // T = <p, x, y>, p = x - y

  // お互い最善を尽くしたとき，先手がx個，後手がy個

  vector<vector<T>> memo(n+1, vector<T>(2));

  auto f = [&](auto f, ll rem, ll tu) -> T {

    if(rem == 0) return make_tuple<ll,ll,ll>(0,0,0);

    if(vis[rem][tu]) return memo[rem][tu];

    vis[rem][tu] = true;

    ll s = (tu == 0 ?  1: -1);

    T ret = make_tuple<ll,ll,ll>(s*(-INFL),0LL,0LL);

    rep(i,k){

      ll nr = rem - a[i];

      if(nr < 0) continue;

      if(tu == 0){

        T tup = {a[i], a[i], 0LL};

        chmax(ret, tup + f(f, rem-a[i], tu^1));

      }else{

        T tup = {-a[i], 0LL, a[i]};

        chmin(ret, tup + f(f, rem-a[i], tu^1));

      }

    }

    return memo[rem][tu] = ret;

  };

 

  auto [_,ans, __] = f(f, n, 0);

  cout << ans << endl;

 

  return 0;

}