AtCoder順列

問題

元の問題: C – Average Length

N個の全ての点を1回ずつ通るような動き方は\(N!\)通りある。総移動距離の平均を求めよ。

解き方順列を使って解く方法

順列(N!)の全探索を行っ ...

探索順列

\(n!\)通りの全探索を行いたい時に順列が用いられます。

順列(permutation)とは、n個のものを順番に並べるのは何通りあるかを考える問題です。n個全てを区別できるなら、\(n!\)通りの並べ方があります。

探索幅優先探索, グラフ, キュー

幅優先探索とは、全探索アルゴリズムの一種です。最短経路を求める際に使用される基本的なアルゴリズムです。

木などのグラフやグラフと同一視できるものを探索する際に良く使われます。深さ優先探索と似ていますが、幅優先探索は始めの状 ...

AtCoder幅優先探索, グラフ

問題

AtCoderでの問題:D – Coloring Edges on Tree

木構造について、頂点から見た時に、自身から伸びる枝に重複が無いように色を塗る問題です。使う色の数は最小にする必要があります。

探索深さ優先探索, スタック, 再帰関数, 全探索

深さ優先探索とは、全探索アルゴリズムの一種です。木などのグラフやグラフと同一視できるものを探索する際に良く使われます。

幅優先探索(BFS)と似ていますが、深さ優先探索は末端に到達するまで「深く」探索してから、他のノードの ...

グラフグラフ

グラフとは

頂点(ノード)と、頂点同士の関係を表したデータ構造です。

数学的には、グラフは以下の2つから構成されます。

頂点(ノード)の集合
頂点同士がつながっているか(隣接しているか)を表す、辺(エッジ)の集合 ...

データ構造集合

Setとは、数学における集合をデータ構造として表したものです。順序はなく、変更可能で、重複した要素を持ちません。

要素の挿入・削除・検索を高速に行うことができる特徴があります。

プログラム例Pythonの例

Py ...

データ構造キュー

キューは待ち行列とも呼ばれます。最初に格納したデータが最初に出てくるような、線形なデータ構造をしていて、このような順序をFirst In First Out (FIFO)と言います。

例えると、レストランにできる行列と一緒 ...

データ構造スタック

スタックとは

線形なデータ構造の1つです。データを格納する操作(push)と取り出す操作(pop)について、対象になるデータの順番が決められています。

スタックは、最後に格納したデータが最初に出てくるようなデータ構造をしてい ...

データ構造入門

連結リストとは

連結リストはノードと呼ばれるデータの塊が、複数繋がってできたデータ構造です。

1つのノードは、格納する値自体と、次のノードへのアドレスを保持します。先頭から各ノードを辿ることで、線形に連結リストを探索すること ...