APC001 D: Forest
解き方
- 前提
n
個の木を連結にするためには、n-1
個の辺を追加する必要がある- 条件から辺に含まれる頂点は重複しないので、
2n-2
個の頂点が辺に含まれる - 連結にするためには、各木から少なくとも1つは頂点を選ばないといけない
- 実装
- 森をn個の木に分割(O(N))し、それぞれでコスト最小の頂点を選ぶ
- 残った頂点(N-n)個のうちから、コストが小さい順に
n-2
個選ぶ - 上の2つのコストの和が答え(ただし、最初から木になっているケースがコーナーケース)
APC001: C Vacant Seat
解き方
- 最初の一回はとりあえず0を聞いて、次に反対側の2点(A, B)を聞く
- 反対側2点の結果から、[0:A]と[B:N-1]のどちらに空席があるかわかるので、そこからは二分探索
ハマったところ
- 実装中、CLionがおかしい挙動をした。terminalからcmakeし直すとなるらしい
ARC090 D: People on a Line
解き方
- 情報をそれぞれ辺としてグラフを作り、DFSしながら条件に当てはまる数字の割当があるかを調べる
ハマったところ
- グラフが連結でないことを想定せず何回かWAした