SRM 511 500pt: FiveHundredEleven

TopCoder

問題概要

カードがN(<50)枚あって、0~511(B=512とおこう)までの数字が書いてある。メモリ上の数字が初め0で、プレイヤー２人は交互にカードをめくってメモリ上の数字にカードの数字をor演算で被せていく。カードが引けなくなったプレイヤー、もしくはメモリを511にしてしまったプレイヤーが負けとなる。最善を尽くしたとき勝つのは先手か後手かを求める問題。

後から考えたこと

  • この問題は本番中解けなかったので、大体の解法(メモ化のキーをどうするか)を知った後で解きなおした。
  • 本番中は、状態が(メモリの値, どのカードを使ったか)だと全然間に合わないとか考えていた記憶がある。
  • 改めて考えると、メモリの値が決まったら、そのビット列に包含されないカードは絶対に使ってないと決定できる。
    • 例えば、メモリの値が0b01101のときに0b00110がまだ使われていないということは自明。
  • で、既に使ったものに関しては、パス相当になるカードを区別する必要が無いので、そういうカードについては毎数だけ覚えていればよい。
    • 例えば、メモリの値が0b01101のときに、0b01001と0b01100を区別する必要はない。どちらのカードも同じパス券でしかない。
  • なので、状態を(メモリの値、未使用なパス券の枚数)にしておけば、計算量O(B*N^3)で解ける。何故なら状態数B*Nで、ある状態からの遷移がN通りあって、新しい状態を計算するのにNかかるから。
  • これでもぎりぎり間に合うけど、実際はもう少し状態数を減らせる。
  • パス券を使って、パス券の枚数が偶数->奇数となるような遷移は考える必要がないことが分かる。
    • 何故なら、その場合相手がパス券を次のターンで使ってこられると意味が無いから。
  • なので、状態は(メモリの値、未使用なパス券の枚数の偶奇)だけでよくて、計算量O(B*N^2)で解ける。

メモ化解法

計算量O(B*N^2)。

#include <vector>
#include <algorithm>
#include <string>
using namespace  std;

const int MAX_N = 512;

bool visited[MAX_N][2];
bool win[MAX_N][2];
vector<int> cards;
int N;

struct FiveHundredEleven {

	string theWinner(vector <int> _cards) {
		cards = _cards;
		N = cards.size();
		return rec(0, count(cards.begin(), cards.end(), 0)&1)?"Fox Ciel":"Toastman";
	}

	//(メモリの状態、　パスが何回できるか)を状態とする
	bool rec(int bit, int parity){

		//メモ化処理
		if(visited[bit][parity]){
			return win[bit][parity];
		}
		visited[bit][parity] = true;

		//メモリが511の状態で回ってきたら勝ち
		if(bit==511){
			return win[bit][parity] = true;
		}

		//パスすることで勝てるかどうか
		if(parity && !rec(bit,0)){
			return win[bit][parity] = true;
		}

		//新しくビットが立つようなのを集める
		vector<int> progress;
		for(int i=0; i<N; i++)if(!is_included(cards[i], bit)){
			progress.push_back(cards[i]);
		}

		//パス以外の遷移を調べる
		for(int i=0; i<(int)progress.size(); i++){
			int new_bit = progress[i] | bit;
			int new_parity = parity;
			for(int j=0; j<(int)progress.size(); j++)if(i!=j && is_included(progress[j], new_bit)){
				new_parity++;
			}
			if( !rec(new_bit, new_parity&1) ){
				return win[bit][parity] = true;
			}
		}

		return win[bit][parity] = false;
	}

	//a が bの部分集合かどうか
	bool is_included(int a, int b){
		return (b | a) == b;
	}

};

今見返したら変数名のMAX_Nは無いな。

DP解法

実際には組んでないけど、

for(int bit=511; bit>=0; bit--){
        for(int parity=0; parity<=1; parity++){
                ...
        }
}

の順で更新すれば良い。

バグを減らす工夫

  • メモ化再帰のときに、
  return memo[state] = ret;

派と、

  int &ret = memo[state];
     ...
  return ret;

派があって、今までは前者を採用していたんだけど、後者の方が便利な気がしてきた。

  • 理由は
    1. 毎回memo[state]と書くのが面倒。状態が複数の値のペアだったりすると面倒さ倍増。
    2. うっかり関数の中でstateの値を書き換えてしまうことがあるかもしれない。

他の人の解法

  • Petr先生のコードを見たら、状態を(メモリの数、今まで使ったカードの数)としていた。もちろんこれでも解けるし、アイデアとしてはこっちの方が自然に見える。
  • それだけじゃなくて、状態遷移がO(1)でできるから、状態数がO(B*N)でも全体の計算量がO(B*N^2)で済む。
  • さらにパリティを利用して、全体で計算量O(B*N)で済む。本当か？
  • 整理しよう。今回は状態を(メモリの値、経過ターン数の偶奇)として、全ての状態遷移をO(N)で計算すれば良い。
  • 書けた。確かにO(B*N)だ。
	string theWinner(vector <int> _cards) {
		cards = _cards;
		N = cards.size();
		return rec(0, 0)?"Fox Ciel":"Toastman";
	}

	//(メモリの状態、経過ターン数の偶奇)を状態とする
	bool rec(int bit, int parity){

		//メモ化処理
		if(visited[bit][parity]){
			return win[bit][parity];
		}
		visited[bit][parity] = true;

		bool &ret = win[bit][parity];
		int next_parity = parity ^ 1;

		//メモリが511の状態で回ってきたら勝ち
		if(bit==511){
			return ret = true;
		}

		//パス券の枚数を数える(使用済のも含む)
		int pass_count = 0;
		for(int i=0; i<N; i++)if(is_included(cards[i], bit)) pass_count++;

		//パスすることで勝てるかどうか
		if( (pass_count-parity)%2 != 0 && !rec(bit, next_parity)){
			return ret = true;
		}

		//新しくビットが立つようなのを集める
		vector<int> progress;
		for(int i=0; i<N; i++)if(!is_included(cards[i], bit)){
			progress.push_back(cards[i]);
		}

		//パス以外の遷移を調べる
		for(int i=0; i<(int)progress.size(); i++){
			int next_bit = progress[i] | bit;
			if( !rec(next_bit, next_parity) ){
				return ret = true;
			}
		}

		return ret = false;
	}