Segment Tree

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

AtCoder Regular Contest 080E: Young Maids

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

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で表して行列…

Codeforces Round #423D: Best Edge Weight

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

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 076F: Exhausted?

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