https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf elementi-bioinformatica/Two Efficient Algorithms for Linear Time Suffix Array Construction.pdf at master · Al…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2230LP双対の問題。似たような問題でLongest Shortest Pathがあるのでそれの解説スライドを見ながら考察した。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2736 まず最長距離の双…

次のグラフの最短距離問題のLP考えよう。 辺は(辺番号)/(辺のコスト)となっている。 LPは次のようになる。min(y1+3(y2)+y3+3(y4)+y5) s.t. y1+y2=1 y1-y3-y4=0 y2+y3-y5=0 y4+y5=1 y1,y2,y3,y4,y5>=0行列を使うと、 min{yb|y>=0, yA>=c}となる。ただし A= {{…

https://beta.atcoder.jp/contests/arc081Typical DP Contest FGHIJ - omochan's diary これのGとほとんど同じで、dp復元がくっついただけ。 でも1-originで逆から見ていくのでかなりこんがらがった。普通に0-originのstringを参照するときに-1をつければい…

http://tdpc.contest.atcoder.jp/PQRSは結構難しい(はず)。解いたやつから順番にあげていきます。 P 木dpするだけのO(NK^2)、と言ってしまえばおしまいだが木dpはバグらせがち。 最初点を主役にして、dpの遷移が意味不明になった。 dp[v][K]:=((vのsubtreeに…

http://tdpc.contest.atcoder.jp/K O(NlogN)ということは問題が簡単な構造をしていますね?区間dpなど複雑なものを考えないでください。 segtreeを使ってできます。 std::findはO(logN)と思っていたのでTLE出た時びっくりした。 あと区間を使う順番に気を付け…

http://tdpc.contest.atcoder.jp/F 駅に一回も止まらない方法は1or0通りなので 駅に一回は止まる方法を求めれば良い。 区間和を含んだ式になるが、大体形は決まっているので、代わりにsという値で更新を行っている。 あとは場合分けをきちんとする。 int N, …

http://tdpc.contest.atcoder.jp/assignmentsTypical DP Contestの問題が最近のCodeforcesでも出たということを聞いて埋めておこうと思った。20問あるので5問ずつに分けます。A 配列使いまわしもして十分高速だけど、boolのdpだとどっかで無駄に情報持ってな…

http://kcs.miz-miz.biz/contest/6/view/EAtCoder Grand Contest 014E: Blue and Red Tree - omochan's diaryこれと全く同じじゃん!と思ったけど微妙に違った。最初辺に注目してマージテクしようと思ったが(つまりqueueに入れるのを辺にした)、これでは新た…

KMPのK - あなたは嘘つきですかと聞かれたら「YES」と答えるブログMP法とKMP法の違い - 生きたいここを参考にさせてもらいました。KMPで求めるのはまさに蟻本p327「禁止文字列」における文字列の状態推移である。 すなわち、ある文字列TとSを比較するとして…

MP法を勉強したのでメモ。文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログこれを参考にしました。A[i]の定義はS[0:i-1]の接頭辞と接尾辞が最大何文字一致しているかである。 [0:i-1]が一致しているから…

http://poj.org/problem?id=1854蟻本には分割統治法と書いてあるがBITでやってしまった。同じ文字だったら一番右にあるのと一番左にあるのを回文のペアにするのが良くて、二番目三番目…についても同様である。 違う文字だったら、対称性よりどっちを先に端に…

http://agc014.contest.atcoder.jp/tasks/agc014_eマージテクの問題を一つ解きたくなったので。詳しくは解説に任せるが、青と赤の辺が重なっている部分を一つの頂点に併合していく感じの操作が出来れば良い。 これは各頂点から生えてる辺を持ってマージテク…

UVa Online Judge蟻本にO(NlogN)になる理由などは述べられている。実装だが、ここが本当にうまいと思った。 //a is sorted by x coordinate int m = n / 2; double x = a[m].fst; double d = min(closest_pair(a, m), closest_pair(a + m, n - m)); inplace_…

UVaデビューです。UVa Online Judge重心分解。問題はどうやってsubtree間のpathを高速に処理するか。 まず各subtreeの重心からのpathについてdamageとlengthの合計を求めておく。 それをすべて一つの配列に入れてsortして、その配列と同じ大きさのsegtreeに…

http://poj.org/problem?id=2114蟻本と同じことやるだけ…と思うがO(MNlog^2N)になって通るわけないだろ!と思い、ググってみるとどうやらそれでいけるらしいと分かったので、submitしてみるとTLE。途方に暮れているとvectorにstaticつけると速くなるよって書…

http://poj.org/problem?id=1741重心分解。解法は蟻本にある。適当に整備して使いやすいようにした。updateだけいじればよくなっている。updateも重心を根とする木について考えれば良いので楽。 namespace CD { //centroid decomposition struct edge { int …

http://poj.org/problem?id=3470平面走査するだけのタイピングゲーなんだけど、TLEがかなり厳しい。AC率308/2036が物語っている。vectorを配列にするとかベタな高速化をしてもACに至らず…segtreeが重いのかな?TLE解法 struct T { pi v; T(pi v = pi(inf, -1)…

http://poj.org/problem?id=3411問題文をよく読みましょう。(a,b)は有向辺です。無向辺でやったあとを残しておきました。 ベルマンフォードっぽくbitDPをやればよい。 int N, M; int A[20], B[20], C[20], P[20], R[20]; int dp[1 << 11][11]; int main() { …

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2266箱が1つなら簡単。 箱がmつの時はM-1個の箱がコストを節約するために使えると考えられる。 どれくらいコストを節約できるか考えよう。 あるボールを時刻sに入れ、次に入れる時刻をtとしよう。…

http://poj.org/problem?id=3680解法は蟻本にある。蟻本では負辺にあらかじめ目一杯流すことで対応しているが、ここではベルマンフォードで最初のポテンシャルを求めることによって解いてみよう。ポテンシャルh(v):=(s-v間の最短距離)と基本的にすれば良いが…

http://arc080.contest.atcoder.jp/tasks/arc080_c逆から見ると、列の偶数番目と奇数番目をとって、3つの列に分割して再帰的にまた同じようなことをする問題に言い換えられる。 しかしうまく実装する方法が思いつかず、ひたすらデバッガ使って通した。強い人…

http://arc080.contest.atcoder.jp/tasks/arc080_dまず列の差をとって区間の問題を距離が奇素数の2点を反転させてすべて0にする問題に帰着させる。座標i,jにある1を対応させるときのコストは |i-j|が奇素数→1 |i-j|が偶数→2 |i-j|が奇素数ではない奇数→3 と…

http://arc078.contest.atcoder.jp/tasks/arc078_cまず桁数を特定する。これは1, 10, 100,...と比較するとわかる。 それからは上の位から数字を特定していく。 例えば(10^3,10^4)の区間において49990を投げると、(10^3,5*10^3)でyes,[5*10^3,10^4)でNoとなる…

http://arc078.contest.atcoder.jp/tasks/arc078_d3^Nの形になるdpなんて初めて見た。まず使う辺に注目して、それらのコストの和を最大化する。 dp[S][v]:=(集合Sの点を使う際で0~v間でpathがただ一つ存在するための最大値)とする。遷移は二種類ある。 (1)pa…

http://poj.org/problem?id=3422http://hos.ac/slides/20150319_flow.pdf ここのp69に載っている問題と同じ。負辺があるが、グラフが特殊な形をしているので、dijkstraで求めても最短経路が求まり、ポテンシャルも正しく求まる。これではつまらないので負辺…

http://poj.org/problem?id=2195これも最大マッチングに毛を生やした程度。 最小コスト完全マッチング問題とか言われるやつ。namespace MCF(Minimum Cost Flow)を使っているのだがMFと書きがちなので注意。 nt H, M; int HX[MAX_N], HY[MAX_N]; int MX[MAX_N…

http://poj.org/problem?id=3068POJ 2135(蟻本p214)とほぼ一緒。 ただ今度は点も共有してはいけないので点の数を二倍にして、点の間に容量1、コスト0の辺を張って対処する。最大点素パスに毛が生えたくらい。inf = 2^30にしたらオーバーフローしてビビった。…

http://poj.org/problem?id=3155良問だと思う。hardness factorがkの時実現可能か考える。 辺と点を対応させた二部グラフを作る。 辺からそれが含む点に対して辺をはる。 そして辺にコスト1,点にコスト-kをつけると、Maximum Closure Problemに帰着できるの…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251DAGの最小パス被覆問題。パスで点を覆う際の最小本数を求める。まず二部グラフG(V,V';E)においてDAGでvからv'に辺がある時v∈V,v'∈V'に辺を張る。 すると答えは|V|-|最大マッチング|となる。有…