Data Structure

AtCoder Regular Contest 085F: NRE

https://beta.atcoder.jp/contests/arc085/tasks/arc085_d配るDPともらうDPでわけわかんなくなってしまった…。 配るDPは操作を考えて、1手進めるとどこに遷移するかを考えるのが基本となります。 対して、もらうDPは漸化式を立ててからメモ化再帰に持ってい…

AtCoder Regular Contest 070E: NarrowRectangles

http://arc070.contest.atcoder.jp/tasks/arc070_c関数dpとかいうやつ。僕のいうところの「愚直に値を持つ」dpと同じです。 愚直にx座標すべて持ってみることを考えて、実は本当に持つ必要があるものは少なくて、更新も簡単にできる、みたいな感じです。 |x-…

JOI2012春day1-2: 魚

https://www.ioi-jp.org/camp/2012/2012-sp-tasks/setを使う問題といえばコレ。直方体の体積を断面図を考えて求めていく問題です。こういう問題でsetを使う際、 (1)番兵を使うと便利。 (2)lb,ubを覚えてまとめてerase(lb,ub)する。 (3)ある要素を見つけてそ…

Codeforces Round #441E: Delivery Club

http://codeforces.com/contest/875/problem/Eならし計算決めるアレです。 とりあえず距離kのとき行けるかどうかを判定する。 setでi番目まで処理し終わったとき、もう一人がどこにいるかを管理する。 i+1番目を考えて、もう一人の候補の座標としてありうる…

赤黒木

最初に これいる?要はmergeとかsplitとかできるようになった強い配列です。ここらへんを参考にして実装しました。 https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day4-copypaste-slides.pdf http://algoogle.hadrori.jp/algorithm/prbtree.html h…

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 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 072F: Dam

http://arc072.contest.atcoder.jp/submissions/1399394O(N)だからqueueとか使うのかな?と一瞬思ったが、水なんて独立に考えることが出来ないだろ!と思い、O(NlogN)で何とかしようとしたが死亡。水を入れた順番から昇順にdequeで管理することを考える。i番目…

AtCoder Regular Contest 075 E: Meaningful Mean

http://arc075.contest.atcoder.jp/tasks/arc075_c条件を数式に落とし込むと ∑(i=0→r)Ai - rK という値について考えればいいことがわかる。数式を使うと独立性に気付ける問題だった。 あとは適当に座圧してBITで数え上げればよい。 int n; //BIT 1-origin ll…

Educational Codeforces Round 23D: Imbalanced Array

http://codeforces.com/contest/817/problem/D久しぶりにコンテストに参加してみたが、全く頭が動かなかった。これくらいの問題が解けないのは大問題。コンテスト中なぜかいろいろ勘違いして最小値最大値分離出来ねえなあと思っていた。 int N; ll A[MAX_N];…