メモ

2020/10/31

ARC107 D 分数を管理するのは嫌な気持ちになる →先に2^(十分大きい数)を掛けておく? →DPの状態数が破滅 2倍すると再帰的になることに気づいていなかった(結局分割数のようなものを求めたいので、同様の方針で考えるべきだった) 今まで使った数の最大値(or…

Push-Relabel メモ

Push-Relabel 最大流を求めるアルゴリズム O(V^2 √E) (the highest label selection ruleを使用) ざっくりと、容量を無視して流した後、流しすぎた分を削っていく感じ 手順 Dinic等と同様に残余辺も考え、各頂点に対し以下を定義する 流量f<最大流量cである…

Main-Lorentz algorithm メモ

文字列Sのrun s[i,...,j] であって、区間長の半分以下の周期を含み、左or右に一つ伸ばせないもの 長さaのrunはO(|S| log a)で列挙できる 全てのrunの個数はO(|S|) 文字列Sに含まれる全てのrunO(|S| log |S|)で列挙する www.sciencedirect.com Finding repeti…

LIS メモ

数列A=a_1,a_2,...a_NのLISを求める 二分探索 dp[i]:=長さiの増加列の末尾の要素の最小値 ISの長さが長いほど末尾の要素は大きくなっていくので、このテーブルは単調増加になる a_1から順にdpテーブル上を二分探索し、末尾の値を更新していく 更新時に、数列…

std::complex メモ

メリット:回転・拡大を自作ライブラリなしで実装できる デメリット:遅い 各種operatorでvectorの加算と拡大回転ができる complex<db> a,b; a*=b;//abs(b)倍拡大、arg(b)だけ反時計回りに回転 a/=b;1/abs(b)倍拡大、arg(b)だけ時計回りに回転 カンマ区切りで実</db>…

並列二分探索 メモ

簡単のため、二分探索の走査範囲を[0,N]とする 二分探索で必要となる情報は、ある値midに対して条件を満たすかどうか(求めたい”境界の値”はmidの左側と右側のどちらの区間に含まれるのか) midを一段階進めるごとに、境界の値が含まれる区間の長さが半分にな…

Sum over Subsets DP (SOS DP) メモ

いわゆる高速ゼータ変換 集合Sに対応する値をa_Sと表記する 下位集合をまとめるタイプ dp[i][mask]:=maskの部分集合であって、i<=xをみたすようなx bit目はmaskと一致するような部分集合についての値(maskごとの累積和) dp[0][mask]=a_mask として、 i bit目…

競技プログラミング 海外資料まとめ

自分用メモ Bin search and relative error 実数の範囲で[l,r]を二分探索する際、1<=lならmidを相乗平均にするべき https://codeforces.com/blog/entry/49189 Dynamic Programming Optimizations DP高速化テクのまとめ https://codeforces.com/blog/entry/82…

幾何 メモ

二直線の交点 http://www.fumiononaka.com/Business/html5/FN1312003.html 線分と頂点の距離 線分の端点との距離or直線との距離 で場合分け 線分と線分の距離 交差する場合は0 しない場合は端点の組み合わせを全探索 点の多角形に対する内外判定 crossing nu…

manacher法 メモ

文字列sの各位置に対して、そこを中心とする回文の最長半径をO(|s|)で求める やってることはかなりシンプルで、回文の対称性を使って調べた部分を使い回そうねという話 例:奇数長回文の場合 abcbaba 1131121 例:偶数長回文の場合は境界から見る abccbabba …

MP法 メモ

文字列sの各prefixに対して、そのprefixとsuffixが一致する最大の長さをO(|s|)で取得する できること 各prefixについて、その最小周期を求める substr(0,i)の最小周期はi-res[i]とかける 証明 string sの先頭r文字と末尾r文字が一致するとき(⇔substr(0,r)==s…

ランレングス圧縮 メモ

操作区間の長さに対して、区間内の要素の種類数が十分少なくなるような操作 →ランレングス圧縮により、区間に対する操作の計算量をO(区間長)からO(区間内の要素の種類数)に落とせる →各項の値に上限があるときに、単調な列を作ることがO(n)でできたりする (…

Dynamic 2D-BIT メモ

何がしたい? H*Wの二次元配列に対し、一点更新(加算)、長方形和取得 (H,W<=10^18、更新する点の個数<=10^6) 実装方法 BITを持つ配列でBITを作る 全ての座標の情報を持つことはできない→必要な部分だけ作る 更新する点の座標のリストを持ち、(x,y)でソート…

HL分解 メモ

HL分解とは? いくつかの頂点を一つの頂点に圧縮し、部分木を全て、深さの最大値がlog(頂点数)であるようなパスグラフにする 何ができる? 木に対するパスクエリを高速に処理できるようになる 実装 1.適当な根を定め、各頂点に対し部分木のサイズを求める …

z-algorithm メモ

vector<int> Zalgo(string &s) { int n = (int)s.size(); vector<int> res(n , 0); res[0] = 0; int j=1;//最も右まで調べたときの左端の値 for (int i = 1; i <= n; ++i){ if(j+res[j]<=i){//未到達の場所に来た res[i]=0; }else{ res[i]=min(res[j]-i+j,res[i-j]); }</int></int>…

プログラミングコンテストの問題を解くのに役立つサイトまとめ

オンライン整数列大辞典 https://oeis.org/?language=japanese 数列の各項の値から、数列の名前や一般項を検索することができる 謎の数列が生えたときに規則を調べるのに使える DESMOS(グラフ描画) https://www.desmos.com/calculator PC上でxy平面上のグラ…