Educational Codeforces Round 46

スポンサーリンク

A. Codehorses T-shirts

コスト 0 か 1 のものしかないので完全一致のものを除いて個数を見ればよいです.

B. Light It Up

何もしない場合のオン・オフになっているところの累積和を求めておきます.挿入場所を決めたときには左側のオンと右側のオフの長さを足します.

C. Covered Points Count

座圧して累積和を使って被覆回数を求める.

D. Yet Another Problem On a Subsequence

dp で解けます.あといくつ要素を先頭以外で消費しなければいけないかを状態とします.

E. We Need More Bosses

二重辺連結成分と橋で木を作って直径です.

F. One Occurrence

$R$ をインクリメントさせながら,各要素の最後の出現に注目します.同じ要素の直前の出現が一番大きなものが候補となります.

G. Two-Paths

パス上の辺はちょうど 1 回で,そこで通る点について,パスが通らない部分木方向への寄り道で正の得点が得られるならば足すということになります.

各頂点 $v$ と親 $p$ に対して,$p$ から $v, par[v]$ 方向にはいかずに元の場所に戻ってくる場合の最大スコアなどを前計算しておけばおおよそパス上の和の計算に帰着できます.

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