World CodeSprint 8 : F. Return of the Nim

これは知らなかった。
https://www.hackerrank.com/contests/world-codesprint-8/challenges/sherlock-and-nim

問題

変則的なNimを考える。
素数であるN要素の数列P[i]がある。
２人で交互にこれらの数字を減算していく。
両者の手番では以下のいずれかの処理を行える。

• １つの要素を選び、P[i]が非負となる範囲で1以上任意の整数だけ減算する。
• 全要素を、P[i]が非負となる範囲で1以上任意の整数だけ減算する。

自分の手番でどちらも行えない場合、負けとなる。
両者最適手を取った場合、勝者はどちらか。

解法

小さいケースで全探索をしてみると、Nが奇数の場合は通常のNimと同じ条件で判定できる。
あとはN=2の場合を考えよう。
全探索してみると、２つの要素が以下の場合に先手が負ける。

0 0
1 2
3 5
4 7
6 10
8 13
9 15
11 18
12 20
14 23
16 26
17 28
...

よく見ると、上記の数列は以下の条件を満たす。

• 上から見ていくと、差が１つずつ広がっている
• 各整数が左右どちらかに１回ずつ登場する

上記いずれかの状態について、先手がどんな処理を行っても、後手が再び上記数列のどれかの状態に戻せることがわかる。
すなわち、先手は最終的に0 0で自分の手番が回ってきて負ける。

あとは上記数列を生成して判定すればよい。

int G;
int N;
int A[31];
string S[2]={"Sherlock","Watson"};
int V[2];

int did[201010];
int mp[201010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	did[1]=1;
	did[2]=2;
	mp[1]=2;
	int add=2;
	for(x=3;x<=100000;x++) {
		if(did[x]) continue;
		did[x]=1;
		did[x+add]=1;
		mp[x]=x+add;
		add++;
	}
	
	cin>>G;
	while(G--) {
		cin>>N;
		
		if(N>2) {
			int xo=0;
			FOR(i,N) cin>>x, xo^=x;
			cout<<S[xo==0]<<endl;
		}
		else {
			cin>>x>>y;
			if(x>y) swap(x,y);
			cout<<S[mp[x]==y]<<endl;
		}
	}
}

まとめ

素数とか言って目くらましさせておいて、結局N=2かそうでないかしか関係ないのがミソ。