kmjp's blog

競技プログラミング参加記です

AtCoder ARC #037 : D - Chaotic Polygons

ARC

本番なかなか数値が合わず頭を抱えたけど、最終的に1発ACできて良かった。
http://arc037.contest.atcoder.jp/tasks/arc037_d

問題

レベルLのシェルピンスキーのガスケットを考える。
ここに登場する各三角形の辺を用いて作れる単純多角形の数を求めよ。

解法

レベルiごとに、以下の3つの値を考える。

  • A_i : 問題文に示すような、レベルiのガスケット内にある単純多角形の数。
  • B_i : レベルiのガスケットにおいて、左下の頂点から上の頂点を経由して右下の頂点につながる辺の組み合わせ数。
  • C_i : レベルiのガスケットにおいて、左下の頂点から上の頂点を経由せず右下の頂点につながる辺の組み合わせ数。

これら3つの値をレベル(i-1)の値から再帰的に計算していく。
以下レベル(i-1)のガスケットをサブガスケットと書きます。
正直文章だけではわかりにくいので、(恐らく公式解説が図を書いてくれるので)そちらと合わせてみた方がよいでしょう。

追記：下記のサイトで図を描いてくれています。
AtCoder Regular Contest 037 D - Chaotic Polygons - mayoko’s diary

  • A_iは真ん中の大きな逆三角形を囲うケースと囲わないケースの和。
    • 囲わないケースは、上左右3か所のサブガスケット内で単純多角形ができるケースなので、 3*A_{i-1}通り。
    • 囲うケースは、上のサブガスケット内で左下から右下、右のサブガスケット内で上から左下、左下のサブガスケット内で右下から上に行く組み合わせを掛けたものなので、 (B_{i-1}+C_{i-1})^3通り。
  • B_iは以下の和。
    • 左下のサブガスケットで左下から右下を通り上に行き、上のサブガスケットで左下から上を通って右下に行き、右下のサブガスケットで上から左下を通らず右下に行く B_{i-1}^2*C_{i-1}通り。
    • 左下のサブガスケットで左下から右下を通らず上に行き、上のサブガスケットで左下から上を通って右下に行き、右下のサブガスケットで上から左下を通って右下に行く B_{i-1}^2*C_{i-1}通り。
    • 左下のサブガスケットで左下から右下を通らず上に行き、上のサブガスケットで左下から上を通って右下に行き、右下のサブガスケットで上から左下を通らず右下に行く B_{i-1}*C_{i-1}^2通り。
    • 左下のサブガスケットで右下を経由するのと、右下のサブガスケットで左下を経由する、両方は行ってはいけないので、片方行うケース2通りとどっちも行わないケースで計3通り。
  • C_iも同様に以下の和となる。
    • B_iの議論において、上のガスケットの上の頂点は経由しないのでそれぞれ掛算で B_{i-1}を1つ C_{i-1}に置き換えればよい。
    • B_iの計算と異なり、そもそも上のサブガスケットを通らないケースもある。これは (B_{i-1}+C_{i-1})^2通り。
ll L;
ll mo=1000000007;
ll D[101000][3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L;
	D[0][0]=D[0][1]=D[0][2]=1;
	
	for(i=1;i<=L;i++) {
		ll p0=D[i-1][0],p1=D[i-1][1],p2=D[i-1][2];
		ll t=p1+p2;
		
		D[i][0] += 3*p0;
		D[i][0] += t*t%mo*t;
		D[i][0] %= mo;
		
		D[i][1] += p1*p2%mo*p1;
		D[i][1] += p1*p2%mo*p1;
		D[i][1] += p2*p2%mo*p1;
		D[i][1] %= mo;
		
		D[i][2] += t*t;
		D[i][2] += p1*p2%mo*p2;
		D[i][2] += p1*p2%mo*p2;
		D[i][2] += p2*p2%mo*p2;
		D[i][2] %= mo;
	}
	cout<<D[L][0]%mo<<endl;
}

まとめ

場合分けの面白いDPでした。