【競プロ】切り捨てと切り上げ

🕒 2019/10/07 🔄 2023/05/01

ここでは、切り捨てと切り上げについて見ていきます。また、ある桁が何であるかを調べたり、C++で割り算の結果を切り上げるためのコードも見ていきます。なお、ここでは、正の数だけを扱うことにします。競プロ記事の一覧はこちら。

📘 目次

切り捨て

ある数に対して、ある桁より下の部分をすべて $0$ にすることを、切り捨てる(round down) といいます。「千円未満切り捨て」というと、千円より小さい金額は $0$ にしてしまう、ということです。なので、1000円も1001円も1999円も、千円未満を切り捨てれば1000円になります。

プログラミングでは、「小数点以下の切り捨て」がよく登場します。小数点以下を切り捨てるとは、小数点以降は無視するということです。 $3.14$ に対して、小数点以下を切り捨てると $3$ になります。

割り算のところで見た通り、C++では、正の整数を正の整数で割った場合、答えは必ず切り捨てになります。数学での答えが 1.2 だろうが、1.5 だろうが、1.999 だろうが、C++では 1 になります。

数学では、小数点以下を切り捨てたものは、 $[\ ]$ を使って表します。 $[3.14]=3$ ということです。正の整数 $a,b$ について、 $a$ を $b$ で割り、その商を切り捨てたものは $\left[\dfrac{a}{b}\right]$ で表すことができます。

$[\ ]$ は、ガウス記号といいます。ガウス記号の代わりに、よく似ていますが $\lfloor x \rfloor$ という記号を使うこともあります。これは床関数(floor function) といいます。

特定の位の値を求める

C++では、整数を整数で割ったときの商が切り捨てられることから、1の位を切り捨てた値を次のようにして求めることができます。

#include <iostream>
using namespace std;

int main(){
  int a = 12345;
  cout << a / 10 * 10;
  return 0;
}

10で割ると、数学的には $1234.5$ になりますが、C++では切り捨てられるので、結果は $1234$ となります。それから10を掛けると $12340$ となり、1の位が切り捨てられた状態になります。

これをさらに応用すれば、ある位の数が何か、求めることができます。例えば、100の位（右から3つ目の数字）が何かを求めてみましょう。

#include <iostream>
using namespace std;

int main(){
  int a = 12345;
  cout << a / 100 % 10;
  return 0;
}

100で割ると、数学的には $123.45$ ですが、C++では切り捨てられて $123$ となります。これを $10$ で割ったときの余りを求めれば、 $3$ となります。こうして100の位を求めることができます。処理としては、不要な右側を消し、次に不要な左側を消して、求めたかった位を見る、という流れです。

こうしたことを踏まえれば、AtCoder ABC 023 A - 加算王などができるようになります。

切り上げ

ある数に対して、ある桁（Xとしましょう）以降を切り上げる(round up) とは、Xの桁より下の部分がすべて $0$ ならそのまま、 $0$ 以外の部分があるときに、Xの桁を1増やし、Xの桁より下の部分をすべて $0$ にすることをいいます。

「千円未満切り上げ」というと、0円より大きく千円より小さい金額は $1000$ にしてしまう、ということです。なので、1001円も1500円も1999円も、千円未満を切り上げれば2000円です。1000円は、千円未満の部分が0なので、切り上げても変わりません。1000円は1000円のままです。

数学では、正の数 $a$ の小数点以下を切り上げた数を $\lceil a \rceil$ で表します。これを天井関数(ceiling function) といいます。

C++では、正の整数を整数で割った場合、つねに切り捨てられてしまうので、切り上げたいときには少し工夫が必要です。例えば、正の整数 $a$ を $3$ で割って、答えを切り上げたいとしましょう。つまり、割り切れたときはそのまま、割り切れないときだけ $1$ を増やしたい、ということです。

そのまま割り算をしてしまうと、次のようになってしまいます。

#include <iostream>
using namespace std;

int main(){
  cout << 1 / 3; // 0
  cout << 2 / 3; // 0
  cout << 3 / 3; // 1
  cout << 4 / 3; // 1
  cout << 5 / 3; // 1
  cout << 6 / 3; // 2
  return 0;
}

$1,2$ のときに答えが1増えればいいのだから a / 3 + 1 とすればいいのではないか、と考えるかもしれませんが、これはうまくいきません。 $a\div 3$ が割り切れるときも1を増やしてしまうからです。

そのため、1つの方法としては、割り切れるときはそのまま、割り切れないときは $1$ を足す、という方法があります。ただ、少し長くなってしまいますね。そこで、次のようなテクニックをよく使います。

#include <iostream>
using namespace std;

int main(){
  for (int a = 1; a < 7; a++) {
    cout << a << ": " << (a + 3 - 1) / 3 << "\n";
  }
  return 0;
}

a に 3 - 1 を足してから3で割っています。こうすると、たしかに切りあがった答えが計算できるようになります。

なぜこれでうまくいくかは、商を切り捨てたとき（C++での通常の割り算）と切り上げたときとを並べてみるとわかりやすくなります。

$a$	1	2	3	4	5	6
$a/3$ 切り捨て	0	0	1	1	1	2
$a/3$ 切り上げ	1	1	1	2	2	2

切り上げたときの結果と切り捨てたときの結果は、横にずれていることがわかります。商がはじめて $1$ になるのは、切り捨ての場合は $3$ のときで、切り上げの場合は $1$ のときなので、切り上げたときの結果を知りたい場合は、 $3-1$ 個だけ右に移動したところにある切り捨ての結果を使えばいいんですね。これが3 - 1を足していた理由です。

一般に、正の整数 $a,b$ について、 $a\div b$ の結果を切り上げたい場合、C++では、(a + b - 1) / bで求められます。次のように、切り上げの結果と切り捨ての結果が b - 1 個だけずれていることからわかります。

$a$	1	…	$b-1$	$b$
$a/b$ 切り捨て	0	…	0	1
$a/b$ 切り上げ	1	…	1	1

C++には、ceilという切り上げた値を返してくれる関数がありますが、これがうまく機能するのは、扱っている値が小数の場合です。C++では、整数同士の割り算の答えは切り捨てられた状態で求められるので、 ceil(a / b)とやっても意味はありません。そこで、上で見たようなテクニックが必要となります。

実際の競プロの問題では、切り捨てるのか切り上げるのかは、自分で考えなければいけません。AtCoder ABC 005 A - おいしいたこ焼きの作り方、AtCoder ABC 009 A - 引越し作業、AtCoder ABC 089 A - Grouping 2などを解いてみましょう。割り切れないときに、どうすると答えになるのかを考えると、考えやすくなると思います。