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にしたらオーバーフローしてビビった。…

POJ 3155: Hard Life

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

AOJ 2251: Merry Christmas

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

POJ 2226: Muddy Fields

http://poj.org/problem?id=2226なるべく長い板を置いていく。 あとは板の縦方向の置き方と横方向の置き方を点に、草を辺に対応させて二部グラフを作り、最小点カバーを求めれば良い。 int H, W; int N, M; char F[60][60]; int X[60][60]; int Y[60][60]; i…

POJ 2724: Purifying Machine

http://poj.org/problem?id=2724omochan.hatenablog.com ↑これとほとんど同じ。 一気に*を使って消せるやつ同士に辺を張ったグラフは2部グラフとなる。 2部グラフになるためには任意のサイクルの大きさが偶数であればよいが、Nコのbitのうち1つ変えるという…

POJ 3692: Kindergarten

http://poj.org/problem?id=3692男女がお互いを知っている最大の集合を求める。 これは男女がお互いを知らない、ということはない最大の集合であるので、 知り合いではない男女を辺でつないで最大安定集合を求めれば良い。 あとは|最大安定集合|=V-|最大マッ…

POJ 1466: Girls and Boys

http://poj.org/problem?id=1466最大安定集合を求める。 二部グラフになるので|最小点カバー|=|最大マッチング|、 任意のグラフについて|最小点カバー|+|最大安定集合|=|V|よりできる。 頂点を2倍にしてあげると実装が楽。 簡単な証明いろいろ。 |最大マッチ…

POJ 1486: Sorting Slides

http://poj.org/problem?id=1486完全マッチングに必ず使われる辺を答えればよい。 それはフローが流れた辺を削除したとき完全マッチングになるかどうかで判断すればよい。その際に押し戻すテクを使ってN-1のフローを作り、対象の辺の容量を0にしてdfsすると…

POJ 2112: Optimal Milking

