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

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

三角形の各辺について、a個、b個、c個の内分点が与えられる。頂点及び内分点同士で直線を互いに交わらないように引けるだけ引く。線の引き方は何通りあるか？

 真ん中に三角形ができるパターンと出来ないパターンの二通りを考える。

真ん中に三角形ができるパターン

各辺から1個点を選び、それで三角形を構成する。これが真ん中にできる三角形になる。a * b * c通り。

次に各頂点と今引いた線で構成される、真ん中の三角形を除いた3個の三角形を考える。

dp[a][b] = dp[a-1][b] + dp[a][b-1] 

の漸化式でカウントできる。(ある直線が引かれる1個前の組み合わせは二通りしかないため。)また、dp[a][1] = dp[1][b] = 1である(1点から残りのすべての辺に線が引かれる。

三角形ができないパターン

一つの辺から残り2この辺への直線のみで構成される。このパターンはdp[a + b + 1][c] などで計算できる。