鳩でもわかるC#

ひとりで勝手にはじめた蟻本読書会 二部グラフの最大マッチング問題 蟻本読書会 の続きです。 3点と三角形の面積 C – 直訴 C – 直訴 点 A の座標が (xa , ya)、点 B の座標が ・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 最大流問題と最小カット問題 蟻本読書会 の続きです。 最小費用流問題とは、流す量が与えられた際、流すために掛かる総費用を最小にするためにはどのようにするとよいのかを決定する問題です。 最・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 最大流問題と最小カット問題 蟻本読書会 の続きです。 二部グラフの最大マッチング問題 グラフ理論における二部グラフとは、頂点集合を2つに分割して各部分の頂点は互いに隣接しないようにできる・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 繰り返し2乗法と行列累乗 フィボナッチ数列 の続きです。 最大流問題を解く 各地点が水道管でつながっていて、ある地点から別の地点へ一定量の水を流し続けることを考えます。始点と終点以外では・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 巡回セールスマン問題 蟻本読書会 の続きです。 繰り返し2乗法 繰り返し2乗法とは、指数を2の累乗の積に分解し、計算を効率化するテクニックです。3の50乗を1000000007（10^9・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 フェニック木 BIT（Binary Indexed Tree） 蟻本読書会 の続きです。 巡回セールスマン問題は、複数の決められた地点を巡回して元の位置に戻る際、どう回れば最も移動距離が・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 セグメント木 遅延評価セグメント木で区間の総和・最大値（最小値）を素早く計算する の続きです。 フェニック木とセグメント木の違い Binary Indexed Tree（BIT 別名 フ・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 座標圧縮 領域の個数 蟻本読書会 の続きです。 セグメント木とは？ セグメント木は、固定長配列にいくつかの操作を加えたデータ構造です。セグメント木は、基本的には以下の操作を時間計算量 O・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 半分全列挙 全探索を高速化するテクニック 蟻本読書会 の続きです。 座標圧縮とは数列 A[0], A[0], …, A[N-1] が与えられたときに、それぞれの要素が全体の中で何番目に小・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 反転 (ライツアウト) 蟻本読書会 の続きです。 全探索では全通り直接的に探索を行うので、対象の数が増えると計算量は指数関数的に増えてしまいます。半分全列挙とは、半分ずつのグループに分け・・・

続きを読む