概要

各リボンを指定長さで切り分けたときのパーツ数を求める問題です。切れ端が指定長さの半分以上であれば追加で1パーツとして数えます。

考察

この問題は、各リボンについて独立に計算できるシンプルな問題です。

具体例で理解する：

• リボンの長さ \(L = 25\)、パーツの指定長さ \(T = 7\) のとき：

  • \(\lfloor 25 / 7 \rfloor = 3\) 個のパーツが切り出せる（\(7 + 7 + 7 = 21\) ミリメートル使用）
  • 切れ端 \(R = 25 \bmod 7 = 4\) ミリメートル
  • \(\lfloor T / 2 \rfloor = \lfloor 7 / 2 \rfloor = 3\)
  • \(R = 4 \geq 3\) なので、切れ端もパーツとして使える → 4個

• リボンの長さ \(L = 20\)、パーツの指定長さ \(T = 7\) のとき：

  • \(\lfloor 20 / 7 \rfloor = 2\) 個、切れ端 \(R = 6\)
  • \(\lfloor 7 / 2 \rfloor = 3\)、\(R = 6 \geq 3\) → 3個

• リボンの長さ \(L = 14\)、パーツの指定長さ \(T = 7\) のとき：

  • \(\lfloor 14 / 7 \rfloor = 2\) 個、切れ端 \(R = 0\)
  • 切れ端が残らない（\(R = 0\)）ので追加なし → 2個

• リボンの長さ \(L = 2\)、パーツの指定長さ \(T = 7\) のとき：

  • \(\lfloor 2 / 7 \rfloor = 0\) 個、切れ端 \(R = 2\)
  • \(\lfloor 7 / 2 \rfloor = 3\)、\(R = 2 < 3\) → 0個

素朴なアプローチで問題ないか？

\(N\) 本のリボンそれぞれに対して割り算と剰余を1回ずつ計算するだけなので、\(O(N)\) で十分高速です。\(L_i, T_i\) が最大 \(10^{18}\) と大きいですが、Python は多倍長整数を標準でサポートするため、オーバーフローの心配もありません。

アルゴリズム

各リボン \(i\) について以下を行います：

1. 商 \(q = \lfloor L_i / T_i \rfloor\) と余り \(R_i = L_i \bmod T_i\) を計算する。
2. \(R_i > 0\) かつ \(R_i \geq \lfloor T_i / 2 \rfloor\) ならば、パーツ数は \(q + 1\)。
3. それ以外（切れ端なし、または切れ端が短すぎる）ならば、パーツ数は \(q\)。

条件の \(R_i > 0\) のチェックが重要です。\(R_i = 0\) のとき（ちょうど割り切れるとき）は \(\lfloor T_i / 2 \rfloor = 0\) となるケース（\(T_i = 1\) のとき）でも追加パーツは数えません。

計算量

• 時間計算量: \(O(N)\) — 各リボンについて定数時間の計算を行う
• 空間計算量: \(O(N)\) — 出力用のリストに結果を格納する

実装のポイント

• 出力の高速化: print を \(N\) 回呼ぶと遅くなるため、結果をリストに溜めておき、最後に '\n'.join(...) でまとめて出力しています。

• 入力の高速化: sys.stdin.readline を使うことで、大量の入力を高速に読み取ります。

• 整数オーバーフロー: C++ などでは \(L_i, T_i\) が最大 \(10^{18}\) のため long long でも掛け算時にオーバーフローする可能性がありますが、Python では整数の桁数制限がないためそのまま計算できます。

• 条件の順序: r > 0 and r >= T // 2 の r > 0 を先に書くことで、\(T = 1\) で \(\lfloor T/2 \rfloor = 0\) のとき切れ端がないのに追加してしまうバグを防いでいます。

  ソースコード

import sys
input = sys.stdin.readline

N = int(input())
out = []
for _ in range(N):
    L, T = map(int, input().split())
    q = L // T
    r = L % T
    if r > 0 and r >= T // 2:
        out.append(q + 1)
    else:
        out.append(q)
print('\n'.join(map(str, out)))

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