けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

余りの切り上げ処理 〜 (a + b - 1) / b とは何か 〜

テーマ解説記事 切り上げ処理 演算子「/」「%」を用いる問題 演算子「+」「-」「*」を用いる問題 算数と数学

プログラミングをしていると、時々「割り算したときに余りがあったら商を 1 増やしたい」ということがあります。今回は、その処理をワンライナーで書く方法を考えましょう！

1：問題設定

早速ですが、次の問題を考えてみましょう！

問題

a 個のりんごに詰めていく。1 つの箱には b 個のリンゴが入る。

すべてのりんごを箱詰めするためには、何箱必要か？

具体的な数値で試す

具体的な数値でやってみましょう。次のような感じになります。

  • a = 12、 b = 4 のとき：
    • 12 \div 4 = 3 より、3 箱
  • a = 13、 b = 4 のとき：
    • 13 \div 4 = 3 あまり 1 より、3 箱に満杯まで詰めたあとに 1 個のりんごが余るので、3 + 1 = 4 箱必要
  • a = 14、 b = 4 のとき：
    • 14 \div 4 = 3 あまり 2 より、3 箱に満杯まで詰めたあとに 2 個のりんごが余るので、3 + 1 = 4 箱必要

こんな感じですね。以上の観察から、 a を b で割り切れるかどうかで処理を分岐すればよさそうだと分かるでしょう。

一般の場合

一般には、次のように解法を整理できます。

a を b で割った商を q とする。

  • a が b で割り切れるとき： q 箱必要である
  • a が b で割り切れないとき： q + 1 箱必要である

この処理は、if 文を用いて次のように実装できます。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    
    if (a % b == 0) cout << a / b << endl;
    else cout << a / b + 1 << endl;
}

if 文をなくしたい！！

......と、これで問題解決！！......と言ってもよいのですが、実は if 文を用いずに 1 本の式で解くことができるのです！！

何事においても、if 文を減らして書くことができるならば、if 文をなるべく減らして書くことが望ましいといえます。なぜならば、if 文を 1 つ書くたびに、テストすべきケースが 2 倍に膨れ上がっていくからです。

　

2：ワンライナーで書く

それでは、一般に次の値（ a を b で割って切り上げた値と呼ぶことにします）をワンライナーで書く方法を考えましょう！

a を b で割った商を q としたときの、

  • a が b で割り切れるとき： q
  • a が b で割り切れないとき： q + 1

一回、自分の手で「こんな式で表現できるのでは！？」とあれこれやってみることをオススメします！！　それをやった上で答えを見ると、「なるほど......うまくできている」と納得できるでしょう。

　

a が b で割り切れなければ......

さて、 a と b の値を本当にランダムに指定したとき、 a が b で割り切れることよりも、割り切れないことの方が多いのは直感的にわかるでしょうか。

たとえば、 b = 5 のとき、 a = 0, 1, 2, \dots に対して、次の図のようになります。なお、 b で割り切れる a については赤く示しています。

赤色の箇所の方が少なくなっています。さらに言えば、 b が大きくなればなるほど、 a が b で割り切れる割合が減っていくことも見て取れるでしょう。

そして、この a を b で割り切れるという例外的なケースを除くと、求めたい「 a を b で割って切り上げた値」は、次の式で正解を導くのです。

a / b + 1

ただし、この式は a が b で割り切れる場合には成り立ちません。その場合にも成り立つ式を考えましょう。

　

a が b で割り切れる場合にも対応したい

それでは、 a が b で割り切れる場合にも対応する方法を考えてみましょう。

ここで、また b = 4 の場合について、

  • A： a を b で割って切り上げた値
  • B： a を b で割ったときの商

をそれぞれ考えてみましょう。次の図のようになります。A も B も、「同じ値を b 回繰り返すと値が 1 上がる」という特徴を持っていることが分かります（値が 1 上がっている瞬間を着色してみました）。

この図を眺めると、値が 1 上がっている瞬間の a の値について、「 a を b で割って切り上げた値」と「 a を b で割ったときの商」とで、ちょうど b - 1 だけズレがあることが分かるでしょうか。

たとえば、 a = 2 のときの「 a を b で割って切り上げた値」は、 a = 5 (= a + b - 1) のときの「 a を b で割った商」と一致するのです。

一般に、「 a を b で割って切り上げた値」は、「 a + b - 1 を b で割った商」に等しいのです！！

よって、「 a を b で割って切り上げた値」は次のように表せます。

(a + b - 1) / b

見事、ワンライナーで表せました！

　

3：問題例

ここまで覚えた技術を用いて、具体的な問題を解いてみましょう。

　

問題 1：AtCoder ABC 153 A - Serval vs Monster

サーバルはモンスターと戦っている。モンスターの体力は H である。

サーバルが攻撃を 1 回行うとモンスターの体力を A 減らすことができる。モンスターの体力を 0 以下にすればサーバルの勝ち。

サーバルがモンスターに勝つために必要な攻撃の回数を求めよ。

解法

この問題の答えは、まさに「 H を A で割って切り上げた値」です。よって、(H + A - 1) / A と表せます。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int H, A;
    cin >> H >> A;
    cout << (H + A - 1) / A << endl;
}

　

問題 2：AtCoder ABC 200 A - Century

西暦 N 年は何世紀であるか？

解法

たとえば、西暦 1700 年は 17 世紀です。西暦 1701 年は 18 世紀です。このように、さまざまな西暦が何世紀なのかを考えると

  • 西暦 N が 100 の倍数であるとき： N を 100 で割った商
  • 西暦 N が 100 の倍数でないとき： N を 100 で割った商に 1 を足したもの

であることがわかります。これはまさに、「 N を 100 で割って切り上げた値」に他なりません。よって、答は (N + 100 - 1) / N です。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    cout << (N + 99) / 100 << endl;
}

　

問題 3：JOI 一次予選 2022 (第 3 回) B - アイスクリーム

JOI アイスクリーム店は、非常に高さのあるアイスクリームタワーが名物のアイスクリーム店である。アイスクリームタワーとは、ベースとなるアイスクリームの上に、追加のアイスクリームを 0 個以上積み重ねたものである。

ベースとなるアイスクリームの金額は 250 円で、高さは A cm である。追加のアイスクリームは 1 個につき 100 円で、1 個追加するごとにアイスクリームタワーの高さが B cm 増える。

この店で高さが S cm 以上のアイスクリームタワーを買うために必要な金額の最小値を求めよ。

解法

追加で買う必要のあるアイスクリームの個数 need を求めましょう。

アイスクリームの高さを全部で S - A cm だけ増やす必要があり、1 個あたり B cm だけ増えるることに注意します。よって、need は「 S-A を B で割って切り上げた値」となります。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int S, A, B, need;
    cin >> S >> A >> B;

    if (A >= S) need = 0;
    else need = (S - A + B - 1) / B;
    cout << 250 + 100 * need << endl;
}