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;
	}
};

SRM517 Div1 600 AdjacentSwaps

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

Problem Statement

コーディングフェーズ

とりあえず逆順に考えたほうが楽なので逆順に考える。つまりpをソートすると考える。

色々考えていると法則性がありすぎてどれを使えばいいか分からなくなった

  • 解が0でない条件は、permutationが2グループに分けられないこと({1,0,3,2}は×、{3,0,1,2}は○)
  • ある時点でswapができる条件は、左の要素が本来の位置より左にあり、右の要素が本来の位置より右にあること
  • ある時点でswapができる条件は、左の要素が右の要素より大きいこと(恐らく上の条件と同じ意味)
  • 各要素は本来の位置へ向かう方向にのみ動き、逆方向に動くことはない(戻れないから)
  • ある時点でswapができる要素は同時に複数存在しうる

何となくDAGっぽくなりそうなのでDAGにしようとしてみたらえらいことになった

結局何か違うなと思いつつタイムオーバー・・・


後で

考えてみれば2番目の法則を使ってメモ化再帰が可能だった

pのある範囲[b,e)の解を再帰的に計算する

pをswap可能なindexで分割し、両側を再帰計算した結果を掛けあわせ、さらに両側の残りswap数を使ってコンビネーションを取る

これだけだった・・・

何か解けそうで解けない方針が色々出てくる問題なので上の解法も思いつくかどうかが全てな気がする。。。

(普通の500だともっとWrong Attemptを枝刈りしやすいイメージ)


ソースコード

cmbgfはMODを取りながらコンビネーションを計算する

自前ライブラリのcmbgfはnやkがMOD以上になった場合に効率良く計算するため複雑になっているが、ここではnやkは大きくならないため、普通にMODをとりながらコンビネーションを計算するだけで問題ない

const int MOD=1000000007;
int memo[52][52];

ll powgf(ll a, ll e) {
	ll res=1;
	for(; e; a=(a*a)%MOD, e>>=1) {
		if(e&1) res=(res*a)%MOD;
	}
	return res;
}
ll divgf(ll a, ll b) { return (a*powgf(b, MOD-2))%MOD; }

ll cmbgf(ll n, ll _k) {
	ll res=1, remn, remk;
	ll k=min(_k, n-_k);
	if(n<0 || n<k || k<0) return 0;
	if(k>=MOD) {
		remn=n%MOD; remk=k%MOD;
		if(remn<remk) return 0;
		res=(cmbgf(remn, remk)*cmbgf(n/MOD, k/MOD))%MOD;
	} else {
		if(n>=MOD) n%=MOD;
		if(n<k) return 0;
		for(ll i=1; i<=k; i++) {
			res=divgf((res*(n-i+1))%MOD, i);
		}
	}
	return res;
}

class AdjacentSwaps {
public:
	int n;

	int rec(int b, int e, vector <int> &p) {
		int res=0;
		if(b==e) {
			if(p[b]==b) return 1;
			else return 0;
		}

		if(memo[b][e]>=0) return memo[b][e];

		for(int i=b; i<e; i++) {
			if(p[i]>i && p[i+1]<i+1) {
				swap(p[i], p[i+1]);
				ll r1=rec(b, i, p);
				ll r2=rec(i+1, e, p);
				if(r1==0 || r2==0) {res=0; break; }
				res=(res+r1*r2%MOD*cmbgf((i-b)+(e-(i+1)), i-b))%MOD;
				swap(p[i], p[i+1]);
			}
		}

		memo[b][e]=res;
		return res;
	}

	int theCount(vector <int> p) {
		int res=1;
		n=p.size();

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