buyoh.hateblo.jp

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

アルゴリズム

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

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

最小頂点被覆の指数時間アルゴリズムの実装(その2,分岐限定法)

その2. 2018/05/19 : note : 後日アルゴリズム含め全て書き直す可能性があります. 最終目標 これをACする. code-thanks-festival-2017-open.contest.atcoder.jp 知識 最小頂点被覆問題? グラフG=(V,E)が与えられる. 頂点集合S⊆Vを考える. 全ての辺e∈E…

最小頂点被覆の指数時間アルゴリズムの実装(その1,半分全列挙)

2018/02/22 軽く更新. その1. 最終目標 これをACする. CODE THANKS FESTIVAL 2017 - G Mixture Drug code-thanks-festival-2017-open.contest.atcoder.jp 知識 最小頂点被覆問題ってなんぞ? グラフG=(V,E)が与えられる. 頂点集合S⊆Vを考える. 全ての辺…

平面 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] が設定さ…

多項式時間で計算できる最小頂点被覆問題(最小点カバー)について

※ 2017/12/11更新:指数時間アルゴリズムについて記述 ※ 2018/02/21更新:全体的に書き直し 最小頂点被覆問題ってなんぞ? 辺集合E,頂点集合Vから成るグラフGが与えられる. 頂点集合S⊆Vを考える. 全ての辺e∈Eが,Sに含まれる頂点に接続している時,Sはグ…