今日の競プロ(2020/4/25) - gyouzasushi’s diary

シンプルに手も足も出んくて悔しい。解説AC。

とりあえずそれぞれの場所を切断するかどうかだけを考える。ナップサックに荷物を入れるか入れないかを考えるのと一緒。そこから肉付けしてったらいける。

ABCでみたね。

$f(p_1(n))$ を基準に差分を足し引きしていく。 $k$ を $1$ から $n$ まで動かすと、 $|pos(p_k(n), x_i)-pos(p_k(n), x_{i+1})|$ の値は $k$ が $x_i$ をまたぐときと $x_{i+1}$ をまたぐときだけ変化する。

$(2^{20})^2$ 回くらいかかる解法しか思いつかなくて、でもそもそも答えの候補20個しかないしなあ、と思いながらダメ元で枝刈りしてたらACしちゃった。想定ではなさそう、明日 editorial 読む。