問題 https://atcoder.jp/contests/abc167/tasks/abc167_c 解法 解法としては各本を買う/買わないで全探索するとO(M2^N)で解けます。 C_n A_n_mは型としては[(Int, [Int])]になります。各要素の(Int, [Int])は単位元を(0, 要素が0の無限リスト)、演算をfstは足す、sndはzipして各要素を足すとするとモノイドになりそうですし問題を解くのに使えそうです。このようになる(Int, [Int])のnewtypeは(Sum Int, Ap ZipList (Sum Int))になります。ApはApplicative fとMonoid aからMonoid (f a)を作るnewtypeです。ZipListはpureをrepeat x、liftA2をzipして関数適用というApplicative実装を持つListのnewtypeなのでApと組み合わせると欲しいMonoidが得られます。 ところでnewtypeの変換にはcoerceという関数が便利です。安全に変換できる