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

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

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

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

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

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であり…

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

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

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

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

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…

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を持た…

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…

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 を参考にした。単調性が本質で、それを…

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

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…

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

http://arc076.contest.atcoder.jp/tasks/arc076_cわかったと思ったけどWA。よく考えてると2つの曲線の点がすべて違う辺に乗っているケースを見逃していた。どっちの端点も長方形の辺に乗っている曲線についてのみ考えればよい。 曲線を適当に0,1,2...と名前…

http://arc077.contest.atcoder.jp/tasks/arc077_bARC077に参加。CとEは結構すぐわかった。D解けないのはさすがにまずい。 余事象で考えればすぐわかる。ずっと足し合わせで求めようとして頭がこんがらがった。 でも足し合わせても求められるくらい頭良くし…