Segment Tree

yukicoder埋め

https://yukicoder.me/problems/no/753dp[level][bit][winner]:level段のトーナメントをbitに属す挑戦者で作る。勝者がwinnerの時の場合の数 として求めます。高速化いろいろしてAC。https://yukicoder.me/problems/no/749和と積のクエリが混ざっている時っ…

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1)

https://codeforces.com/contest/1074DEFを見ただけですが…D 区間をsetで持っておけば奈良市計算量決められるやつ。 E 気合としか言いようがない。基本2*2の回転でできますが、最後だけ2*3の回転をいれて調整します。 F euler tourすれば区間をたかだか3つ足…

VK Cup 2018 - Round 1

http://codeforces.com/problemset/problem/923/DA 良問。どこまで減らせるかが貪欲で求まる。 B 雪山について独立に考えれば。 C よくあるbitのやつ。これtrieでやるのかなぁ…segtreeっぽくしちゃったけど。また使いそうなので貼っときます。 int K = 1; st…

Codeforces Round #497 (Div. 1)

https://codeforces.com/contest/1007A 普通にループ回しましょう。 B 包除原理で美しく書きましょう。 C やりたくない… D 2-SATだけど、普通にやったら間に合わないのでsegtreeっぽく構築するやつですね。HL分解すれば論理式がO(Nlog^2N)個になって多分解け…

精進7/15

https://beta.atcoder.jp/contests/agc026/tasks/agc026_b BとDの最大公約数が肝になることがわかればほとんど解けたようなもんですが、他の自明な条件も忘れないように。 https://beta.atcoder.jp/contests/agc026/tasks/agc026_c 文字列の前N字について割…

Codeforces Round #482 (Div. 2)

http://codeforces.com/contest/979順位はそんな悪くないんですが…A n=0〜 B 奇数偶数やろ…となるんですが違います C えぇ… D 追加は約数個のオーダーだし、答える時は、segtreeっぽく範囲を狭めていきます。問題文が無駄に複雑。やめて。 考察は一瞬でした…

永続segtree

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

SA+LCP+RMQ

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

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]と表せるのでそこに含まれる最大の人の数を求めればよい。…