きろく

特筆すべき記録のまとめ

yukicoder:No.914 Omiyage

問題

https://yukicoder.me/problems/no/914

解法

国 [1, N / 2) での買い物の仕方と,国 [N / 2, N] での買い物の仕方をそれぞれ全列挙し,前者のそれぞれの金額について,後者との和が最も K に近くなるような後者の買い物の仕方を二分探索で求める(半分全列挙).この和を K から引いた値の min が答えとなる.O(M^(N / 2)log(M^(N / 2))).

解答

https://yukicoder.me/submissions/392999

f:id:babcs2035:20191026121806p:plain