Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 302 A問題 Attack

AtCoder ABC ABC302 A問題 100 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

体力が A のモンスターが居る.

このモンスターの体力を 0 以下にするためには, 1 回の攻撃で体力を B 減らせる攻撃を最低何回する必要があるか?

制約

  • 1 \leq A \leq 10^{18}
  • 1 \leq B \leq 10^{18}

解法

求めるべき答えは \left \lceil \dfrac{A}{B} \right \rceil である. しかし, これを求める場合, 次の違いにしなければならないことがたくさんある.

  • 整数の型 (int 型, long 型)
  • 整数を整数で割った商には実数の商と整数の商があること.
  • 切り捨てと切り上げ

\left \lceil \dfrac{A}{B} \right \rceil を切り捨てを用いて求める方法としては次のような方法がある.

(1)

\left \lceil \dfrac{A}{B} \right \rceil=\left \lfloor \dfrac{A+B-1}{B} \right \rfloor

(2)

\left \lceil \dfrac{A}{B} \right \rceil=\begin{cases} \left \lfloor \dfrac{A}{B} \right \rfloor & (B \mid A) \\ \left \lfloor \dfrac{A}{B} \right \rfloor+1 & (B \not \mid A) \end{cases}

ここで, B \mid A, B \not \mid A はそれぞれ B は A の倍数である (倍数ではない) という意味である.