Codeforces Round #670 感想

総括

C...

Problem A

n個の非負整数を2つの集合A,B（片方が空でもいい）に分けて、各集合に含まれない最小の数mexAとmexBの和を最大化せよ

考えたこと

• 0が1つも与えられないなら0
• 小さい数から注目するのがよさそう
• 集合に要素を追加しながら考えていくイメージ
• 整数iについて、可能なら両方の集合に入れたい
• そのためには2個以上ないとダメ
• 小さい順にみていって、初めて2個未満の数はmexAになる
• mexBはどこまで大きくできるか
• mexAより大きい要素がAにあっても意味がないので、あとは全部Bに回す
• mexBは一回も現れない数

Problem B

n個の数から5つ選んで積を最大化せよ

考えたこと

• 大きい正の数は有利
• 絶対値が大きい負の数はそれ同士の積だと強い
• 負の数は使うとしたら符号をプラスにしたいのでペアで
• とりあえず大小関係を整理するためにソートが必要 以下昇順ソートされているものとする
• いったん正の数も負の数も十分にあるものとして
• 筆頭候補、大きいほうから5つ
• 次いで、大きいほう3つ小さいほう2つ（小さいほうは絶対値の大きい負の数）
• または、最大と小さい4つ
• の、どれか
• を、全部試せばいい
• 正の数や負の数が大きく偏っている場合は
• どれかはうまくいく、いかない（負や0になる）としたらそれはそれが最大のとき

Problem C

木がある。辺をひとつ消してひとつ生やしてcentroidの頂点をひとつにせよ centroidはその頂点を削除したときの最大の連結成分を最小化できる頂点

考えたこと

• きつそうなのでcentroidの判定を考えるのは後回し
• もとからcentroidが1つなら、適当な辺を消してつなぎ直すだけ
• centroidはたかだか2個？（未証明）
• centroidが1つでない場合、centroid以外からcentroidに出ている辺を消してもう一方のcentroidにつなぐ？（未証明だけどこれでACしている）
• centroidの判定はどうするか
• 最大連結成分を検証する
• 再帰関数を頑張るといけそう
• というかこの問題はこれに尽きる
• 全ての辺の組み合わせx-yiについて、x->yi方面の頂点数（子孫含む）を調べる
• そうするとyi->x方面の頂点数もわかる n-yiの子の数-yi自身
• あとは辺をつなぎ変える
• なんで通るんや…