読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

AGC011 A, B, C, D

agc011.contest.atcoder.jp

A問題

 早い時間に到着する乗客をバスに乗せずに待たせて置くほうがいいパターンは存在しません。したがって到着時間をあらかじめソートしておくと、条件を満たすぎりぎりの乗客まで乗せて出発するを繰り返すことで答えを求められます。


B問題

 色の順序等は答えに影響しないことからあらかじめ、大きさ順にソートしておいても問題ありません。a[i]番目の生物がa[i+1]番目の生物を吸収できる条件は、a[i]以下の大きさの和の2倍がa[i+1]以上であることです。したがって、累積和をとって、k番目以降が全て条件を満たしているならばn-k+1色が存在可能です。


C問題

 二つの連結グラフA, Bが存在するときこれらのグラフから作られるグラフの連結成分の個数を考えます。

  • A, Bどちらかが孤立点のとき

 頂点数の積

  • A, Bどちらかが二部グラフでない

 二部グラフでない場合奇数長のサイクルが存在するため各頂点間に偶数と奇数のパスが両方存在する。したがって全ての頂点が連結になるため連結成分の数は1

  • A, Bともに二部グラフ

 奇数長のパスの組と偶数長のパスの組でそれぞれ連結成分がつくられるため連結成分の個数は2

与えられたグラフの孤立点の個数をa個、二部グラフの個数をb個、二部グラフでないグラフの個数をc個とすると、
{ 
2b^2 + 2bc + c^2 + a^2 + 2a(n-a)
}
個の連結成分となります。二部グラフの判定はdfsでO(|V|+|E|)で可能なので2秒以内に答えが求まる。


D問題

 rngさんの解説放送を見てください。
www.youtube.com