JAG夏合宿 Day 2 - DEGwerのブログ

オンラインでゆるーく参加してました。

〜11:00 Codeforcesを解いている。
11:02 コンテストの存在に気付く。
JAGなのでどうせ解けないからやるだけ解くのはやめてむずかしめな問題を考えるだけ考えようと思う。
いろんな問題を開ける。
C座標圧縮+累積和しか見えない。
書きだす。
よく考えたら座標と座標-1と両方持ってたらMLEするよね
別の問題考えよう。
H問題が目に留まる。面白そう。
動かすのを最小にするっていうことは、動かさないのを最大にするっていうことだよね
動かさないのは単調増加数列
ということは、もっともコストの大きい単調増加な部分列を求めればいいんだよね
なんだけLISににてる
n<=100000だからLIS-2の応用だろうなぁ
LIS-2するとメモリがO(n^2)になってやばそう
突然のLIS-1
最小値を求めるところにRMQ使えばn log nでいける？
実装
RMQ速いけど微妙にバグる
と思ってたらsegtreeの実装間違ってました
(max(a,b)とすうところをa+=bとかしてた)
BITの書きすぎである
直す。動く。
一発AC.
これならと思いAをかく。
さすがにAC.
Cに帰ってくる。
座標-1って持つ必要なかったよね
upper_boundとか盛大につかって書く。
一発AC.
まるかいてとかおもしろそう
空白から考えて、もともと丸のところは負のコストにして...
空白からどう作るのかわからず絶望。
塾に行く時間になってしまったのでおわり。
帰ってきたら17位でした。