(P||Q||...)&(R||S||...)みたいな連言標準形で書かれた論理式を真にする割り当てはあるかを判定する問題をSATといいます。 2-SATの場合カッコ内のリテラル数が高々2つ、つまり(P||Q)&(R||S)みたいになってます。2-SATの解き方は蟻本の通り、SCCを使って真のn…

Euler Tourは木を直線にして扱いやすくするテクニックです。 これを使うとLCA、二点間のpathの長さがO(logN)で求められます。でもHL分解ならあるpath上の辺の長さをすべて+1するみたいなこともできるので、汎用性はHL分解の方が上です。 HL分解は実装が重い…

永続は怖いイメージがあると思いますが、segtreeくらいなら簡単に永続化できます。 単にupdateされる予定のnodeを複製して、その複製されたnodeに対してupdateを行えばいいです。 普通のセグ木に複製してリンクを張り替えるコストが増えただけで更新の計算量…

http://agc017.contest.atcoder.jp/tasks/agc017_c解説を見るとこんなうまいやり方があったのかぁ…となるんですが、それをどうやって思いつけるようになるかが重要だと思います。 僕はこう考えたらしっくりきました。まず魔法をかける前、ボールがどうなって…

http://agc017.contest.atcoder.jp/tasks/agc017_d(ある点vのsubtree)と(vから親pへ向かう辺)で構成されるグラフについてgrundyが求まれば、あとはXORをとれば、pのsubtreeに対してgrundy(p)が求まります。grundy(v)は再帰的に求まるとして、このグラフにvか…

grundy数について勉強したのでお話します。grundy数はご存知の通り、ゲームの勝敗を求める際に使う数なのですが、こんな感じの性質があると思います。1.grundy数は非負整数であり、grundy数=0ならば負け、grundy数>=1ならば勝ちを意味する。 2.grundy数=kの…

http://poj.org/problem?id=3690蟻本に書いてあるように二次元hashをすればいいです。hashといえばこの記事 http://hos.ac/blog/#blog0003 が有名ですが、ここに書いてあるように3つのmodでhashをとるようにしてみました。注意：TLE解法です。 struct ll3 { …

SA+LCP+RMQで任意の2つのsuffixの組について先頭何文字が一致しているかをlog(N)で求めることができる。 前処理も全部O(N)でやることもでき、高速。(下のコードはRMQの前処理がO(NlogN)だが)HL分解した木に乗せることを考えながらライブラリ化した。 struct …

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つの列に分割して再帰的にまた同じようなことをする問題に言い換えられる。 しかしうまく実装する方法が思いつかず、ひたすらデバッガ使って通した。強い人…