AGC011 A, B, C, D
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個とすると、
個の連結成分となります。二部グラフの判定はdfsでO(|V|+|E|)で可能なので2秒以内に答えが求まる。
