from ARC114 ARC114A💻
- 考えたこと
- 20個くらいの素数からいくつか選んで全体を被覆する
- その方法のうち、コスト最小のもの
- 覆われる対象は50個、「何が覆われてるか」をbitで持つと2^50でちょっと多すぎる
- 最小カット？
- コストが各選択肢の積→対数を取れば和になる
- コスト最小化は最小カット
- と思って実装して見たが…
- 10がある時に「素因数2か素因数5のどちらかがSでなければならない」の表現方法がわからない
- たくさんの数の約数である素数から順に取っていく貪欲法でAC
- これは嘘解法
- 3,5,7,6,10,14とかで2を選んじゃうけど選ばないのが正解
- 素数が15個なので2^15=32768件の全探索をしても余裕
-