APC001 D: Forest

apc001.contest.atcoder.jp

解き方

  • 前提
    • n個の木を連結にするためには、n-1個の辺を追加する必要がある
    • 条件から辺に含まれる頂点は重複しないので、2n-2個の頂点が辺に含まれる
    • 連結にするためには、各木から少なくとも1つは頂点を選ばないといけない
  • 実装
    • 森をn個の木に分割(O(N))し、それぞれでコスト最小の頂点を選ぶ
    • 残った頂点(N-n)個のうちから、コストが小さい順にn-2個選ぶ
    • 上の2つのコストの和が答え(ただし、最初から木になっているケースがコーナーケース)

github.com

APC001: C Vacant Seat

apc001.contest.atcoder.jp

解き方

  • 最初の一回はとりあえず0を聞いて、次に反対側の2点(A, B)を聞く
  • 反対側2点の結果から、[0:A]と[B:N-1]のどちらに空席があるかわかるので、そこからは二分探索

ハマったところ

  • 実装中、CLionがおかしい挙動をした。terminalからcmakeし直すとなるらしい

github.com

ARC090 D: People on a Line

D - People on a Line

解き方

  • 情報をそれぞれ辺としてグラフを作り、DFSしながら条件に当てはまる数字の割当があるかを調べる

ハマったところ

  • グラフが連結でないことを想定せず何回かWAした

github.com