mayoko’s diary

プロコンとかいろいろ。

2016-04-19から1日間の記事一覧

POJ 3709: K-Anonymous Sequence

POJ

蟻本の練習です。前出た convex hull trick ですね。 ていうかこの問題だと convex hull を構成するアルゴリズムと全然関係ないですね。 問題 3709 -- K-Anonymous Sequence長さ n の単調非減少数列 a が与えられる。1 回の操作で数列の 1 つの項の値を 1 だ…

lay_contest beta round 00004 神による整地 (3)

問題 www.hackerrank.com 解法 まず基本的な解法ですが, 全部同じ値になったらそれが最適 そうでない場合は, 最大のものと最小のものを選択し, それぞれ -1, +1 する というのが最適です。この貪欲法を素直にやると 10%, map でやって少し工夫すると 30% の…