kmjp's blog

競技プログラミング参加記です

TopCoder SRM 701 Div1 Easy PartisanGame

Easyは解けたもののチャレンジミスとかしてグダグダだった。
https://community.topcoder.com/stat?c=problem_statement&pm=14426

問題

N個の意思を2人で交互に取り合うゲームを行う。
先手は正整数の集合A,後手は正整数の集合Bに含まれるいずれかの数の分石を取る。
石を取れなくなったら負けである。

互いに最適手を取る場合、勝者はどちらか。

解法

Nの上限が大きいのでNim+Grundy数に持ち込んでも間に合わない。
A,Bの要素が小さいので、一度Nが小さい範囲でNがどの値の時にどちらが勝つかシミュレートしてみよう。
ある程度以上大きくなると、勝者が周期性を持つことがわかる。

あとは周期性を用いてNを小さくすればよい。
以下のコードは、実際にA,Bを総当たりで試すと周期が高々1~10なので、それらのLCMである8*9*5*7で周期性があることを仮定している。

class PartisanGame {
	public:
	string getWinner(int n, vector <int> a, vector <int> b) {
		const int D=10000;
		int F[D+2]={},G[D+2]={};
		
		for(int i=1;i<=D;i++) {
			FORR(r,a) if(i>=r && G[i-r]==0) F[i]=1;
			FORR(r,b) if(i>=r && F[i-r]==0) G[i]=1;
		}
		
		if(n>D) n = 8*9*5*7+(n-8*9*5*7)%(8*9*5*7);
		
		return (F[n]?"Alice":"Bob");
		
	}
}

まとめ

実装は軽いのに、なんで300ptなんだろう。
法則見つけるのに時間がかかるから?