Educational Codeforces Round 45

スポンサーリンク

A. Commentary Boxes

$n$ の上下最寄りの $m$ の倍数を調べる.

B. Micro-World

$(x,x+K]$ 内の要素があるものだけしか消せません.それらは昇順に消すことが可能です.

C. Bracket Sequences Concatenation Problem

個々の文字列はなるべく () をマッチさせると )))((( の形になります.このうち同じ個数で片方の種類だけが余っている ((( と ))) が求めるペアです.

D. Graph And Its Complement

$a,b$ どちらかは必ず $1$ になります.成分が複数あると,カットを考えれば補グラフは完全二部グラフを含むからです.$(a,b)=(a,1)$ で $a>1$ などを構築する場合にも $a$ 側だけのことを考えればよいので簡単です.

E. Post Lamps

それぞれの $k$ に対する最小個数を求めます.この貪欲を $O(ans)$ ステップでできれば,全体では $O(n\log n)$ ステップになります.

Just a moment...

F. Flow Control

連結成分ごとに総和が $0$ であることが必要十分.構築は全域木をとって葉側から決めていけばよいです.

G. GCD Counting

各 $d$ に対して,$d\mid g(x,y)$ となる $(x,y)$ が数えられればよいです.$d$ の倍数である点だけ取り出して森を作ります.このときの各連結成分の大きさを $n$ として $\binom{n}{2}$ の和が求めるものです.

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