床関数・天井関数と関係式

POINT

  • 床関数・天井関数の定義
  • 競技プログラミングでよく使われる関係式の導出

分数のところの関係式が競技プログラミング(AtCoder,蟻本など)のコードでよく使われています.検索しても欲しい記事が出てこないので,自分で考えました.

床関数

床関数$\lfloor x \rfloor$は,$x$以下の最大の整数,つまり
\begin{aligned}
\mathbb{R}\ni x
\mapsto \lfloor x \rfloor := \max \{n\in\mathbb{Z}\mid n \leq x\}
\end{aligned}
で定義されます.これは,実数の小数点以下を切り捨てることに相当します.

まさに,実数$x$を整数ごとに敷かれた床まで落とすイメージです.

天井関数

天井関数$\lceil x \rceil$は,$x$以上の最小の整数,つまり
\begin{aligned}
\mathbb{R}\ni x
\mapsto \lceil x \rceil := \min \{n\in\mathbb{Z}\mid n \geq x\}
\end{aligned}
で定義されます.これは,実数の小数点以下を切り上げることに相当します.

こちらは,実数$x$を整数ごとにある天井にぶつけるイメージです.

関係式

我流の議論になっています.参考になるものがあれば教えて下さい.
(特に,分数の場合の関係式については,もっと見通しの良い方法がありそうだと感じています)

「x未満」の最大の整数

$x$未満の最大の整数を表す方法を考えます.

場合分けをして考えると,

  1. $x$が整数のとき:$x-1=\lceil x -1 \rceil$
  2. $x$が整数でないとき:$\lfloor x \rfloor=\lceil x -1 \rceil $
です.

よって,次で与えられます.

$x$未満の最大の整数
\begin{aligned}
\lceil x -1 \rceil
\end{aligned}

「xを超える」の最小の整数

同様に,$x$を超えるの最小の整数について考えます.

場合分けすると

  1. $x$が整数のとき:$x+1 = \lfloor x+1 \rfloor$
  2. $x$が整数でないとき:$\lceil x \rceil = \lfloor x+1 \rfloor$
です.

よって,次で与えられます.

$x$を超えるの最小の整数
\begin{aligned}
\lfloor x+1 \rfloor
\end{aligned}


分数(x=a/b)の場合の表現

$x$が分数で表される場合は,プログラミングでよく使われる他の表現があります.

以下では,分数$x=a/b$を考えて,$a\div b$の商を$a/\!/b$,剰余を$a \% b$と表します(*1).つまり,

\begin{aligned}
a = b\cdot a/\!/b + a \% b
\end{aligned}
です.

剰余$a\% b$に着目するのがポイントです.これまでは$x$が整数かどうかに着目してきましたが,ここでは,$a\% b=0$が$a/b$が整数であることと同値であるためです.

床関数

\begin{aligned}
\lfloor a/b \rfloor
&=a/\!/b
\end{aligned}
【説明】
床関数の定義と,
\begin{aligned}
a/b = a/\!/b + (a \% b)/b
\end{aligned}
において,$a/\!/b$が整数で,$(a \% b)/b < 1$が小数であることによりわかります.//

天井関数

\begin{aligned}
\lceil a/b \rceil
&=
\begin{cases}
\, a/\!/b & (a \% b = 0) \\
\, a/\!/b + 1 & (a \% b \neq 0)
\end{cases} \\
&= \bigl(a + (b-1) \bigr)/\!/b
\end{aligned}
【説明】
1つ目の等号は,天井関数の定義からわかります.
2つ目の等式は,剰余で場合分けすれば
  1. $a \% b = 0$の場合:$a \% b + (b-1)=b-1 < b$なので,$[a + (b-1)] /\!/ b = a/\!/b$,
  2. $a \% b = 1,2,...,b-1$の場合:$b \leq a \% b + (b-1) < 2b$なので,$[a + (b-1)] /\!/ b = a/\!/b + 1$,
となることからわかります.//



2つ目の等式では,剰余に何か($\alpha$とする)を加え,
  1. 剰余ゼロの場合の商は変えず(つまり$a \% b + \alpha < b$)に,
  2. 剰余がゼロでない場合の商を$+1$する(つまり$b \leq a \% b + \alpha < 2b$)
$\alpha$はあるか,という問題を考え,$\alpha = b-1$とすればよい,という答えを得たわけです.

$\alpha$を整数に限らなければ,$\alpha = b-0.8$など,多数の表現が可能です.



【応用】
正整数$b$の倍数で,正整数$a$以上のもののうち最小のものを求めてみます.つまり,$b$を何倍すれば始めて$a$以上となるか,ということです.答えを$xb$とすれば,
\begin{aligned}
x &= \min\{n\in\mathbb{Z}\mid nb\geq a \} \\
&= \min\{n\in\mathbb{Z}\mid n\geq a/b \} \\
&=\lceil a/b \rceil
\end{aligned}
より,答えは以下で与えられます.
$\min\{ xb \mid xb \geq a,\; a,b,x\text{:正整数} \}$
\begin{aligned}
\lceil a/b \rceil \cdot b
= \bigl(a + (b-1) \bigr)/\!/b \cdot b
\end{aligned}

あるいは,

\begin{aligned}
a/b \leq \lceil a/b \rceil
\end{aligned}
から
\begin{aligned}
a= a/b\cdot b \leq \lceil a/b \rceil \cdot b
\end{aligned}
であり,$a/b$と$\lceil a/b \rceil $の間には整数が存在しないことからも,簡単にわかります(こちらの方がわかりやすく,早いかも).

「x=a/b未満」の最大の整数

\begin{aligned}
\lceil a/b -1\rceil
&=
\begin{cases}
\, a/\!/b - 1 & (a \% b = 0) \\
\, a/\!/b= \lfloor a/b \rfloor & (a \% b \neq 0)
\end{cases} \\
&= (a-1)/\!/b
=\lfloor (a-1)/b \rfloor
\end{aligned}
【説明】
これまで示していないのは2行目の等式だけです.剰余で場合分けすれば
  1. $a \% b = 0$の場合:$-b\leq a \% b -1 = -1 < 0$なので,$(a-1)/\!/b = a/\!/b - 1 $,
  2. $a \% b = 1,2,...,b-1$の場合:$0\leq a \% b -1 < b$なので,$(a-1)/\!/b = a/\!/b$,
となることからわかります.//



2つ目の等式では,剰余に何か($\alpha$とする)を加え,
  1. 剰余ゼロの場合の商を$-1$し(つまり$-b\leq a \% b + \alpha < 0$),
  2. 剰余がゼロでない場合の商を変えない(つまり$0 \leq a \% b + \alpha < b$)
$\alpha$はあるか,という問題を考え,$\alpha = -1$とすればよい,という答えを得たわけです.

$\alpha$を整数に限らなければ,$\alpha = -0.3$など,多数の表現が可能です.

「x=a/bを超える」の最小の整数

\begin{aligned}
\lfloor a/b+1 \rfloor
&=(a+b) /\!/ b
\end{aligned}
【説明】
床関数で示した関係式から示されます.//

参考記事

床関数と天井関数 - Wikipedia

*1:代数では通常$a=bq + r\,(0\leq r< |b|)$と表します.本記事ではプログラミングに使うことを念頭に置くので,それに沿った記号を使うことにします.また,$a\% b=0$のことを代数では$b \mid a$と表記し,$a\% b\neq 0$のことを代数では$b \nmid a$と表記します.