「ネタ」の記事一覧

クヌース-モリス-プラット法（Knuth-Morris-Pratt algorithm）は、文字列検索アルゴリズムの一種です。文字列Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置・・・

続きを読む

Union-Find木（ユニオンファインド木）とはグループ分けを管理するデータ構造です。Union-Find木を用いることで、グループ同士の併合（Union）、ある要素がどのグループに属しているかを見つける操作（Find・・・

続きを読む

引用元：トポロジカルソート可能かを判定 (paizaランク A 相当) トポロジカルソートとは 有向グラフ G について、下図のようにすべての辺が同じ方向になるように頂点を一列に並べることを「トポロジカルソート」といいま・・・

続きを読む

二分ヒープと優先度付きキュー プライオリティキュー（優先度付きキュー）とは、優先度の高いデータから取り出すというデータ構造で、その代表的なものがヒープといわれる木構造です。ヒープの中にも単純な構造である二分ヒープを扱いま・・・

続きを読む

ハミルトン閉路とは？ 任意の頂点から出発してすべての頂点をちょうど 1 回ずつ訪問したのち、最初の頂点に戻ってくることができるようなグラフをハミルトングラフといいます。またそのような順番で頂点を並べた閉路をハミルトン閉路・・・

続きを読む

オイラーグラフとオイラー閉路 グラフ上の任意の頂点から出発して、すべての辺を使って一筆書きをすることができるようなグラフを準オイラーグラフと呼びます。またそのような一筆書きの順番で頂点を並べたパスをオイラー路と呼びます。・・・

続きを読む

ワーシャルフロイド法とは？ ワーシャルフロイド法は最短経路問題で使われるアルゴリズムの１つです。重みが負の辺があっても負閉路がない限り使えます。 下のようになっている場合、0 → 1 と直接移動する場合は 10 ですが、・・・

続きを読む

連続する区間の和 与えられたint型の配列において、長さが 1 以上で総和が与えられた値以下であるものを考えます。そのような区間がいくつあるか、区間の長さで最大のものを求めるにはどうすればいいでしょうか？ （例）int[・・・

続きを読む

累積和 累積和とは配列の任意の区間の総和を求めるためのアルゴリズムです。 繰り返し処理を使うと大きな計算量になってしまう区間の計算問題を、適切な前処理を行うことによって高速に行うことができます。 配列と累積和 int型の・・・

続きを読む

最長増加連続部分列 最長増加連続部分列とは、配列があったとき単調増加になっている最も長い部分です。配列が {1, 2, 3, 4, 5} であるなら配列全体が単調増加しているので求める解は {1, 2, 3, 4, 5}・・・

続きを読む