Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-09-11SRM517 Div1

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