yukicoder : No.520 プロジェクトオイラーへの招待

想定解法が面白かったです。
http://yukicoder.me/problems/no/520

問題

正三角形ABCの三辺BC,CA,ABにそれぞれa個,b個,c個の内分点を取る。
元の三角形の頂点およびこれらの内分点の間を、互いに交差しないように線分を追加して結んでいく、という動作をこれ以上線分を追加できなくなるまで繰り返す。
線分の引き方は何通りか。

解法

以下の関数を考える。
f(x,y) := 元の正三角形の1個の頂点から、そこにつながる2辺にそれぞれx個・y個の内分点があるとき、それらの内分点同士の線分の結びかた

この値は以下の通りDPで計算できる。

• x,yのいずれかが1以下の時f(x,y)=1
• x,yがともに2以上の場合
  • x個内分点がある場合一番頂点から遠い内分点が、もう一方の辺のy個のうち遠い方i個とつながる、と考える。
    • Writerのeditorialではとなっているが、こっちの方が計算量短いな。

上記f(x,y)を使って元の問題を解こう。

• 元の正三角形からいずれかの内分点に線分を伸ばす場合、元頂点のうち1つしかそのような線分は伸ばせない。
  • たとえばAからa個の内分点のうち、頂点C辺側から見てi個目の頂点に1本目の線を引いた場合の組み合わせは通り
  • 3つの辺に対し、それぞれiを総当たりして数え上げる
• 元の正三角形頂点に線分を1本も伸ばさない場合
  • この場合、内分点同士を結んだ三角形ができる
  • a個の内分点のうち頂点C辺側から見てx個目、b個の内分点のうち頂点A辺側から見てy個目、c個の内分点のうち頂点B辺側から見てz個目で三角形を組んだ場合、残りの領域の線分の組み合わせは通り
  • x,y,zを総当たりしてこれらを数え上げる

int N;
ll memo[103][103];
ll mo=1000000007;

ll hoge(int A,int B) {
	ll& ret=memo[A][B];
	if(ret>=0) return ret;
	if(A<=1 || B<=1) return 1;
	
	ret=0;
	for(int x=1;x<=B;x++) ret+=hoge(x,A-1);
	ret %= mo;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	int A,B,C;
	
	MINUS(memo);
	cin>>N;
	while(N) {
		N--;
		cin>>A>>B>>C;
		ll ret=0;
		for(i=1;i<=A;i++) for(j=1;j<=B;j++) for(x=1;x<=C;x++) (ret+=hoge(i,j)*hoge(B+1-j,x)%mo*hoge(A+1-i,C+1-x))%=mo;
		for(i=1;i<=A;i++) (ret+=hoge(i,B)*hoge(A+1-i,C+1)%mo)%=mo;
		for(i=1;i<=B;i++) (ret+=hoge(i,A)*hoge(B+1-i,C+1)%mo)%=mo;
		for(i=1;i<=C;i++) (ret+=hoge(i,A)*hoge(C+1-i,B+1)%mo)%=mo;
		cout<<ret%mo<<endl;
	}
}

まとめ

本番は元頂点に線分を張らないケースをものすごく面倒なDPで求めて苦労した。
ともあれ面白かったです。