Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-09-11SRM517 Div1

SRM517 Div1 250 CompositeSmash

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

Problem Statement

コーディングフェーズ

サンプルを見て、N%target==0かつtargetが素数か、N==targetか、Nを1回smashしたら必ずtargetが出ればYesかなと想像したがつい最近KISSの原則なる記事を書いたことを思い出しメモ化で全探索することにした。

書いた。サンプル合った。提出。

サンプルにないパターンでコーナーケースを探してみる。

適当に32,4とかやってみたらYesだった。確かに手計算してみてもYesになる・・・

ということでチャレンジで50点ゲットした。ラッキー。


ソースコード

よく見たら実は全然メモ化できてなかった。

メモ化しなくても計算量が余裕だったので気づかなかった。

int memo[100010];

class CompositeSmash {
public:
	int rec(int N, int t) {
		if(N==t) return 1;
		if(memo[N]>=0) return memo[N];
		int ok=0;
		int r=1;
		for(int i=2; i*i<=N; i++) {
			if(N%i!=0) continue;
			ok=1;
			int r1=rec(N/i, t);
			int r2=rec(i, t);
			r&=(r1|r2);
		}
		//memo[N]=(r&ok);が入るはずが・・?
		return r&ok;
	}

	string thePossible(int N, int target) {
		string res;

		memset(memo, -1, sizeof(memo));
		int r=rec(N, target);
		res=(r?"Yes":"No");
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110911