いろはちゃんコンテスト Day1：E - 放課後
問題
解法
デートする日を最小化することを考える．以下，最小のデート回数を考える．
B = 0，すなわち，記念日が無いとき，最小のデート回数は N / A．
そうでないとき，0 日目と最初の記念日の間，B - 1 箇所ある隣り合う記念日同士の間，最後の記念日と N 日目の間の３つに分けて考える．まず，0 日目と最初の記念日の間には空白が D[0] - 1 日ある．よって，最小のデート回数は (D[0] - 1) / A となる．次に，隣り合う記念日同士の間には空白が D[i + 1] - D[i] - 1 日ある．よって，最小のデート回数は (D[i + 1] - D[i] - 1) / A となる．最後に，最後の記念日と N 日目の間には空白が N - D[B - 1] 日ある．よって，最小のデート回数は (N - D[B - 1]) / A となる．この 3 つを足し合わせたものが全体の最小のデート回数となる．
最終的な答えは N から最小のデート回数を引いたものになる．O(B)．
解答
