Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-06-03SRM508 Div1

SRM508 Div1 500 YetAnotherORProblem

| 23:17 | SRM508 Div1 500 YetAnotherORProblem - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM508 Div1 500 YetAnotherORProblem - SRM diary(Sigmar) SRM508 Div1 500 YetAnotherORProblem - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

すぐに分かるのは、各ビットにつき1が1つ以下でなければORとADDが一緒にならない

1つずつ要素を加えていくDPをすると10^18のメモリが必要

うむ、全然分からん

どう考えても要素数が10しかないことを利用するんだろうが・・・

1桁ずつDPとかできるのかな・・・

各要素の最大値が決められているというのが扱いにくい

最大ってどうしたらいいんだ・・・

(何か色々迷走、終了10分前くらいに解法を思いつく)

上位の桁から順番に、全要素のビットを確定していけばいいのでは

例えば、10100という5桁の2進数があったとする

最初の桁を0にすると、下の4ビットは最大値1111で任意の数字を選択できる

最初の桁を1にすると、下の4ビットは最大値0100でそのまま残る

0100という4桁の2進数があったとする

最初の桁は0しか選べず、下の3ビットは最大値100でそのまま残る

このルールさえ分かれば、後はDP可能だ

各要素につき、任意のビットが選択可能になっているかを記憶すれば良い

各桁につき、1になるのは最大1つなので、せいぜい11分岐、次のビットマスクの生成コストが10であるから、

計算量は約60*2^10*11*10=6600000くらいと全然余裕

ここまで分かった時点で残り5分

コーディングは大したことないので何とかなるか?

頑張って書く

合わない

終了

くっ・・・


ソースコード

微修正で答え合った

const int MOD=1000000009;
int memo[62][1<<10];

class YetAnotherORProblem {
public:
	int rec(vector <ll> &R, int d, int mask) {
		if(d<0) return 1;
		if(memo[d][mask]>=0) return memo[d][mask];

		ll res=0;
		int nmask=mask;
		for(int j=0; j<(int)R.size(); j++) {
			if(R[j]&(1LL<<d)) nmask|=(1<<j);
		}
		res=(res+rec(R, d-1, nmask))%MOD;

		for(int i=0; i<(int)R.size(); i++) {
			if(!(mask&(1<<i)) && !(R[i]&(1LL<<d))) continue;
			int nmask=mask;
			for(int j=0; j<(int)R.size(); j++) {
				if(i==j) continue;
				if(R[j]&(1LL<<d)) nmask|=(1<<j);
			}
			res=(res+rec(R, d-1, nmask))%MOD;
		}

		memo[d][mask]=res;
		return res;
	}

	int countSequences(vector<long long> R) {
		ll res;

		memset(memo, -1, sizeof(memo));
		res=rec(R, 61, 0);
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110603