torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Beginner Contest 185, C : Duodecim Ferra

問題概要

 長さ $L$ ($L$ は整数)の棒を $11$ 箇所で切断して $12$ 本の棒(各棒の長さは整数)を作ることを考える.切断の仕方は何通りあるか?

制約

  • $12 \leq L \leq 200$

解法

 切断の仕方というのは,$L - 1$ 箇所ある棒上の整数点から $11$ 箇所を選ぶことに対応するので,答えの値としては二項係数 $\binom { L - 1 } { 11 }$ になります.ですが本記事では,二項係数的な雰囲気がもう少し薄い DP による解法を考えます.
 切り出し方のパターンを全通り試す全探索をイメージします.すると,(棒を左から切っていくとして,)棒の左から長さ $i$ までの部分の使い方が決まっているとき,次の切れ込みを入れる箇所……というか,次に切り出される棒の右側の端点の位置 $k$ は $i < k \leq L$ なる $k$ です.この $k$ の候補は $L$ の制約が小さいことから現実的な個数に収まります.とはいえ,一ステップあたりの選択肢の数が現実的でも,全体の切り出し方の総数というのは試してみれば分かるようにナイーブには扱えません.そこで,次のように状態をとる動的計画法を考えます:

  • $\mathit{ dp }_{ i, j }$ $:=$ 左から長さ $i$ までの部分の使い方が決まっていて,切り出す本数は $j$

このとき,$\mathit{dp}_{ i, j }$ の状態からの次の選択肢は,次に切る箇所を位置 $k$ として,

  • $\mathit{ dp }_{ k, { j + 1 } }$ に $\mathit{ dp }_{ i, j }$ を足し込む

として DP に落とし込めます.
 この DP の状態数は,$12$ が定数なことを考えると $\Theta( L )$ で,各状態からの遷移の数は $O( L )$ であることから,この DP は $O( L^2 )$ 時間で計算できます.
 最後に $\mathit{ dp }_{ L, 12 }$ を読めば答えが求まります.

コード

int main()
{
	IN( int, L );
	
	static LL dp[ 256 ][ 16 ];
	dp[0][0] = 1;

	REP( i, L )
	{
		REP( j, 12 )
		{
			REP( k, i + 1, L + 1 )
			{
				dp[k][ j + 1 ] += dp[i][j];
			}
		}
	}

	cout << dp[L][12] << endl;

	return 0;
}