SRM645 DIV1
0pt
Rate: 1243->1263
1年半ぶりの参加らしい。が、0完でつらい。
250. JanuszTheBusinessman
解けなかった。
出会える人のグラフを作って、そのグラフの中で頂点集合を選んで、その頂点と隣接頂点がグラフすべての頂点をカバーしているような最小の頂点集合を求める問題、と考えてしまったけど、これは最小支配集合問題のようで、NP困難。
考え方
一番出発が速い人を考えると、その人が出発するまでにプロモ対象者と接触しないといけない。言い換えれば、「その人か、その人の滞在中に会う人の中」からプロモ対象者を選んでいなければいけない。
この対象者を選ぶには、「一番滞在時間が遅い人を選んだ方がカバーしている日数が多い」ので、そんな人を選んだほうがよい。
選ばれた対象者が滞在中に会う人は、プロモされることになる。
同様に、プロモされていない、かつ、次に出発が速い人について、処理を繰り返す。
