中級 0件解決済み 正答率0%

カタラン数

カタラン数 C(0) から C(n) までを列挙します。

このチャレンジで学べること

  • 前の値から数列を組み立てられる
  • 積の和の形の漸化式を使える
  • 途中結果のオーバーフローを避けられる

問題

原文(英語)を表示

カタラン数 1, 1, 2, 5, 14, 42, … は、さまざまなものの個数として現れます。たとえば n 組の括弧の正しい並べ方、n 個のノードを持つ二分木の個数、凸多角形を三角形に分割する方法の数などです。C(0) = 1 から始まり、C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0) を満たします。

catalan_numbers(n) を実装してください。

入力

n:リストに含める最後のカタラン数の添字。

出力

n + 1 個の値からなるリスト [C(0), C(1), …, C(n)] を返してください。符号付き64ビット整数に収まる最大のカタラン数は C(35) なので、途中の計算でのオーバーフローに注意してください。

制約

0 ≤ n ≤ 35

例

例 1
入力:
n = 4

期待される出力:
expected = [1, 1, 2, 5, 14]
入力:
long long n = 4;

期待される出力:
std::vector<long long> expected = {1, 1, 2, 5, 14};
入力:
long n = 4;

期待される出力:
long[] expected = new long[] {1, 1, 2, 5, 14};

解説

C(4) = 1·5 + 1·2 + 2·1 + 5·1 = 14 なので、リストは [1, 1, 2, 5, 14] です。

例 2
入力:
n = 0

期待される出力:
expected = [1]
入力:
long long n = 0;

期待される出力:
std::vector<long long> expected = {1};
入力:
long n = 0;

期待される出力:
long[] expected = new long[] {1};

解説

求めるのは C(0) = 1 だけなので [1] です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

計算した値をリストに保存していきます。

ヒント 2

C(k + 1) は、i についての C(i) × C(k − i) の和です。

ヒント 3

この和に含まれる各積は最終的な値以下なので、制約の範囲内では和を取る方法でオーバーフローしません。

目安の計算量

時間 O(n^2)、追加メモリ O(n)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。