指数時間アルゴリズムというのは，NP困難問題を頑張って指数時間かけて解くアルゴリズムのことで，できるだけ指数の底の小さいアルゴリズムを開発することが目指されています． コンテスト界では部分和問題の半分全列挙による2^(n/2)時間アルゴリズムなどが…

（この記事は Competitive Programming Advent Calendar の 18 日目の記事として書かれました．まだ18日です！セーフ！！！）自分はICPC時代によく嘘解法を駆使して問題を解いていたので（ジャッジの方々ごめんなさい），よく使われる嘘解法テクニックを紹介…

前回のSRMでLayCurseさんの900の解法を見て思い出したので解説。次のように、二分探索の中で全探索をしているようなプログラムを考える。 int lb = 0, ub = INF; while (ub - lb > 1) { // 二分探索 int mid = (lb + ub) / 2; boolean tmp = false; for (Sta…

以前O(n log n)の空間凸包を組もうとして挫折してずっと放置してたが、こないだの冬コンテストで出たのでそこそこ高速で楽な実装を考えてみた。 とりあえず、４点が同じ平面上に乗ってるのはないとして、 1. 点を徐々に追加していく 2. 凸包の各面が見えるか…

1. 根以外の全ての点について、入ってくる辺のコストの最小値を求め、その値をコストから引く 2. 入ってくる辺がない点が存在したら、有向木は存在しないのでそこで終了 3. コスト0の辺のみからなるグラフ上で強連結成分を計算し、それらを一つにまとめる 4.…

GCJ Round2のCがもろ単体法一発な問題だったのでやっぱり単体法は必要だと思い、ちゃんと勉強して組んでみた 改訂の方は０要素圧縮しないと速くなる気がしなかったのでやめてふつーの不等式形の単体法を組んだ C問題で使うとなると行列のサイズが8000×4くら…

SuffixArray Larsson-Sadakaneとかいう構築法とLCPの求め方などの基本的なとこを勉強した おかげでようやくこれが解けた Hopcroft-Karp 二部マッチング版Dinicみたいな感じ 予想以上の速さでここで頂点数辺数ともに100万くらいの二部マッチングが間に合った …

暇だったからいろんなMaxFlowを隣接行列でてきとーに実装してみた あるごりずむのかいせつはちょーてきとーだから間違ってるかも 1)藤重さんのスケーリング使う版 1.辺の容量の最大値をaとする 2.始点から確実にa以上の流量が届く点を探索する 3.終点まで届…