概要

\(N\) 種類のお菓子を種類ごとに箱詰めし、すべての箱の合計個数の最小値を求める問題です。各箱には同じ種類のお菓子しか入れられず、最大 \(K\) 個まで入れることができます。

考察

この問題を解くための重要なポイントは、「種類が異なるお菓子は同じ箱に入れられない」という制約です。

この制約があるため、各種類のお菓子について「その種類を運ぶために最低何箱必要か」を個別に計算し、それらをすべて合計すれば答えが求まります。他の種類のお菓子と余ったスペースを共有することができないため、種類ごとに独立して考えてよいことになります。

具体的に、ある種類のお菓子の合計個数を \(S = A_i + B_i\) とすると、必要な箱の数は以下のようになります： - \(S = 0\) のとき： \(0\) 箱 - \(S > 0\) のとき： \(S\) を \(K\) で割って切り上げた値（ \(\lceil S / K \rceil\) ）

例えば、\(K = 10\) のときに合計 \(23\) 個のお菓子がある場合、10個、10個、3個と分けることで最小の \(3\) 箱で運ぶことができます。これは \(23 \div 10 = 2.3\) を切り上げた結果と一致します。

アルゴリズム

1. 答えを格納する変数 total_boxes を \(0\) で初期化します。
2. 各種類 \(i = 1, 2, \dots, N\) について以下を繰り返します：
   • 高橋君の分 \(A_i\) と青木君の分 \(B_i\) を足して、合計 \(S = A_i + B_i\) を求めます。
   • \(S > 0\) であれば、必要な箱の数 \(\lceil S / K \rceil\) を計算して total_boxes に加算します。
3. 最終的な total_boxes を出力します。

切り上げ処理の工夫

プログラミング言語の整数型における割り算（/ や //）は、通常「切り捨て」が行われます。切り上げ計算 \(\lceil S / K \rceil\) を整数演算のみで行うには、以下の式を使うのが一般的です： $\((S + K - 1) // K\)$ これにより、浮動小数点数の精度問題を回避しつつ正確な切り上げ値を求めることができます。

計算量

• 時間計算量: \(O(N)\) お菓子の種類数 \(N\) に対して、各種類を 1 回ずつ処理するため、入力の大きさに比例した時間で計算が終わります。
• 空間計算量: \(O(1)\) または \(O(N)\) 入力を順次処理する場合は \(O(1)\) です。すべての入力を一度にリスト等に読み込む場合は \(O(N)\) となります。

実装のポイント

• 大きな数値への対応: お菓子の総数や箱の数は非常に大きくなる可能性があります。Python は標準で多倍長整数をサポートしていますが、他の言語（C++など）を使用する場合は、合計値が 32-bit 整数の範囲を超えるため、long long 型などの 64-bit 整数を使用する必要があります。

• 入力の高速化: \(N\) が最大 \(2 \times 10^5\) と比較的大きいため、Python では sys.stdin.read().split() や sys.stdin.readline を使用して入力を高速に読み込むのが望ましいです。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを取得し、スペース・改行で分割する
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了
    if not input_data:
        return
    
    # イテレータを使用してデータを順番に取得する
    it = map(int, input_data)
    
    # N: お菓子の種類数, K: 1箱に入れられる最大個数
    try:
        N = next(it)
        K = next(it)
    except StopIteration:
        return
    
    total_boxes = 0
    
    # 各種類のお菓子について、必要な箱の数を計算する
    for _ in range(N):
        try:
            A = next(it)
            B = next(it)
            
            # 合計個数
            S = A + B
            
            # 合計が0個の場合は箱は不要
            if S > 0:
                # 必要な箱の数は ceil(S / K)
                # 整数演算のみで求める場合は (S + K - 1) // K
                total_boxes += (S + K - 1) // K
        except StopIteration:
            break
            
    # 結果を出力
    print(total_boxes)

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-thinking によって生成されました。