天下一プログラマーコンテスト2015 予選A : E - 天下一魔法使い

これは解き方がシンプルで良いな。
http://tenka1-2015-quala.contest.atcoder.jp/tasks/tenka1_2015_qualA_e

問題

円の円周上に等間隔でN個の点がある。
うち1つの点は北を向いている。
これらの点を辺で結び、幾つかの多角形を作る。
この時以下の条件を満たしているようにしたい。

• 各多角形はK個以上の点からなる。
• 各多角形は互いに(間接的に)交差している。すなわち各多角形の辺を辿って各点をつなぐことができる。

回転して同じ形状になる多角形群は同一と見なすとき、条件を満たす多角形群の作成方法は何通りあるか。

解法

以下Editorialのまま。
Editorial見た方が図があるので良いと思う。
まずは後者の交差に関する条件を除き、単にx頂点をK個以上の点の組に分割する組みわせG(x)を考える。
回転して同じ形状のものは同一と見なすため、普通の分割数のDPではこれは求められない。

同一条件を無視すると既にi個の点を分割した状態にj個の点を足すと考えてなのだが、同一と見なす条件を考えるため、常に新規に足すj個の点側に北の点があると考えると、と考えればよくなる。

i頂点において題意を満たすケース数をA(i)とする。A(N)が求めたい解である。
すると、G(i)から交差しない多角形が存在するケースを取り除いたものがA(i)といえる。

A(i)を考えるにあたり、i頂点中j頂点が北の点を含む多角形、及びそこと間接的に交差する多角形群を構成する頂点群とする。
これらの多角形群と交差しない多角形を生成する(連続頂点群)の組がいくつかあるとき、たとえば1つの連続頂点群がy頂点からなるなら、その構成法はG(y)個である。

この事実より、i頂点中に、北の点を含む多角形及びそこと交差する多角形群に含まれるj個あるような組み合わせをD(i,j)とする。
するとでDをDPで求めることができる(左辺の+1は、連続頂点群を分断するために間に最小1個の頂点が含まれるため。)

A(i)はG(i)から北の点を含む多角形及びそこと交差する多角形群に含まれない点が存在するケースを引いていけば良いので、で求められる。

int N,K;
ll A[404],G[404],dp[404][404];
ll mo=1000000007;

const int CN=1001;
ll C[CN][CN];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
	
	cin>>N>>K;
	G[0]=1;
	FOR(i,N+1) for(j=K;j<=N-i;j++) (G[i+j] += G[i]*C[i+j-1][j-1])%=mo;
	
	dp[0][0]=1;
	FOR(i,N+1) FOR(j,i+1) for(k=0;i+k+1<=N;k++)
		(dp[i+k+1][j+1]+=dp[i][j]*G[k])%=mo;
	
	A[0]=1;
	for(i=1;i<=N;i++) {
		A[i]=G[i];
		for(j=1;j<i;j++) A[i] -= dp[i][j]*A[j]%mo;
		A[i]=((A[i]%mo)+mo)%mo;
	}
	cout<<A[N]<<endl;
	
}

まとめ

個々のDP式はとても簡単。
回転して同一になるものを外す処理と合わせ、勉強になる問題だった。