SoundHound Inc. Programming Contest 2018 (春) C 広告
問題概要
縦 マス 横
マスのグリッドがあり、それぞれのマスには ' * ' か ' . ' が書かれている。
' . ' のマスに、それぞれがとなり合わないように広告を打つとき、打てる広告の最大数を求めよ。
制約
解法
' . ' のマスを頂点とし、となり合う ' . ' のマス同士を辺で結んでグラフを作ると二部グラフになる。
この問題はグラフの最大独立集合を求める問題に帰着するので、このグラフの最大マッチングを求めて、頂点数から引けばよい。
Submission #2161432 - SoundHound Inc. Programming Contest 2018 (春)
