TopCoder SRM 785 : Div2 Hard EllysNimDiv2

Div1の方は難しいけど。
https://community.topcoder.com/stat?c=problem_statement&pm=16135&rd=17965

問題

Nimのある状態が与えられる。
いくつかの山に石を足し、先手必敗にしたい。
最小何個石を足せばよいか。

解法

dp(i,x) := prefix i個の山の石の数のxorがxになるような追加石数の最小値
とする。元の石の数が1000個以下なので、足してもせいぜい2進数で1024の桁まであればよいので、xは2048未満だけ考えればよい。

int from[2050];
int to[2050];

class EllysNimDiv2 {
	public:
	int getMin(vector <int> A) {
		int i;
		FOR(i,2050) from[i]=1<<30;
		from[0]=0;
		FORR(a,A) {
			FOR(i,2050) to[i]=1<<30;
			FOR(i,2048) {
				for(int x=0;x+a<2048;x++) to[i^(x+a)]=min(to[i^(x+a)],from[i]+x);
			}
			
			swap(from,to);
		}
		return from[0];
		
	}
}

まとめ

Hardと難易度が全然違う。