AGC050(Good Bye rng_58 Day 1) 参加記

久しぶりに良いパフォーマンスが出た

A 問題

非自明すぎる

$i$ から $max(i+1, i+\lfloor(N-i+1)/2\rfloor)$ に張ったらできました 証明はしてないので自分で $O(N^3)$ ジャッジを書きました

B 問題

たぶん公式解説より簡単

$f(l,r,b)\ (0\leq l,r<N, b=0,1)$ を、「$[l,r)$ で操作したときにおける和の最大値、ただし $b=1$ のときは $[l,r)$ にすべてコインが置いてある状態から操作を始める」とすると、メモ化再帰で $O(N^3)$ で求められる

C 問題

難しい まず B 同士の距離の条件に帰着させる、これはだいぶ自明 前から DP しようとすると何をどうしても $O(N^3)$ になってしまって、計算量が償却で落ちないかな〜みたいなことを考えると後ろからやりたくなる

後ろから DFS する感じで探索することを考えると B の距離としてよい最小値の個数が $O(\log N)$ に落ちて、後ろから DP するのを累積和で高速化すれば $O(NlogN)$ になる

感想

これくらいのパフォーマンスが安定すれば橙には食い込めるんですよね