Educational Codeforces Round 74

スポンサーリンク

A. Prime Subtraction

$x-y\geq 2$.

B. Kill ‘Em All

max 側から貪欲に直接攻撃していきます.

C. Standard Free2play

貪欲に操作を決めていけます.

D. AB-string

両端以外の文字は必ず回文に含まれます.両隣に同じ文字があれば長さ $2$,どちらも違う文字であれば長さ $3$ の回文に含まれます.結局,ABBBB など端だけある種類というものを数えればよいです.

E. Keyboard Purchase

文字ごとの位置を決める問題です.順列 $p_0,\ldots,p_{k-1}$ を決める問題と見なせます.$\sum_{i,j}c_{i,j}|p_i-p_j|$ の形でコストが書けます.

$p_i$ が小さいところから決めていって定めた $i$ 全体の集合を保持します.$p_i$ を決めるときに,各 $j$ に対して $c_{i,j}(p_i-p-j)$ と $c_{i,j}(p_j-p_i)$ のどちらがコストになるかが保持している集合から分かるので,bit dp できます.

F. The Maximum Subtree

good tree というのは catapiller というのと同値です.良いグラフなら区間を座標昇順に見ていくと catapiller の直径部分になるし,catapiller に対応する区間を作るのも容易です.

catapiller の直径部分を作ることを考えると,最適なパスを見つける問題だといえます.適当な木 dp で答えを計算できます.

G. Adilbek and the Watering System

順に貪欲をシミュレーションすればよいです.

貪欲は,「好きに受け取る」「ただしあとで捨てることもできるとする」「使ったときにコスト発生」と解釈すると考えやすいと思います.なるべく所持するものが安くなるように受け取って、安いものから使っていきます.

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