buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

アルゴリズム

データアクセスに制限のある Binary Indexed Tree () の高速化

タイトルについて 正しくは「データアクセスに制限のある Binary Indexed Tree (と同じクエリに答えるデータ構造) の高速化」です Binary Indexed Tree とは 以下のクエリに時間O(logN)で答えることが出来るデータ構造. 初期化 サイズNの配列の要素を0に初…

平面 traveling salesman problem の厳密解を求める.

平面tspの分岐限定法のコードをなんとなく書いてみたけれども,全然早くならなかった. Traveling Salesman Problem (TSP) N個の都市と都市間の距離が与えられる.全ての都市をちょうど一度ずつ巡って始点に戻る順回路の中で移動距離が最小のものを出力する…

Kの重複を許す区間スケジューリング問題

2018/02/22 更新 文章を修正 区間スケジューリング問題 http://www.prefield.com/algorithm/misc/interval_scheduling.html から引用. 区間スケジューリングは次の問題である.仕事が n 個与えられる.各仕事 j には開始時刻 s[j] と終了時刻 f[j] が設定さ…

2部グラフ上の重み付き最小点カバー問題を解くアルゴリズム

※ 2017/12/11更新:指数時間アルゴリズムについて記述 ※ 2018/02/21更新:全体的に書き直し ※ 2018/11/02更新:2部グラフのケースのみ残し,タイトルを変更. 最小点カバー問題 辺集合E,頂点集合V,頂点重みw(v)から成るグラフGが与えられる. 頂点集合S⊆V…