ABC185 C問題 Duodecim Ferra 数学系問題を解く - 競技プログラミング悪戦苦闘日記

ABC185のC問題を解説します。
自分の反省点としてはpythonのライブラリの知識が不十分だなと思いました。。。

長さ L の鉄の棒が東西方向に横たわっています。この棒を 11 箇所で切断して、12 本に分割します。このとき分割後の各棒の長さが全て正整数になるように分割しなければなりません。分割のしかたが何通りあるかを求めてください。

$L$ の範囲は $12 \leq L \leq 200$ です。
Lが12の場合、1の長さが12個になるように切断するしか選択肢はないので、答えは1になります。
Lが13になると、1の長さが11個、長さ2が1個になります。長さ2を何番目に持ってくるかは12通りあるので、答えは12です。

公式解説の通りなのですが、分割する位置のパターンは $L - 1$ 箇所あり、そこから異なる11個を選ぶ組み合わせが答えになります。

なので ${}_{L-1} \mathrm{C} _{11}$ を求めるコードを書きます。

自分で関数を作っても良いのですが、楽な方法はないかとググって以下のQiitaの記事に辿り着きました。

qiita.com

ユーザー定義型２をそのまま引用して、以下のコードになりました。

from operator import mul
from functools import reduce
L = int(input())


def cmb(n, r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


ans = cmb(L - 1, 11)
print(ans)

無事に解けたのですが、他の人の答えを見て唖然とします。
mathモジュールの中にcombメソッドあったんですね。。。

from math import comb
L = int(input())
print(comb(L - 1, 11))

Pythonのライブラリの知識が足りてないな。。。まぁこうやって覚えていけば良いと思いますが。