【AtCoder】ABC 185 C - Duodecim Ferra

2026-11-07

AtCoder/ABC/C問題 AtCoder/ABC/300点問題 AtCoder/灰Diff AtCoder/NoviSteps/3Q AtCoder/数学/二項係数競技プログラミング

C - Duodecim Ferra

C - Duodecim Ferra

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 374 / NoviSteps: 3Q / 配点: 300 点

問題概要

長さ $L$ の鉄の棒を $11$ 箇所で切断して、 $12$ 本に分割する。

分割後の各棒の長さが全て正整数になるように分割するとき、分割のしかたが何通りあるかを求めよ。

制約

$12 \le L \le 200$
$L$ は整数

考察

「棒に $L - 1$ 箇所の切れ込みがあり、そのうち $11$ 箇所を選んで切断する」と考えると、 $L - 1$ 個の中から $11$ 個を選ぶ組み合わせの数が本問の答えとなる。

これは二項係数 $\binom{L - 1}{11}$ によって求めることができるが、オーバーフローに注意。

今回は自作のライブラリを使用した。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.using ll = long long;
5. 
6.ll nCk(ll n, ll r)
7.{
8.    if (r < 0 || n < r)
9.        return 0;
10.    ll ans = 1;
11.    for (ll i = 1; i <= r; i++)
12.    {
13.        ans *= n--;
14.        ans /= i;
15.    }
16.    return ans;
17.}
18. 
19.// ======================================== //
20. 
21.int main()
22.{
23.    ll L;
24.    cin >> L;
25. 
26.    cout << nCk(L - 1, 11) << endl;
27. 
28.    return 0;
29.}

https://atcoder.jp/contests/abc185/submissions/80403477

実装時間: 5 分

コメント

オーバーフローに配慮した二項係数の計算ライブラリを持っておくと、これからも役立ちそう。