【競プロ】条件式の式変形テクニック

# 目次
- [1. 導入](#1-導入)
- [2. 前提知識](#2-前提知識)
    - [小数点以下切り捨て（床関数）](#小数点以下切り捨て床関数)
    - [小数点以下切り上げ（天井関数）](#小数点以下切り上げ天井関数)
- [3. 結論](#3-結論)
- [4. 証明](#4-証明)
    - [(1)の証明](#1の証明)
    - [(2)の証明](#2の証明)
    - [(3)の証明](#3の証明)
    - [(4)の証明](#4の証明)
- [5. おわりに](#5-おわりに)

# 1. 導入
先日のABC406にて次のような問題が出題されました．

https://atcoder.jp/contests/abc406/tasks/abc406_b

この問題の本質はオーバーフローを起こさないよう，上手く条件式を作成することでした．

多倍長整数が実装されているPythonなどの高級言語を使っている人でない限り，実装には工夫が必要ですが，一番手っ取り早いのは，式変形により整数型数値同士の比較に持ち込む手法だと思います．

**コード例**
```c++:ABC406_B.cpp
#include<iostream>
using namespace std;
typedef long long ll;

int n,k;

int main(){
    ll now=1,a,max_sum=1;
    scanf("%d%d",&n,&k);
    while(k--)max_sum*=10;
    while(n--){
        scanf("%lld",&a);
        if((max_sum+now-1)/now<=a)now=1;//「max_sum<=a*now」から式変形
        else now=now*a;
    }
    printf("%lld\n",now);
    return 0;
}
```

競プロでは，条件式の式変形は主に以下の目的で行われます．
1. 浮動小数点型数値を絡めた計算の誤差対策
2. 整数型数値のオーバーフロー対策

1.に関しては単純に，商の形から積の形に式変形を行えばよいです．
しかし2.に関しては，逆に積の形から商の形に持ち込み，値を適切な整数に丸め，整数同士での比較に持ち込む場合が多いため，同値変形ができているかきちんと考察する必要があり，面倒だと思っている方が多いのではないでしょうか．
実は$a * b < c$や$a * b > c$のような**2数の積と1数との比較の条件式**に関しては，単純な**小数点以下切り捨て**と**小数点以下切り上げ**のみを用いて，簡単に積$\rightarrow$商の形に式変形した整数型数値の比較に持ち込むことが可能です．

本記事はこの式変形に関するテクニックについて，記事にしてみました．
# 2. 前提知識
本章ではテクニックを利用する上で必要になる前提知識について示します．

## 小数点以下切り捨て（床関数）
ある整数型変数$ a , b $が存在する時，$ \frac{a}{b} $の小数点以下を切り捨てた値を求める処理の実装を考えます．プログラミング言語によりその方法は様々ですが，C++では整数型変数同士の単純な割り算で実現でき，$ a/b $と記述するだけでよいです．
この処理は$ \frac{a}{b} $の床関数の値を求める処理と同じです．ある実数$ x $の床関数の値とは，**実数$ x $以下で最大の整数**のことを指し，以下の式で表すことができます．
```math
\lfloor x\rfloor
```
## 小数点以下切り上げ（天井関数）
ある整数型変数$ a , b $が存在する時，$ \frac{a}{b} $の小数点以下を切り上げた値を求める処理の実装を考えます．C++では，**整数型変数同士の商による小数点以下が切り捨てられる処理**を利用して，$ (a+b-1)/b $と記述することで実現できます．
この式の形について詳しく知りたい方は以下の記事を参照してください．

https://qiita.com/Naon_Yutakachan/items/963eda370221a28e80ba

この処理は$ \frac{a}{b} $の天井関数の値を求める処理と同じです．ある実数$ x $の天井関数の値とは，**実数$ x $以上で最小の整数**のことを指し，以下の式で表すことができます．
```math
\lceil x\rceil
```
# 3. 結論
2整数の積と1整数との比較の条件式は以下の4パターン存在し，それぞれ床関数と天井関数を用いて，次のように言い換えることができます．
```math
\begin{align}
    a*b<c \Leftrightarrow a<\lceil c/b\rceil \tag{1}\\
    a*b\leq c \Leftrightarrow a\leq \lfloor c/b\rfloor\tag{2}\\
    a*b> c \Leftrightarrow a> \lfloor c/b\rfloor\tag{3}\\
    a*b\geq c \Leftrightarrow a\geq \lceil c/b\rceil\tag{4}\\
\end{align}
```
```c++:CodeExample.cpp
int a,b,c;
// (1)
a*b < c  == a < (c+b-1) / b
// (2)
a*b <= c == a <= c / b
// (3)
a*b > c == a > c / b
// (4)
a*b >= c == a >= (c+b-1) / b
```
積の形になっている2整数のいずれか一方で両辺を割り，発生した商の形について床関数か天井関数のどちらの形にするか決定する形になります．
# 4. 証明
本章では，各式の証明を行います．ここで3変数$ a,b,c $は全て整数です．
各証明は$ c/b $の値について場合分けを行い，各場合で2式の評価が一致するか確認していく形となります．
## (1)の証明
```math
\begin{equation}
    a*b<c \Leftrightarrow a<\lceil c/b\rceil
\end{equation}
```
- $ c/b\leq a $ の時，$\lceil c/b \rceil \leq a$となり，$ a*b<c $ と $ a<\lceil c/b\rceil $ の判定値は共に偽となり同値
- $ c/b>a $ の時，$ \lceil c/b\rceil \geq a+1$となり，$ a*b<c $ と $ a<\lceil c/b\rceil $ の判定値は共に真となり同値

従って，この式変形は成立する．
## (2)の証明
```math
a*b\leq c \Leftrightarrow a\leq \lfloor c/b\rfloor
```
- $ c/b <a$ の時，$\lfloor c/b\rfloor < a$となり，$ a*b\leq c $ と $ a\leq \lfloor c/b\rfloor $ の判定値は共に偽となり同値
- $ c/b \geq a$ の時，$ \lfloor c/b\rfloor \geq a $となり，$ a*b\leq c$ と $ a\leq \lfloor c/b\rfloor $ の判定値は共に真となり同値

従って，この式変形は成立する．
## (3)の証明
```math
a*b> c \Leftrightarrow a> \lfloor c/b\rfloor
```
- $ c/b < a $の時，$ \lfloor c/b\rfloor< a$ となり，$ a*b\geq c $ と $ a\geq \lfloor c/b\rfloor $の判定値は共に真となり同値
- $ c/b \geq a $の時，$ \lfloor c/b\rfloor\leq a$となり，$ a*b\geq c $ と $ a\geq \lfloor c/b\rfloor $ の判定値は共に偽となり同値

従って，この式変形は成立する．
## (4)の証明
```math
a*b\geq c \Leftrightarrow a\geq \lceil c/b\rceil
```
- $ c/b \leq a $ の時，$ \lceil c/b\rceil\leq a $となり，$ a*b\geq c $ と $ a\geq \lceil c/b\rceil $ の判定値は共に真となり同値
- $ c/b>a $の時，$ \lceil c/b \rceil \geq a+1$となり，$ a*b\geq c $ と $ a\geq \lceil c/b\rceil $ の判定値は共に偽となり同値

従って，この式変形は成立する．
# 5. おわりに
Qiitaで初投稿の記事になります．
間違いなどがあれば指摘してくださると幸いです．