概要

\(N\) 種類のお菓子をそれぞれ箱に詰めるとき、各種類ごとに必要な箱の数を求めて合計する問題です。

考察

重要な気づき

1. 異なる種類のお菓子は同じ箱に入れられないため、種類ごとに独立に考えればよいです。ある種類の箱の数が、他の種類の詰め方に影響を与えることはありません。

2. 同じ種類であれば高橋君と青木君のお菓子に区別はないため、\(i\) 番目の種類のお菓子は単に \(A_i + B_i\) 個として扱えます。

3. 各種類について、合計 \(A_i + B_i\) 個のお菓子を \(1\) 箱あたり最大 \(K\) 個ずつ詰めるので、必要な箱の数は 切り上げ除算（天井関数）で求まります。

具体例

例えば、\(K = 3\) で、ある種類のお菓子が合計 \(7\) 個ある場合： - 1箱目: 3個 - 2箱目: 3個 - 3箱目: 1個

よって \(\lceil 7 / 3 \rceil = 3\) 箱必要です。

合計が \(0\) 個の場合は箱は不要なので、スキップします。

素朴なアプローチとの比較

この問題は各種類ごとに独立に計算して足し合わせるだけなので、特に複雑なアルゴリズムは不要です。ただし、\(A_i + B_i\) が最大 \(2 \times 10^9\) になるため、64ビット整数の範囲に注意する必要があります（Python では整数のオーバーフローは起きないので心配不要です）。

アルゴリズム

1. \(N\) と \(K\) を読み込む。
2. 答えを格納する変数 ans を \(0\) で初期化する。
3. 各種類 \(i\) について：
   • \(\text{total} = A_i + B_i\) を計算する。
   • \(\text{total} > 0\) なら、\(\lceil \text{total} / K \rceil\) を ans に加算する。
4. ans を出力する。

切り上げ除算 \(\lceil a / b \rceil\) は、Python では math.ceil(a / b) や (a + b - 1) // b で計算できます。

計算量

• 時間計算量: \(O(N)\) — 各種類について定数時間の計算を行うだけ
• 空間計算量: \(O(1)\) — 入力を逐次読み込むため、追加のメモリはほぼ不要

実装のポイント

• math.ceil の利用: Python の math.ceil(total / K) は、total や K が大きい場合に浮動小数点の精度の問題が生じる可能性があります。より安全な方法は整数演算のみを使う (total + K - 1) // K です。ただし、今回の制約（\(A_i + B_i \leq 2 \times 10^9\)）では math.ceil でも正しく動作します。

• sys.stdin.readline の利用: \(N\) が最大 \(2 \times 10^5\) と大きいため、標準の input() より高速な sys.stdin.readline を使って入力を読み込んでいます。

• 合計が \(0\) の場合のスキップ: \(A_i = B_i = 0\) のとき箱は不要なので、条件分岐で total > 0 を確認しています（math.ceil(0 / K) = 0 なのでスキップしなくても結果は同じですが、明示的にしています）。

  ソースコード

import math
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    total = a + b
    if total > 0:
        ans += math.ceil(total / K)
print(ans)

---

この解説は claude4.6opus-thinking によって生成されました。