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;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110603