Description:
n種類の病気と、m種類の薬がある。(1<=n<=300, 1<=m<=200)
各々の薬は、特定の複数の病気の内、一つでも罹っていれば、陽性と判断することが出来る。
また、薬は混ぜる事が可能である。
病気1,2を検出する薬、病気2,3,4を検出する薬、病気5を検出する薬を混ぜると、病気1,2,3,4,5を検出する薬を作ることが出来る。
今ある薬で可能なテストを全部出来るままに保ちつつ、最大で何種類薬を取り除くことが出来るか?
Answer:
薬Aで検出できる病気を全て薬Bが検出できる時にAからBへの枝が存在するようなグラフを考える。
同じ特性の薬が無いと仮定すると、このグラフはDAG(Directed Acyclic Graph)になる。
このグラフを見ると、ある薬を取り除いたとしても、他の薬が取り除けるかどうかの判断に全く影響を与えない事がすぐわかる。
よって、一つずつ薬を見ていって、残っている手持ちの薬から作る事が出来る薬をgreedyに取り除けば問題無い。
計算量は、O(n*m^2)。
Source: