ACM-ICPC 2016 Asia Tsukuba Regional, K 解法

K: Black and White Boxes

問題

アリスとボブがゲームをする。
箱が縦に一列に積み上げられており、各箱の色は白か黒である。この一列を山と呼び、山が複数ある。二人で交互に箱を取り除く。

  • アリスは黒箱を1つ選んで、その箱とその上に積んであるすべての箱を取り除く。
  • ボブは白箱を1つ選んで、その箱とその上に積んであるすべての箱を取り除く。
  • 自分の手番で取り除くことができなくなったら負け。
  • 二人は勝つために最適な行動をする。

先手のプレイヤーを任意にした場合、アリスにもボブにも勝つ可能性があるようなゲームはfairであるという。

n個の山が与えられるのでその中から0個以上選択してfairなゲームを見つけ、fairなゲームの初期状態の箱の数の最大値を求めよ。

制約

山の数 n <= 40
一つの山の箱の数 p_i <= 40

解法

先に計算方法だけ述べる。

  • 山に箱がなかったら0点
  • 一番下の箱から同色の箱が1個以上連続していたら、それぞれ1点
  • 下から、初めて色が変わった箱は1/2点。以降の箱は直下の箱の1/2倍の点。
  • 黒箱はマイナス、白箱はプラスとして、合計が山の点数。
  • 山の点数の総和がゲーム全体の点数。

ゲームの点数が

  • 0: 後手必勝
  • 正: 白必勝
  • 負: 黒必勝

f:id:natsugiri:20161023160401p:plain
各山は(山の点数, 箱の数) の形に消化され、山の点数の和が0に成るようにナップザック問題を解く。山は40以下なので、半分全列挙が適している。


以下考察。
このゲームはHackenbushと言う有名ゲームで特にBlue-Red Hackenbushと呼ばれるバリエーションである。その中で、パスグラフに限定されたものとして出題されている。
ゲームの状態は一つのSurreal Number (サーリアルナンバー)に写され、Surreal Numberは実数に写される。この実数がゲームの点数である。
引き分け・無限ループのない二人零和有限確定完全情報ゲームは先手必勝・後手必勝・左必勝 (アリス必勝)・右必勝(ボブ必勝)の4通りの状態がある。Blue-Red Hackenbushはこの内、後手必勝・アリス必勝・ボブ必勝の3通りだけのゲームである。

考察はいくつか仮定しながら小さい盤面を書き下すしか無いように思える。
まずGrundy数に還元できるか考える。問題文中に先手後手関係なく片方のプレイヤーが必勝の場合があると述べられているのでGrundy数には還元できない。

問題文でチェスについて触れられているので、一般的なチェスエンジン同様に

  • 0: 同等
  • 正: 白有利
  • 負: 黒有利

と評価する。また

  • 箱が無いなら0点
  • 白箱1つなら1点
  • 黒箱1つなら-1点
  • 箱の並びが同じ山は同じ点数
  • 色が全て逆の山は、互いに逆の符号の点数
  • 山が複数あるときは和を取って点数とする

も、自然に思いつく。最後の和を取る評価は全く正しいかどうかこの時点ではわからないが2つの山の色が互いに逆であればfairになることから予想することは可能。
このゲームは自分の手番では、自分のできる手を減らすことに成るので、手番を行うとゲームの状態が自分にとって悪くなる(ただし、手番を相手に与えるのは良いこと)。よって、あるゲームの点数は白が1手進めた状態以上、黒が1手進めた状態以下の値にすべきである。
以上の考察を以て小さいケースと、重大なヒントであるサンプル1のfair状態を眺めると、下から2段めが1/2に成ることが分かる。
先手後手を無視して評価するのがやや思いつきにくいか。

コード

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

int N;
pair<double, int> P[44];
char S[44];

vector<pair<double, int> > calc(pair<double, int> *P, int N) {
    vector<pair<double, int> > ret;
    ret.push_back(make_pair(0, 0));

    REP (i, N)
	REP (j, ret.size())
	    ret.push_back(make_pair(ret[j].first + P[i].first, ret[j].second + P[i].second));

    sort(ret.begin(), ret.end());
    return ret;
}

int main() {
    scanf("%d", &N);
    REP (i, N) {
	scanf("%s", S);
	int L = strlen(S);

	double ac = 0, d = 1, x = 1;
	REP (j, L) {
	    if (j && S[j] != S[j-1]) d = 2;
	    x /= d;
	    ac += (S[j] == 'W'? 1: -1) * x;
	}

	P[i] = make_pair(ac, L);
    }

    vector<pair<double, int> > le = calc(P, N / 2);
    vector<pair<double, int> > ri = calc(P + N / 2, N - N / 2);
    int ans = 0;

    for (int i=0, j=ri.size()-1; i<(int)le.size(); i++) {
	while (j > 0 && le[i].first + ri[j].first > 0) j--;
	if (le[i].first + ri[j].first == 0) amax(ans, le[i].second + ri[j].second);
    }

    printf("%d\n", ans);

    return 0;
}

感想

この問題は広義に既出である。
前半のゲームパートは勝敗判定のみであるが例えばcodechef Contest Page | CodeChef で出題された。
後半のナップザックパートは例えばatcoder D: ナップサック問題 - AtCoder Beginner Contest 032 | AtCoder で出題された。
ただしHackenbushとナップザックを混ぜた問題は見たこと無いので革新的な問題である。
Hackenbushといえば今年3月にHackerrankで出題されたのが記憶に新しいが、そのときはGreen Hackenbushというバリエーションで、本問の考察とは全く関係ない。しかしゲームに興味を持つには十分な内容である。
Blue-Red Hackenbushは根付き木でもO(n * (実数の精度と相談))時間で計算可能であるので復習するとよい。