kazuma8128’s blog

競プロの面白い問題を解きます

2018-02-28から1日間の記事一覧

Codeforces Round #463 F Escape Through Leaf

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

傾きの単調性が要らない Convex Hull Trick

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