問題

インビジブル | Aizu Online Judge

2人でカードゲームをする。各々デッキを持つ。カードには数字がかかれている。-1は妨害カードで、それ以外は正の得点となるカードである。2人は交互にプレイする。プレイヤーは、カードを場のスタック上に置くか、パスするかの選択肢を取れる。パスした場合、相手の置いた妨害カードの上の自分の全てのカードの和を得点として得ることが出来る。スタックに何も置かれていない状態から、2人がパスした場合にゲーム終了となる。2人とも出せるカードがなくなった場合もゲーム終了である。プレイヤーは、自分の得点から相手のプレイヤーの得点を引いた値を最大化しようとする。互いに最適な行動を取った場合、プレイヤー1の得点からプレイヤー2の得点を引いた値を求めよ。

$1\le n,\ m\le 50$

解法

2人のゲームで得点の最大化をするので、ミニマックス法のメモ化再帰をする解法をとる。パスしたときに得点として加算され、それまでは妨害カードがいかなるタイミングで置かれるかわからないため、場のスタックの状態を何らかの形で持てるようにしたい。自分のカードと相手のカードを混ぜて一つのスタックの配列のようなものに記憶する必要はなく、自分のデッキのどこからどこまでの範囲のカードを場に出しているかと、相手のデッキのどこからどこまでの範囲のカードを場に出しているかとが分かれば、場のスタックの状態が分かることになる。実際、パスしたときに得点に影響するのは、スタックに置いた自分のカードと相手の妨害カードなので、各人のデッキのどの範囲をスタックにおいているかを考えたほうが都合が良い。このようにスタックに置いたデッキの範囲を持つと、パスのタイミングで得られる得点は累積和の差分で計算できる。

メモ化再帰のコードは自分と相手で分析して書く方法があるが、自分と相手でやっていることが変わらないので、rec(p1, p2, ...) -> rec(p2, p1, ...) のように状態をひっくり返して記述する方法が書きやすい。

メモ化再帰中で考えるべき選択肢に「パス」と「カードを置く」がある。

「パス」には2つの処理がある - 各々のプレイヤーがスタックに出しているデッキの範囲を得点化 - デッキの範囲をクリアする処理

得点化する処理は、+ (自分のデッキの範囲の累積和の差分) - (相手のデッキの範囲の累積和の差分) を与えることで計算できる。

また、スタックが空の状態で2人がパスした場合ゲーム終了なので、パスの数を数えておいて、回数が3回目に突入した段階で、以後得点の変動はなく再帰計算が終了する。

「カードを置く」について、以下の2択がある。 - 得点カードを出す - 妨害カードを出す

「カードを置く」は「パス」とは異なり自分のまだスタックに出していないカードがあるときでないと実行できない。

妨害カードは以下のように考えることが出来る。 - 相手のデッキの範囲を帳消しにする

妨害カードの得点を0としておくと、妨害カードを置いた人の得点計算に都合が良い。こうすることで妨害カードを置くタイミングで得点計算をする必要がなく、あくまでパスのタイミングのみで得点計算すればよくなる。

状態は以下のようにすれば良い。

(自分のL, 自分のR, 相手のL, 相手のR, どちらの手番か, 連続パス回数)

#include <bits/stdc++.h>
 
using namespace std;
int const MAX = 55;
 
int n[2];
int deck[2][MAX];
int sum[2][MAX];
  
int dp[MAX][MAX][MAX][MAX][2][4];
bool used[MAX][MAX][MAX][MAX][2][4];
 
int rec(int l1, int r1, int l2, int r2, int which, int pass) {
 
  auto& ret = dp[l1][r1][l2][r2][which][pass];
 
  if(used[l1][r1][l2][r2][which][pass]) return ret;
  used[l1][r1][l2][r2][which][pass] = 1;
 
  if(pass == 3) {
    return ret = 0;
  }
 
  // pass
  ret = -rec(r2, r2, r1, r1, !which, pass + 1)
        + (sum[which][r1] - sum[which][l1])
        - (sum[!which][r2] - sum[!which][l2]);
 
  if(r1 == n[which])
    return ret;
 
  if(deck[which][r1] != -1)
    ret = max(ret, -rec(l2, r2, l1, r1 + 1, !which, 0));
  else
    ret = max(ret, -rec(r2, r2, l1, r1 + 1, !which, 0));
 
  return ret;
}
  
int main() {
 
  for(int i=0; i<2; i++)
    cin >> n[i];
 
  for(int i=0; i<2; i++)
    for(int j=0; j<n[i]; j++)
      cin >> deck[i][j];
 
  for(int i=0; i<2; i++) {
    sum[i][0] = 0;
    for(int j=0; j<n[i]; j++) {
      int point = deck[i][j];
      if(point == -1) point = 0;
      sum[i][j + 1] = sum[i][j] + point;
    }
  }
 
  cout << rec(0, 0, 0, 0, 0, 0) << endl;
 
  return 0;
}

感想

書き方にだいぶ悩んで、いい感じの書き方を他の人から参考にしたら急に明快になりました（解法の説明は煩雑ですが）。

Logfiles

AOJ2741 Invisible

問題

解法

感想