問題文 http://codeforces.com/contest/932/problem/F 問題概要 問題文が短いので省略 解法 木DPのイメージでやると, 頂点 v に対して dp[v] = min{ a[v] * b[u] + dp[u] } (u は v の子孫) という式が立つので, Convex Hull Trick で求まりそうな形になりま…

はじめに 傾きに単調性がなくても insert ができる Convex Hull Trick を書きたいなーと思ったものの, 平衡二分木で書くのはめんどくさそうだし定数倍遅そうとか考えて色々調べてたら, セグメントツリーを使った簡単な方法を見つけたので, 備忘録的に書いて…

問題文 http://codeforces.com/contest/464/problem/E 問題概要 頂点数 n 辺数 m の無向グラフが与えられるので, 頂点 s から 頂点 t までの最短経路を求めよ. 存在しない場合は-1, 複数ある場合はどれでもよい. ただし辺のコストは, 辺ごとに x_i が与えら…

問題文 https://www.codechef.com/problems/ELPHANT IOI 2011 の問題なのでこっちでも見れます. https://www.ioi-jp.org/ioi/2011/tasks/day2/elephants_jpn.pdf 問題概要 直線状にいる N 匹の象を幅 L まで撮れるカメラで撮る. 全匹を撮るための最小の撮影…

問題文 https://www.codechef.com/problems/GPD 問題概要 頂点数 N の根付き木が与えられる. 各頂点には正整数のキーが付いている. 以下の二種類の Q 個のクエリをオンラインで処理せよ.クエリ１：頂点 v の子に, キー k の付いた新しい頂点 u を増やす クエ…

この間， AOJ にある Do use segment tree とかいう問題を解きなおしたときに今まで持っていた遅延評価 Segment Tree で無理やり書こうとしたら，無限にバグらせて結局一から書き直す羽目になったので，そのとき考えたことについて書きます． 間違っていると…