【ABC185 C】「Duodecim Ferra」を解く【Python3】

コンテスト一覧へ

 

長さLの棒を、各棒の長さが正整数になるように12分割するとき、分割の仕方が何通りあるかを求める問題です。

提出
import math
l = int(input())

ans = math.factorial(l-1) // (math.factorial(l-12) * math.factorial(11))
print(ans)

長さ1を「○」に置き換えて考えます。

すると、長さ12は、

○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○

となります。これを12分割するには、

○|○|○|○|○|○|○|○|○|○|○|○

となり、11個の「|」が必要になります。「|」が入る場所も11個であるため、1通りになります。

長さ12以上のLは、

○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ……

となり、これを各棒の長さが正整数になるように分割するには、「|」を「L-1」個の中から11個選んで入れれば良いことがわかります。

つまり、組み合わせの問題で解くことができます。

「L-1」個の中から11個選ぶ組み合わせは、

です。

言語によっては工夫が必要になりますが、Pythonであれば、math.factorial() で階乗を求められるので、これを利用します。

【ABC185】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。