チラチラチラ裏

\主に競プロ備忘録/

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

ARC 068 E - Snuke Line

問題 問題概要 N個の区間[l_i,r_i],自然数Mが与えられる. 1 <= d <= Mについて,dの倍数を含む区間はいくつあるかそれぞれ答えよ. 1 <= N <= 3*105, 1 <= M <=105 解法 まず,各dについてr_i - l_i >= d-1 となる区間は必ず倍数を含む. よって r_i - l_i でソ…

yukicoder No.595 登山

問題 問題概要 要素数Nの数列{a_i}とコストPが与えられる. 任意の場所へのワープにはコストP,隣接するiからjへのの移動にはmax(0,a[i]-a[j])かかる時,全ての点を訪れる最小コストを求めよ. 2 <= N <= 2*105, 0 <= P,a[i] <= 109 解法 1 普通のDP 解説が詳し…

yukicoder No.649 ここでちょっとQK!

問題 問題概要 自然数K,Qが与えられる.以下のクエリQ個を処理せよ. 1. 配列に値Xを挿入する 2. 配列のK番目に大きい値を出力し,削除する 1 <= Q,K <= 2*105, 1 <= X <= 1018 解法 想定解で解いた. minキューとmaxキューを用意し,maxキューにはK番目に小さい…