問題: D - Powerful Discount Tickets 問題概要 解法 証明 ($\star$) の証明 類題 問題概要 $N$ 個の商品の値段 $A_1, A_2, \dots, A_N$ と割引券の枚数 $ M $ が与えられる。$a$ 円の商品に $b$ 枚割引券を使うと $\lfloor a / 2^b \rfloor$ 円で買える。$N…

グラフの話です。 簡単のために、グラフは連結で、多重辺や自己ループがないものとします。 用語の説明 2 色で塗り分けられるとは、次の条件を満たすようにグラフの頂点を 2 色で塗る方法が存在することをいいます。 条件：u と v が辺でつながっている ⇒ u …