問題文 : ばらばら饅頭解法 : まず, 2個の饅頭で作る組み合わせが最適である(らしい) ので, 2個で作れる饅頭の個数を貪欲法で求める. (証明できなかった).その後は, ナップサック問題を解く要領でメモ化再帰を行う. このように, 配列に値を持たせて行うDPをm…

問題文 : カードキー解法 : 包除原理のようなものをつかう.この問題は, "0 ~ 2 ^ (N - K)までの数から, すくなくとも1つ数をつかって論理積を0にする組み合わせの総数はいくつか", という問題に置き換えられる.数の選び方は, U = 2 ^ (2 ^ (N - K)) - 1 通り…

問題文 : AOJ 0247解法 : 基本的には深さ優先探索を行う. ただし, それだけでは時間制限に間に合わないので, 反復深化深さ優先探索(IDDFS)を行う. 具体的には, 下界uを決めて, uよりコストがかかることがわかればuを増やすという事を行う. 下界から決めてい…