「ネタ」の記事一覧（5 / 12ページ目）

ひとりで勝手にはじめた蟻本読書会 数学的な問題 線分上の格子点の個数 ユークリッドの互除法 蟻本読書会 の続きです。 素数判定 A – 素数、コンテスト、素数 N が素数のときは YES、そうでないときは N・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 グラフ理論 木上での全頂点対最短経路問題と最小共通祖先 蟻本読書会 の続きです。 線分上の格子点の個数 点A（x1, y1）と点B（x2, y2）がある。線分AB上の格子点の数を求めよ。・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 グラフ理論 木上での全頂点対最短経路問題と最小共通祖先 蟻本読書会 の続きです。今回も前回同様、木関連の自由研究です。 葉の判定 葉の判定 (paizaランク C 相当) 木には葉と呼ば・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 グラフ理論 最短路問題 ワーシャルフロイド法 蟻本読書会 の続きです。 蟻本ではグラフに関する章はダイクストラ法、ベルマンフォード法、ワーシャルフロイド法で終わっているのですが、面白い課・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 グラフ理論 いわゆる牛ゲーと最短路問題とベルマンフォード法 蟻本読書会 の続きです。 ワーシャルフロイド法と全ペアの最短経路 ワーシャルフロイド法は、重み付き有向グラフの全ペアの最短経路・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 グラフ理論 最小全域木問題 クラスカル法 蟻本読書会の続きです。 ベルマンフォード法とは？ ベルマンフォード法は、重み付き有向グラフにおける単一始点の最短経路問題を解くアルゴリズムのひと・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 グラフ理論 最短路問題 ダイクストラ法 蟻本読書会の続きです。 最小全域木問題とクラスカル法 最小全域木とは、グラフが連結であるという条件を保ったまま辺を消去して得られる木のなかで辺のコ・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 グラフ理論 二部グラフ判定 蟻本読書会の続きです。 ダイクストラ法と最短路問題 ダイクストラ法（だいくすとらほう、英: Dijkstra’s algorithm）はグラフ理論・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 データ構造 Union-Find 木 蟻本読書会の続きです。 グラフと二部グラフ グラフとは、ノード（頂点）群とノード間の連結関係を表すエッジ（枝）群で構成されるデータ構造です。 鉄道や・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 データ構造 set, map 編 蟻本読書会の続きです。 Union-Find木とはグループ分けを木構造で管理するデータ構造です。このデータ構造であれば、同じグループに属するなら同じ木に・・・

続きを読む