Codeforces Round 1054

A. Be Positive

$0$ は $1$ にしてしまいます.そのうえで $-1$ が奇数個ならこれをひとつ $1$ にします.

B. Unconventional Pairs

ソートして昇順に $2$ 個ずつ取っていくのが最適解のひとつです.

C. MEX rose

$K$ であるものを何かに変更させる必要があります.

$K$ 未満で存在しない値は作る必要があります.

D. A and B

b を集める問題だとして,prefix と suffix に a を集めます.

prefix, suffix に集める個数を決めると,コストはインデックスの和から求まります.

E. Hidden Knowledge of the Ancients

尺取り法で各 $L$ について,$[L,R]$ が $K-1$ 種類以下であるような最大の $R$ や,$[L,R]$ が $K$ 種類以下であるような最大の $R$ が求まります.ここからちょうど $K$ 種類になるような長さの範囲が求まります.

F. Nezuko in the Clearing

答で二分探索します.目標時刻を決めると休憩回数が決まります.休憩回数を $k$ 回とすると移動は $k+1$ 個の連続移動に分割されます.ここになるべく均等に割り振るのが最適です.まずは最終的に正の体力かどうかを判定します.最終的に正であるとき,消費体力の大きな移動を後回しにすることで常に正にできるのでこれで大丈夫です.

G. Buratsuta 3

全体の $1/3$ より多くを占めるものは,互いに異なる $3$ 要素を削除することを繰り返しても生き残ります.この方法で生き残る高々 $2$ 種類を区間集約値としてセグメント木にのせます.これで,候補が高々 $2$ 種類になるので最後にチェックします.

出力形式はよく読みましょう.昇順出力や,サンプルにはありませんが -1 出力など.

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