zuka天井関数を実装するよ。
本記事では，天井関数の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください。
目次
本記事の概要
天井関数はstd::ceilが利用できますが，勉強のために今回は自前で実装したいと思います。とは言っても，実装は一行で終わります。
今回おさえるべき内容
天井関数の定式化を確認する
天井関数を実装する
定式化
正の整数$a$，$b$に対して，天井関数は以下のように計算できます。
\begin{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lfloor\frac{a+b-1}{b}\right\rfloor \label{ceil}
\end{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lfloor\frac{a+b-1}{b}\right\rfloor \label{ceil}
\end{align}
式(\ref{ceil})の証明をしていきます。まず，$a$が$b$で割り切れるとき，つまり$a$が$b$の倍数であるときを考えます。そのとき，$a$は以下のように表せます。
\begin{align}
a &= qb
\end{align}
a &= qb
\end{align}
ただし，$q$は正の整数です。すると，式(\ref{ceil})の左辺は以下のように計算できます。
\begin{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lceil\frac{qb}{b}\right\rceil \\
&= q
\end{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lceil\frac{qb}{b}\right\rceil \\
&= q
\end{align}
一方で，式(\ref{ceil})の右辺は以下のように計算できます。
\begin{align}
\left\lfloor\frac{a+b-1}{b}\right\rfloor &= \left\lfloor\frac{bq+b-1}{b}\right\rfloor \\
&= q + 1 - 1\\
&= q
\end{align}
\left\lfloor\frac{a+b-1}{b}\right\rfloor &= \left\lfloor\frac{bq+b-1}{b}\right\rfloor \\
&= q + 1 - 1\\
&= q
\end{align}
次に，$a$が$b$で割り切れないときを考えます。このとき，$a$は以下のように表せます。
\begin{align}
a &= qb + r
\end{align}
a &= qb + r
\end{align}
ただし，$r$は$b$より小さい正の整数です。すると，すると，式(\ref{ceil})の左辺は以下のように計算できます。
\begin{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lceil\frac{qb+r}{b}\right\rceil \\
&= q + 1
\end{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lceil\frac{qb+r}{b}\right\rceil \\
&= q + 1
\end{align}
一方で，式(\ref{ceil})の右辺は以下のように計算できます。
\begin{align}
\left\lfloor\frac{a+b-1}{b}\right\rfloor &= \left\lfloor\frac{bq + r + b - 1}{b}\right\rfloor \\
&= q + 1 +1 - 1\\
&= q + 1
\end{align}
\left\lfloor\frac{a+b-1}{b}\right\rfloor &= \left\lfloor\frac{bq + r + b - 1}{b}\right\rfloor \\
&= q + 1 +1 - 1\\
&= q + 1
\end{align}
以上で，式(\ref{ceil})が正しいことを示せました。
ポイント
たた覚えにくい式ですが，基本的には分子に$b$を足した上で，帳尻合わせとして$1$を引くと覚えましょう。
実装
int my_ceil(int a, int b){
return (a + b - 1) / b;
}
コメント