Codeforces Round 1011

スポンサーリンク

A. Serval and String Theory

文字種が 1 種だと不可能.2 種以上あるならば両端を使うことで 2 回あれば達成可能.1 回で可能かは全探索可能です.

B. Serval and Final MEX

長さ 4 以上ならば可能と書いてあるので長さ 4 までは適当な操作をして構いません.あとは場合分けしていくとできます.

C. Serval and The Formula

$x=y$ ならば不可能.そうでなければ大きい方が $2$ べきになるようにすれば成功です.

D. Serval and Kaitenzushi Buffet

後ろから見て $tK$ 個ごとに $t$ 個までしかとれないという条件になります.

E. Serval and Modulo

候補は sum(A) – sum(B) の約数に限定できます.これを全部試せばよいです.

F2. Serval and Colorful Array (Hard Version)

適当な凸関数最小化で通しましたが,証明は勘違いしていたので怪しいです.

集めるものの集合を固定したときに何が起こるかというと,そのうち中央にあるものを固定して,左右の近いものから寄せてくるという恰好になります($\sum_i |x-a_i|$ 最小化のあれ).よって不動となる中央要素の位置をインクリメントしながらコストを求めるというのが想定解です.

コストは左右それぞれで選んだもののインデックスの和だけから決まります.そして選び方は左右のコストの差でソートして半分ずつに切るというものです.ソートして半分ずつという形なので上下に分けてそれぞれの sum を管理します.

左右のコストは基本的には定数加算で変化していき,各要素を通り過ぎるところと $2$ つの要素の中点を通り過ぎるところで規則がずれます.これは $O(N)$ 回しか起こらないので,そこで要素を入れなおすという処理をすればよいです.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました