POJ 3690: Constellations

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

SA+LCP+RMQ

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

SA-IS

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…

AOJ2230: How to Create a Good Game

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考えよう。 辺は(辺番号)/(辺のコスト)となっている。 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= {{…

AtCoder Regular Contest 081E: Don't Be a Subsequence

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

Typical Dp Contest PQRST

DP

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

Typical DP Contest KLMNO

DP

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

Typical DP Contest FGHIJ

DP

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

Typical DP Contest ABCDE

DP

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

Yosupo Wettbewerb E: Oh, Vertexes & Edges!

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

KMP法

KMP

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

MP法

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

POJ 1854: Evil Straw Warts Live

BIT

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

AtCoder Grand Contest 014E: Blue and Red Tree

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

UVa 10245: The Closest Pair Problem

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 12161: Ironman Race in Treeland

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

POJ 2114: Boatherds

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

POJ 1741: Tree

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

POJ 3470: Wall

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

POJ 3411: Paid Roads

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() { …

AOJ 2266: Cache Strategy

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

POJ 3680: Intervals

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

AtCoder Regular Contest 080E: Young Maids

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

AtCoder Regular Contest 080F: Prime Flip

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

AtCoder Regular Contest 078E: Awkward Response

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となる…

AtCoder Regular Contest 078F: Mole and Abandoned Mine

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

POJ 3422: Kaka's Matrix Travels

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

POJ 2195: Going Home

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…

POJ 3068: "Shortest" pair of paths

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