ARC114A💻

ARC114A💻

考えたこと

20個くらいの素数からいくつか選んで全体を被覆する

その方法のうち、コスト最小のもの

覆われる対象は50個、「何が覆われてるか」をbitで持つと2^50でちょっと多すぎる

最小カット？

コストが各選択肢の積→対数を取れば和になる

コスト最小化は最小カット

と思って実装して見たが…

10がある時に「素因数2か素因数5のどちらかがSでなければならない」の表現方法がわからない

たくさんの数の約数である素数から順に取っていく貪欲法でAC

これは嘘解法

3,5,7,6,10,14とかで2を選んじゃうけど選ばないのが正解

素数が15個なので2^15=32768件の全探索をしても余裕