AtCoder-ABC185 C - Duodecim Ferra【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

AtCoder Beginner Contest185 C問題について記載していきます。
AtCoder Beginner Contest 185 - AtCoder

AtCoder Beginner Contest185 C - Duodecim Ferra

問題文

長さLの鉄の棒が東西方向に横たわっています。この棒を11箇所で切断して、12本に分割します。このとき分割後の各棒の長さが全て正整数になるように分割しなければなりません。
分割のしかたが何通りあるかを求めてください。二つの分割の方法は、一方で分割されているが他方で分割されていない位置が存在する場合に、そしてその場合に限って区別されます。
なお、この問題の制約下で答えは2^63未満であることが証明できます。

制約

・12≤L≤200
・Lは整数

解答例

l = int(input())

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

a = cmb(l-1,11)

print(a)

解説

長さLの棒を11か所切断して、それぞれ長さが整数の12本の棒に切り分ける分け方が何通りあるかという問題です。
切り分けたあと12本の棒がすべて整数であるためには、切る位置の候補はどちらかの棒の端を基準として1,2,3…,L-1のようにL-1までの整数の位置になります。
この候補から11個の位置を選ぶ組み合わせの数を求めればよいことになります。

後で記載するitertoolsを用いた方法ではTLEとなりNGでした。
こちらの記事で紹介されていたプログラムを使用させていただきました（感謝です）。
【Python】組み合わせ(nCr) 計算の高速化 - Qiita
nCr = (n-1)Cr + (n-1)C(r-1) の公式を使用して組み合わせの数を求められているようです。
他人のふんどしでACもらうのは情けない話ですが、またまた勉強させてもらいました。

NG例

import itertools

l = int(input())

n = []
i = 1
while i < l:
    n.append(i)
    i += 1

comb = list(itertools.combinations(n,11))

print(len(comb))

私の解答はTLEとなりました…
順列と組み合わせについて次の記事で過去に勉強していました。
ebisuke33.hatenablog.com
itertoolsを用いて組み合わせの数を求めようとしましたが時間切れでした（制限時間を無視しても正しいか自信ないです…）。
使用する方法自体の処理速度による差は大きいようです。
以前勉強したことだったので、これだ！と飛びつきましたが、そう簡単にはいきませんでした。

D問題はコンテストでは解答できませんでしたが、解説を読んで内容を理解できたら記事にしていきたいです。

以前のABC185の記事はこちら
ebisuke33.hatenablog.com