LoginSignup
1

More than 5 years have passed since last update.

Project Euler 53「組み合わせ選択」

Posted at

ワンライナーって気持ちいい。
でも 次の問題 をチラ見したらクソ程めんどくさそうで若干萎え気味。

Problem 53 「組み合わせ選択」

12345から3つ選ぶ選び方は10通りである.
123, 124, 125, 134, 135, 145, 234, 235, 245, 345.
組み合わせでは, 以下の記法を用いてこのことを表す: $_5C_3 = 10$
一般に, r ≤ n について $_nC_r = n!/(r!(n-r)!)$ である.
ここで, n! = n×(n−1)×...×3×2×1, 0! = 1 と階乗を定義する.
n = 23 になるまで, これらの値が100万を超えることはない: $_{23}C_{10} = 1144066$
1 ≤ n ≤ 100 について, 100万を超える $_nC_r$ は何通りあるか?

def hoge(max_n, limit):
    f = lambda n: n * f(n-1) if n > 0 else 1
    C = lambda n, r: f(n) // (f(r) * (f(n-r)))
    return sum( 1 for n in range(1, max_n+1) for r in range(1, n+1) if C(n, r) > limit )

print(hoge(100, 1000000))

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1