問題 枚の板について長さと設置できる上下限位置が与えられる。また個のボールが各座標に落とされる。板に一つもボールが落ちないような板の配置方法が何通りあるか求めよ。 解法 ボールが落ちる位置について累積和を取って、各板が設置可能な範囲を二分探索…

問題 日間営業するレストランで夕食を食べることを考える。レストランは常に種類のパターンを用意しているが、ある曜日にあるパターンの夕食を食べると、同じ曜日には同じパターンの夕食した食べられない。日目の番目のパターンに対するコストを与えるので、…

問題 数の集合に対する以下のクエリを処理せよ。 タイプ1 : に数を追加する。 タイプ2 : に含まれる数のうち番目に小さい数を答え、その数をから削除する。 解法 「番目に小さい数⇔それ以下の数が個以上追加されている数のうち最も小さい数」と考え、ある数…