概要

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

考察

ページ数を \(A\)、用紙 \(1\) 枚あたりのページ数を \(B\) とします。

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

単に整数除算 A // B を使うと、余りが切り捨てられるため、割り切れない場合に用紙が \(1\) 枚不足します。一方、常に \(1\) を足すと、割り切れる場合に \(1\) 枚多くなってしまいます。

したがって、必要な枚数は次のようになります。

• \(A\) が \(B\) で割り切れる場合：\(A \div B\) 枚
• 割り切れない場合：整数除算の結果に \(1\) を足した枚数

これは、\(A/B\) の切り上げである \(\lceil A/B \rceil\) と表せます。

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

アルゴリズム

1. 資料の件数 \(N\) を読み込みます。
2. 次の処理を \(N\) 回繰り返します。
   • ページ数 \(A\) と用紙 \(1\) 枚あたりのページ数 \(B\) を読み込みます。
   • -(-A // B) で \(\lceil A/B \rceil\) を計算し、出力します。

Python の // は、計算結果を負の無限大方向に切り下げる演算です。そのため、次の関係を利用できます。

\(\lceil A/B \rceil = -\lfloor -A/B \rfloor\)

例えば、\(A=10\)、\(B=3\) なら、-10 // 3 は -4 です。その符号を反転すると、必要な枚数 4 が得られます。

計算量

• 時間計算量: \(O(N)\)
  各資料について、定数時間の計算を行います。
• 空間計算量: \(O(1)\)
  資料を \(1\) 件ずつ処理するため、全資料の情報を保存する必要はありません。

実装のポイント

• Python では、負の数に対する // は小数部分を単に取り除く演算ではありません。例えば、-10 // 3 は -3 ではなく -4 です。

• 今回のように \(A\) と \(B\) が正の整数なら、(A + B - 1) // B でも同じ切り上げ除算ができます。

• 浮動小数点数を使わず、整数の演算だけで正確に計算できます。

  ソースコード

# 問題文から独立に実装
n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    print(-(-a // b))

---

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