トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

カタラン数

このエントリーをはてなブックマークに追加

[アルゴリズム]

カタラン数

以下、Wikipediaからの引用。重要なのは、このアルゴリズムが二分木を用いたプログラミングにとても密接にかかわりそうだということだ。競技プログラミングに関連しそう。

カタラン数の意味
定義はWikipediaに任せます
  • ()を正しく並べる方法
    • 例えば3組の()を正しく並べる方法は、「((()))」「()(())」「()()()」「(())()」「(()())」の5通りある。これが C3=5 の場合に対応している。
    • ())()) や )(()() といった形は()を正しく並べていないのでカウントしない。
  • 二分木
    • Cnは、n個の分岐を持つ(n+1枚の葉を持つ)二分木の総数である。上記の図は C3=5 の場合に対応している。
  • 格子状の経路数え上げ
  • 平面グラフの交差

  カタラン数を使った問題に対する回答など

  • [], (), <>の三種類の記号を使って、括弧が正しく閉じるように並べるとする
  • サンプルケースとしてそれらの文字列を含んだ文字列が与えられるとき、括弧が正しく閉じていればOK、そうでなければNGを返せ

回答

    • この問題はカタラン数の性質を使えば簡単に解ける、記号が3種類しかない場合記号の並び方は5種類しかない
    • 三種の記号をすべて同じ向きの()に変換し、5種類のパターンにマッチするかしないかを確認する

  参考

お名前: コメント: