概要

各リボンから指定された長さのパーツを切り出すとき、余った切れ端が条件を満たせば追加で1個のパーツとみなせる。このルールに基づいて、各リボンから得られるパーツの個数を求めよ。

考察

この問題では、各リボンに対して以下のような処理を行う必要があります： - まず、リボンの長さ \(L_i\) を指定されたパーツの長さ \(T_i\) で割った商 \(\lfloor L_i / T_i \rfloor\) を求め、これは確実にパーツとして使える部分です。 - 次に、余り \(R_i = L_i \bmod T_i\) を求めます。 - この余りが0より大きく、かつ \(R_i \geq \lfloor T_i / 2 \rfloor\) であれば、切れ端も1つのパーツとしてカウントします。

例えば、\(L_i = 7\), \(T_i = 3\) の場合： - 商：\(\lfloor 7 / 3 \rfloor = 2\) → 2個のパーツ - 余り：\(7 \bmod 3 = 1\) - \(\lfloor T_i / 2 \rfloor = \lfloor 3 / 2 \rfloor = 1\) - \(R_i = 1 \geq 1\) なので、切れ端も1個のパーツになる → 合計3個

一方、\(L_i = 5\), \(T_i = 4\) の場合： - 商：\(\lfloor 5 / 4 \rfloor = 1\) → 1個のパーツ - 余り：\(5 \bmod 4 = 1\) - \(\lfloor T_i / 2 \rfloor = \lfloor 4 / 2 \rfloor = 2\) - \(R_i = 1 < 2\) なので、切れ端は使えない → 合計1個

素朴なアプローチの問題点

もし標準入力で1行ずつ読み込むと、\(N\) が最大 \(2 \times 10^5\) あるため、入力の時点で時間がかかりすぎてTLEになる可能性があります。また、\(L_i, T_i\) が最大 \(10^{18}\) なので、除算や剰余演算を効率よく処理できる必要があります。

解決方法

Pythonの sys.stdin.read を使い、すべての入力を一度に読み込んで高速化します。さらに、divmod 関数を使うことで商と余りを一度に求めることができ、効率的かつシンプルに処理できます。

アルゴリズム

1. すべての入力を一度に読み込み、リストに格納する。
2. 各リボンについて以下の処理を行う：
   • divmod(L, T) を使って商 \(q\) と余り \(r\) を求める。
   • \(T\) の半分の値を half_T = T // 2 で求める。
   • 条件 \(r > 0\) かつ \(r \geq \text{half\_T}\) を満たすなら \(q + 1\) を答えとする。
   • それ以外なら \(q\) が答え。
3. 結果を文字列としてリストに保存し、最後に改行で結合して出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 大量の入力を高速に処理するために sys.stdin.read を使用。

• 商と余りを同時に求めるために divmod を利用。

• 文字列で結果を保持してから一括で出力することで、出力処理のオーバーヘッドを抑える。

• 条件判定では「\(r > 0\) かつ \(r \geq \lfloor T/2 \rfloor\)」を正確に実装すること。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    idx = 1
    results = []
    for _ in range(N):
        L = int(data[idx])
        T = int(data[idx+1])
        idx += 2
        q, r = divmod(L, T)
        half_T = T // 2
        if r > 0 and r >= half_T:
            results.append(str(q + 1))
        else:
            results.append(str(q))
    print('\n'.join(results))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。