けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2018-09-18から1日間の記事一覧

AtCoder ARC 091 E - LISDL (青色, 700 点)

問題へのリンク 問題概要 1, 2, ..., N を並べ替えてできる列であって、以下の条件を満たすものがあるかどうか判定し、あればその例をひとつ構成せよ: 最長増加部分列の長さは A 最長減少部分列の長さは B 制約 1 <= N, A, B <= 3 × 105 解法 LIS and LDS と…

CS Academy 070 DIV1 E - Squared Ends

Convex Hull Trick の練習に。 問題へのリンク 問題概要 長さ の数列 が与えられる。数列を 個の区間に分割して、各区間 [, ] についての の総和を最小にせよ。 制約 解法 いかにも な DP になるのを頑張って高速化する系の問題。2 乗だから convex hull tri…

COLOCON 2018 Final C - スペースエクスプローラー高橋君 (600 点)

Convex Hull Trick の練習に。DP ではないけど、DP 高速化でよくやる Convex Hull Trick の構造そのものを試せる問題。Convex Hull Trick についての詳しい解説は Convex-Hull Trick (satanic さん) がとてもわかりやすい! 問題へのリンク 問題概要 長さ の…