pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Convex Hull Trick

天下一プログラマーコンテスト 2016 本戦: E - 串焼きパーティ

http://tenka1-2016-final-open.contest.atcoder.jp/tasks/tenka1_2016_final_e

Codeforces Round #351 (Div. 1) C. Levels and Regions

3 時間近く掛けてようやく AC。 http://codeforces.com/contest/674/problem/C 問題 数列 t[i] が与えられる。これを K 個の連続する部分列に分割する。各部分列はゲームにおけるレベルに対応しており、プレイヤーはレベル 1 からレベル K の順に攻略してい…

Codeforces Round #344 (Div. 2) E. Product Sum

Convex Hull Trick は蟻本にも書いてあるらしいが知らなかった。 codeforces.com 問題概要 サイズ n の配列 a が与えられる。配列の characteristic は $\sum_{i=1}^n a_i \cdot i$ で定められる。 一回だけ配列の要素をひとつ抜き取って好きな場所に挿入す…