SRM534 Div1 Easy(250), Div2 Medium(500) EllysCheckers

状態数が高々2²⁰通りなので、状態ごとに勝ち負けを覚えておいて、ゲーム木探索。

もっと簡単に解ける。@nico_shindannin さんの放送で聞いた解法。チェッカーが盤上に残っているのにゲームが終わることはない。また、チェッカーは常に奇数マス右に移動する。よって、それぞれのチェッカーと右端の距離を足し合わせて、偶奇を調べれば勝者が分かる。

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

int n;
vector<int> memo;

bool BT( int B )
{
    B &= ~1;

    if ( memo[B]!=-1 )
        return memo[B]!=0;

    bool ans = false;

    for ( int i=0; i<n; i++ )
    if ( B>>i&1 )
    {
        //  step
        if ( i>=1 && !(B>>(i-1)&1) && !BT(B^(1<<i)^(1<<(i-1))) )
            ans = true;
        //  jump
        if ( i>=3 && (B>>(i-1)&3)==3 && !BT(B^(1<<i)^(1<<(i-3))) )
            ans = true;
    }

    memo[B] = ans?1:0;
    return ans;
}

class EllysCheckers{public:
string getWinner( string board )
{
    n = (int)board.size();
    memo = vector<int>(1<<board.size(),-1);

    int B = 0;
    for ( int i=0; i<(int)board.size(); i++ )
        B = B<<1 | (board[i]=='o'?1:0);

    return BT(B) ? "YES" : "NO";
}};

#include <string>
using namespace std;

class EllysCheckers{public:
string getWinner( string board )
{
	int n = (int)board.size();
	int c = 0;

	for ( int i=0; i<n; i++ )
		if ( board[i]=='o' )
			c += n-i-1;

	return c%2==1 ? "YES" : "NO";
}};