Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-03SRM508 Div1

SRM508 Div1 250 DivideAndShift

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

Problem Statement

コーディングフェーズ

これは・・・DivideとShiftの操作は可換だ。ピンと来た

これが分かったら解けたも同然だな

エラトステネスの篩で素数を生成しておいて、再帰的にNを素数で割っていく

各Nの最小手数をメモ化しておけば計算量は問題ない(Nが決まればMが決まるため、状態数は100万程度しかない)

書いた

サンプル合った

提出

多少実装と可換の確認に時間を食ったがそこそこ早めに解けた


ソースコード

vector <bool> cpn(int n) {
	vector <bool> vn(max(2, n+1), true);

	vn[0]=vn[1]=false;
	for(int i=2; i*i<=n; i++) {
		if(!vn[i]) continue;
		for(int j=i*i; j<=n; j+=i) vn[j]=false;
	}
	
	return vn;
}

vector <bool> v;
int memo[1000010];

class DivideAndShift {
public:
	int calc(int N, int M) {
		if(memo[N]>=0) return memo[N];
		int res=min(M, N-M);
		for(int i=1; i*i<=N; i++) {
			if(N%i!=0) continue;
			if(i!=1 && v[i]) res=min(res, calc(N/i, M%(N/i))+1);
			if(v[N/i]) res=min(res, calc(i, M%i)+1);
		}
		memo[N]=res;
		return res;
	}

	int getLeast(int N, int M) {
		int res;
		v.clear();
		v=cpn(1000000);
		memset(memo, -1, sizeof(memo));

		res=calc(N, M-1);
		return res;
	}
};

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