Educational Codeforces Round 72

スポンサーリンク

A. Creating a Character

str に振り分けるポイントを $x$ として,条件を満たす $x$ の範囲を求めます.

B. Zmei Gorynich

最後の 1 回を除き,$d-h$ が最大のものを使うことになります.

C. The Number Of Good Substrings

$s_l\ldots s_r$ から先頭の $0$ を除いたものを固定して数えます.そのような部分の長さは $\log_2 |s|$ 以下なので全探索可能です.

D. Coloring Edges

$2$ 色あれば目的を達成可能です.$u<v$ であるか $u>v$ であるかによって色を割り当てればよいです.$1$ 色で可能かどうかは topological sort 可能かということなのでこれも判定可能です.

E. Sum Queries?

ある桁がどちらも $0$ でないような $2$ 数は条件を満たします.そのような桁のうち一番小さい桁に注目すれば分かります.

条件を満たす集合は必ずそのような $2$ 数を含むことも分かります.よって桁ごとに,その桁が $0$ でない要素 $2$ つの和として最小なものを計算すればよいです.

F. Forced Online Queries Problem

オンラインクエリっぽい見た目ですが,なんとクエリで与えられる $(x,y)$ は,$last$ が分からなくても高々 $2$ 択にまで絞られています.

クエリ平方分割をします.バケット内のクエリで変更される可能性がある辺を列挙し,それ以外の辺については union しておきます.あとは求値クエリのたびに,足りない辺を追加して判定して巻き戻せばよいです.TLE する場合は必要な頂点(の成分)だけ残して dfs 等で判定すると log の類がつかないです.

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