脳log[20220427]

2022年04月27日 (水) [AtCoder] 精進。先週あったモノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249）-F「Ignore Operations」(青 diff)。コンテスト当日は同じ青 diff だけど F より難しいことになっている E 問題「RLE」で詰まっていた。E 問題は制約上限が 3000 なんだけど愚直にやると N の３乗になって TLE が避けられない。最内ループの足し上げる部分をなんとかしたかったけどどうにもならなかった。N<300 くらいまでしか間に合わない。■さておき F 問題。まずどの t=1 を無視しないかを決める。そうするとそれより前にある操作は存在しないのと同じ。それより後にある t=1 はすべて無視しなければいけない。後にある t=2 のうち 0<=y のものは当然無視せず(K を消費せず)最大値に寄与させる。後にある t=2 のうち y<0 のものは小さいものから無視できるだけ無視する。問題はこれをどう効率良く処理するか。特に負の y の累積和。ソート済みの状態を保ちながら y を順次追加しつつ、その累積和を利用したい。■提出 #31310696 (AC / 1130 Byte / 520 ms)。BIT を２本使ってがんばる。■そうだ思い出した。E 問題で詰まっていたのは本当だけど、D 問題を諦めて飛ばした上で詰まっていたのだった(つまり３完)。D 問題の制約上限 20 万にびびって手がつけられなかったのだけど、解説を読めば「さて、実は……」とか書いてある。それがわかんねーんだよな。10 数個だけ解けずに残っている選ばれし緑 diff の１つ「Coprime」の仲間だと思った(それなら解けない)。