Codeforces Round 586

スポンサーリンク

A. Cards

“n”, “z” の回数だけ見ればよい.

B. Multiplication Table

$ab,ac,bc$ から $a$ が分かる.

C. Substring Game in the Lesson

初手に合法手があるならば勝ちです.合法手のうち極大なものをとればよいからです.

D. Alex and Julian

$B$ に対する判定を考えます.最大公約数で割って互いに素な場合に帰着します.偶数があるならば奇サイクルができてしまいます.奇数のみなら大丈夫です.

互いに素の仮定を外すと,$2$ で割れる回数をそろえることになります.

E. Tourism

入力は連結だとしておきます.葉といえば「始点以外で」次数 $1$ の点のことだとします.

葉を削除することを繰り返すと,始点以外の次数がすべて $2$ 以上であるようなグラフができます.このグラフの点はすべて訪れた上で最後の点も好きに選ぶことができます.二重辺連結成分分解を考えると,葉に相当する成分がサイクルを含むことから,木の Euler Tour のようにたどれるからです.

最後に終点ごとに元のグラフでの葉に向かって伸ばせるパスのスコアの最大値を加算すればよいです.

F. Gardener Alex

根の左右それぞれで解くことにします.根が左端にあるとして,右側に incremental に頂点を追加していくという状況を考えます.根から右に進み続けるパスを持っておくことにすると,これの末尾を pop しつつ,pop した部分の部分木の深さを +1 するという感じの処理になります.

G. Geolocation

全点までの距離を総和をとれば,候補となる円が得られます.

この円の中心とは異なる点をひとつとり,その点との距離をすべて試します.すると候補となる点が $O(n)$ 個にしぼられます.

これらに対して条件が成り立つかをチェックします.チェックが $O(n)$ 時間かかると計算量 $O(n^2)$ ということになります.

しかし,円の交点として $\Theta(n)$ 個の格子点が得られるというのもチェックに $\Theta(n)$ 時間かかるというのも,恣意的なケースを作ろうとしてもそんな最悪ケースは作れないのではないかと思います.さらには解となる点のひとつ?がランダム生成されているということから多少まともな実装方針はどれも TLE にならないのだと思います.

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