にぶたんして最大流流す。にぶたんの初期値を小さくしすぎてWA出した… struct edge {int to, cap, rev; }; vector<edge> G[MAX_N]; bool used[MAX_N]; void add_edge(int from, int to, int cap) { G[from].push_back((edge){to, cap, (int)G[to].size()}); G[to].</edge>…

POJ 2914: Minimum Cut

http://poj.org/problem?id=2914これもフローとはまた違った話。全域最小カット。Stoer–Wagnerを使う。Stoer–Wagnerは 「点の集合からの辺のコストの合計が大きいもの点から取っていって、最後から二番目に取った点sと最後に取った点tの最小カットは tから生…

POJ 3713: Transferring Sylla

Mengerの定理より全域最小点カットを求めれば良い。すべての点対に対してフローを流せばできるが、それではTLE。 全域最小辺カットならO(V^3)のアルゴリズム(Stoer-Wagner)が存在するが、全域最小点カットは見つけられなかった。全域最小点カットが2以上にな…

POJ 2987: Firing

http://poj.org/problem?id=2987はじめてフローでまともな問題解いたかもしれない。maximum closure problemという有名問題。↓wiki参照。 https://en.wikipedia.org/wiki/Closure_problem何個使うかも答えなければいけないが、それはmin-cutを得る際の(cap>0…

POJいろいろ8/3

3109 http://poj.org/problem?id=3109座標圧縮+平面走査segtree。実装ややこしいはずだけど一発で通って気持ちがいい。実装ちゃんと練ればすんなりいくんだね。3735 http://poj.org/problem?id=37351+B+B^2...の形が出てくるので行列の累乗和を貼って終了、…

POJいろいろ8/2

2441 http://poj.org/problem?id=2441bitdpやるだけしたら3938MS/4000MSで超ギリギリだったw3254 http://poj.org/problem?id=3254sampleも一発で通って気持ちがいい。bitdp。3420 http://poj.org/problem?id=3420行列累乗。一行ごとのstateをbitで表して行列…

POJいろいろ8/1

3185 http://poj.org/problem?id=3185普通に端から反転させるだけ…と思ったが、端の場合分けで反転の回数カウントしていなくてWA生やしまくった。1222 http://poj.org/problem?id=1222これも端を決めて反転するだけ。反転は決めることが本質。2100 http://po…

POJ 3045: Cow Acrobats

http://poj.org/problem?id=3045上からi-1番目まで決めているとする。i-1番目までの重さをWとすれば i番目とi+1番目のriskは W-S[i] W+A[i]-S[i+1](Aは重さ)となる。ここでi番目とi+1番目のcowを入れ替えてみるW-S[i+1] W+A[i+1]-S[i]となる。 W-S[i] W+A[i]…

AOJ 0531: Paint Color

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531 座標圧縮+二次元imos。久しぶりに二次元imosしたけどこっちはうまくいった。座標圧縮で少しこんがらがった。 長方形の辺が存在しない区間の長さを1にする感じ。 int fd(const vector<int>& vec, i</int>…

POJ2010: Moo University - Financial Aid

http://poj.org/problem?id=2010蟻本でpriority_queueと二分探索のどちらでも取り上げられているように解法が2通りある。1. http://omochan.hatenablog.com/entry/2017/06/30/214614 この問題と同じように、真ん中を決めてしまえば独立に考えられるので前後…

POJ 3104: Drying他

蟻本少しずつ埋めます。http://poj.org/problem?id=3104POJ久しぶりにしたので注意点を。(POJ以外の注意点もあり) cout,cinはios::sync_with_stdio(false)にしても遅いのでprintf,scanfを使う。 c++11は使えないのでtemplateらへんでcompile errorが生えるの…

AtCoder Regular Contest 078D: Fennec VS. Snuke

http://arc078.contest.atcoder.jp/tasks/arc078_b解法自体は簡単だけど、バグらせたので。 こういう境界でバグらせやすい問題は[a b)の区間で考えるのがよさそう。 [a (a+b)/2)にすると半分、またはそれより1小さくなり、 [a (a+b+1)/2)にすると半分、また…

Codeforces Round #423E: Rusty String

FFT

http://codeforces.com/contest/827/problem/E初FFTですk periodである条件は|i-j|%k=0かつS[i]とS[j]がそれぞれVとKであるi,jが存在しないことである。 そこで、S[i]='V'ならばA[i]=1でありそれ以外の要素は0である配列Aと、S[N-i-j]='V'ならばB[i]=1であり…

Codeforces Round #423D: Best Edge Weight

初HL分解です。http://codeforces.com/contest/827/problem/D解法自体は簡単で、ある辺について、それを含むループの中の辺での最大cost-1が答えとなる。 これはMSTを作ってHL分解すればできる。snukeさんのコードを参考にした。 HL以外のところでめちゃくち…

Codeforces Round #421B: Mister B and PR Shifts

http://codeforces.com/contest/819/problem/B傾きと切片を持って適当にやればいい…がvectorの形で保持したらTLEぎりぎりになってしまった。 累積和でやりましょう。 あとmodの条件もいろいろ勘違いして結構バグらせた。 modは1違うだけで値が劇的に変わった…

Codeforces Round #419C: Karen and Supermarket

http://codeforces.com/contest/815/problem/C3乗っぽいけど2乗な木dp。 5000*5000*2のlong longの配列持ったらMLEした。 さらに初期化を適当にやりすぎてO(N^3)になってしまった。 直してAC。 int N, B; vector<int> G[MAX_N]; int dp[MAX_N][MAX_N][2]; int dp2</int>…

Codeforces Round #423B: High Load

http://codeforces.com/contest/827/problem/B最初にrootを一つ決めて、あとはkコずつrootからまんべんなくつけていけば、木の高さが最小、かつその時の一番rootから離れているedgeの個数も最小になるのでこれが求めるグラフとなる。 int N, K; void solve()…

Codeforces Round #423C: DNA Evolution

http://codeforces.com/contest/827/problem/Ce int n; ll sum(ll *bit, int i) { ll s = 0; while(i > 0) { s += bit[i]; i -= i & -i; } return s; } void add(ll *bit, int i, ll x) { while(i <= n) { bit[i] += x; i += i & -i; } } struct query { int…

AtCoder Regular Contest 073F: Many Moves

http://arc073.contest.atcoder.jp/tasks/arc073_ddp高速化。dp[i][j]:=(i番目のqueryまで処理して、2点の座標がx[i]とjの時の最小値)とする。 するとdp[i][j]+jとdp[i][j]-jの値についてrange_sumとrange_minが出来れば高速に更新できる。2つsegtreeを持た…

AtCoder Regular Contest 074: Lotus Leaves

http://arc074.contest.atcoder.jp/tasks/arc074_dflow。行と列を代表する頂点を用意してうまく辺を張ると、辺の本数がO(H*W)になって十分高速。 int H, W; string S[MAX_N]; void solve() { cin >> H >> W; int s, t; rep(i, 0, H) { cin >> S[i]; rep(j, 0…

AOJ 2415: Sashimi

DP

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415 monge(もんじゅ)dp。http://topcoder.g.hatena.ne.jp/spaghetti_source/20120915 と http://sssslide.com/www.slideshare.net/ikumihide/ss-50881829 を参考にした。単調性が本質で、それを…

AtCoder Regular Contest 076F: Exhausted?

http://arc076.contest.atcoder.jp/tasks/arc076_d flowのお勉強。Hallの結婚定理より、人の集合Xの誰かが座れる椅子の集合をP(X)と置けば必要な椅子の数はX-P(X)である。椅子の集合は[0,L]or[R,M+1]と表せるのでそこに含まれる最大の人の数を求めればよい。…

AtCoder Regular Contest 072D: Alice&Brown

http://arc072.contest.atcoder.jp/tasks/arc072_bゲームこわいと思ったが、終了状態が(0,1)か(1,1)なのだから、そこからbacktrackしたら結局abs(X-Y) (Brownの勝利)となることがすぐわかる。 ll N, M; void solve() { cin >> N >> M; if(abs(N - M) <= 1) c…