概要

各資料について、ページ数を用紙 \(1\) 枚あたりのページ数で割り、端数を切り上げた値を求めます。

考察

ある資料のページ数を \(A\)、用紙 \(1\) 枚に印刷できるページ数を \(B\) とします。

例えば、\(A=10\)、\(B=3\) の場合、用紙 \(3\) 枚では \(9\) ページしか印刷できません。残りの \(1\) ページにも用紙が必要なので、答えは \(4\) 枚です。

整数除算 A // B は小数部分を切り捨てるため、そのままでは割り切れない場合に用紙が \(1\) 枚不足し、誤答になります。したがって、必要な枚数は次のようになります。

• \(A\) が \(B\) で割り切れる場合：\(A // B\) 枚
• 割り切れない場合：\(A // B + 1\) 枚

この切り上げは、条件分岐を使わずに次の式で計算できます。

\(\displaystyle \left\lceil \frac{A}{B} \right\rceil = \left\lfloor \frac{A+B-1}{B} \right\rfloor\)

Python では、(A + B - 1) // B と書けます。

この式が成り立つ理由を確認します。\(A=qB+r\)（\(0 \leq r < B\)）とすると、次のようになります。

• \(r=0\) なら、\(A+B-1=qB+(B-1)\) なので、\(B\) で整数除算した結果は \(q\) です。
• \(r>0\) なら、\(A+B-1=(q+1)B+(r-1)\) なので、\(B\) で整数除算した結果は \(q+1\) です。

用紙を \(1\) 枚ずつ追加して必要枚数を数える方法でも、この制約では間に合います。ただし、上の式を使えば各資料の答えを一度の計算で求められます。

アルゴリズム

1. 資料の件数 \(N\) を読み込みます。
2. 各資料について、次の処理を行います。
   • ページ数 \(A_i\) と、用紙 \(1\) 枚あたりのページ数 \(B_i\) を読み込みます。
   • (A_i + B_i - 1) // B_i を計算します。
   • 結果を文字列にして、出力用のリストに追加します。
3. リストの要素を改行でつなぎ、入力順に出力します。

計算量

• 時間計算量: \(O(N)\)
  各資料について定数時間の計算を行います。
• 空間計算量: \(O(N)\)
  提示コードでは、入力全体と出力用のリストを保存します。

実装のポイント

• Python の // は整数除算です。/ では浮動小数点数になるため、今回は // を使います。

• (a + b - 1) // b のように、足し算の部分を括弧で囲みます。

• \(A_i < B_i\) の場合も用紙は \(1\) 枚必要です。この式なら正しく \(1\) が得られます。

• 提示コードでは入力全体を split() で分割しています。\(i\) を \(0\) 始まりとすると、data[1 + 2 * i] がページ数、data[2 + 2 * i] が用紙 \(1\) 枚あたりのページ数に対応します。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    out = []
    for i in range(n):
        a = int(data[1 + 2 * i])
        b = int(data[2 + 2 * i])
        out.append(str((a + b - 1) // b))
    sys.stdout.write("\n".join(out) + "\n")

main()

---

この解説は gpt-6-astra-medium によって生成されました。