kmjp's blog

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

TopCoder SRM 601 Div1 Medium WinterAndSnowmen

本番中に計算量を落としきれなかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=12891

問題

数値NとMが与えられる。
1番手は集合{1,2,,,N}の部分集合A、2番手は集合{1,2,,,M}の部分集合Bを取るとき、以下の条件を満たす部分集合のとり方は何通りあるか。

  • A,Bは同じ要素を持たない。
  • 集合内の全要素のxorを取った場合、Aの(全要素の)xorの方がBの(全要素の)xorより小さい。

解法

以下L=max(N,M)、AX=Aの要素のxor、BX=Bの要素のxor、とする。
本番にO(L^3)の解はすぐに思いついた。
1からLまで、順に(Aに加える,Bに加える,どちらにも加えない)のいずれかを行い、AX,BXを状態とした組み合わせ数DP[AX][BX]を更新していけばよい。
ただしN,Mは2000まで行くのでO(L^3)ではTLEするため、本番submitせず。

xor問題の定石として、bit単位で処理をすることでO(L^3)からO(L^2 logL)位に落としたかったが、本番中に色々考えて間に合わず。

以下の解説が(日本語だし)わかりやすかったので、参考にさせて頂いて再チャレンジ。
2013-12-23 - 思考錯誤 - By evima - TopCoder部

AXとBXを互いに2進数にしたとき、上位桁がずっと両者同じ値で、下からd桁目で初めて差がつくとする。
すなわちAXのd桁目が0、BXのd桁目が1であれば、AXの方が小さいと言える。
その場合d桁より下の桁の値はどうでもよく、d桁目より上の桁は一致しなければならない。
ただ、AXとBXのd桁目より上位桁をそれぞれ状態としてDPすると、結局O(L^3)になってしまう。

ここで発想が必要。
AXとBXのd桁目より上が一致するということは、両者のxorが0になるということ。
ここまでくれば回答はすぐで、DP[(AX^BX)のうちd桁目より上][AXのd桁目][BXのd桁目]を状態として、1からLまで、順に(Aに加える,Bに加える,どちらにも加えない)のいずれかを行って状態を更新すればよい。
この処理を1<=d<=logLで繰り返すと結局O(L^2 logL)で解ける。

ll okok[2][2048][2][2];
ll mo=1000000007;

class WinterAndSnowmen {
	public:
	int getNumber(int N, int M) {
		int i,x,y,z,d;
		ll ret=0;
		FOR(d,11) {
			ZERO(okok);
			okok[0][0][0][0]=1;
			for(i=1;i<=max(N,M);i++) {
				int cur=(i-1)%2;
				int tar=cur^1;
				ZERO(okok[tar]);
				FOR(x,2048>>(d+1)) FOR(y,2) FOR(z,2) {
					if(okok[cur][x][y][z]==0) continue;
					okok[tar][x][y][z] = (okok[tar][x][y][z]+okok[cur][x][y][z])%mo;
					int upi=i>>(d+1),mdi=(i>>d)&1;
					if(i<=N) okok[tar][x^upi][y^mdi][z] = (okok[tar][x^upi][y^mdi][z]+okok[cur][x][y][z])%mo;
					if(i<=M) okok[tar][x^upi][y][z^mdi] = (okok[tar][x^upi][y][z^mdi]+okok[cur][x][y][z])%mo;
				}
			}
			ret += okok[max(N,M)%2][0][0][1];
		}
		return (int)(ret%mo);
	}
};

まとめ

本番、「xorの大小問題なので、bit単位で処理すればO(L^3)をO(L^2 logL)に出来る」まで思いつけたのはよかった。
ここでもう一段階、「上位桁が一致する=上位桁のxorが0になるようにする」という発想に至らなかったのが実力不足な点。でも今回で覚えた。

こういう問題ってCodeforcesに多いよね…。

広告を非表示にする