概要

与えられたリボンの長さ \(L_i\) を指定の長さ \(T_i\) で切り分けるとき、基本の切り出しに加えて「切れ端の長さが \(T_i\) の半分以上ならパーツを1つ追加する」というルールに従い、得られるパーツの総数を求める問題です。

考察

• リボンの長さ \(L_i\) とパーツの長さ \(T_i\) は最大 \(10^{18}\) と非常に大きな値になります。そのため、\(L_i\) から \(T_i\) を引き続けるようなループ処理（素朴なシミュレーション）を行うと、計算回数が膨大になり TLE（実行時間制限超過）になってしまいます。
• そこで、四則演算を使って一発で答えを求めるアプローチをとります。
• 切り出せる基本のパーツ数は、割り算の商 \(\lfloor L_i / T_i \rfloor\) で求まります。
• 切り出した後に残る切れ端の長さは、割り算の余り \(L_i \bmod T_i\) で求まります。
• あとは問題文のルール通り、この余りが \(0\) より大きく、かつ \(\lfloor T_i / 2 \rfloor\) 以上であるかを判定し、条件を満たせばパーツ数を \(+1\) すればよいです。

具体例： - \(L_i = 10, T_i = 3\) の場合 - 商は \(10 \div 3 = 3\)、余りは \(10 \bmod 3 = 1\) - \(\lfloor T_i / 2 \rfloor = \lfloor 3 / 2 \rfloor = 1\) - 余り \(1\) は \(1\) 以上なので条件を満たし、パーツ数は \(3 + 1 = 4\) 個になります。 - \(L_i = 10, T_i = 4\) の場合 - 商は \(10 \div 4 = 2\)、余りは \(10 \bmod 4 = 2\) - \(\lfloor T_i / 2 \rfloor = \lfloor 4 / 2 \rfloor = 2\) - 余り \(2\) は \(2\) 以上なので条件を満たし、パーツ数は \(2 + 1 = 3\) 個になります。

アルゴリズム

各リボンについて、以下の手順で計算します。 1. \(L_i\) を \(T_i\) で割った商を計算し、これを基本のパーツ数とします。 2. \(L_i\) を \(T_i\) で割った余り \(R_i\) を計算し、これを切れ端の長さとします。 3. \(R_i > 0\) かつ \(R_i \geq \lfloor T_i / 2 \rfloor\) を満たすか if 文で判定します。 4. 条件を満たせば、基本のパーツ数に \(1\) を足します。 5. 計算したパーツ数を出力用のリストに追加します。

この処理を \(N\) 本のリボンすべてに対して繰り返し、最後に結果をまとめて出力します。

計算量

• 時間計算量: \(O(N)\)
  • 1つのリボンに対する割り算や余りの計算は \(O(1)\) で完了します。これを \(N\) 回繰り返すため、全体の時間計算量は \(O(N)\) となります。
• 空間計算量: \(O(N)\)
  • 入力データを一括で読み込むためのリストや、出力結果を保持するためのリストを使用するため、\(O(N)\) のメモリを使用します。

実装のポイント

• Pythonでは、整数の商（切り捨て除算）は // 演算子、余りは % 演算子を使って簡単に計算できます。

• 入力されるリボンの本数 \(N\) が最大 \(2 \times 10^5\) と多いため、標準の input() を何万回も呼ぶと入出力の処理で時間がかかってしまうことがあります。そのため、sys.stdin.read().split() を使って入力を一括で読み込み、出力も配列に溜めてから \n.join() で一気に出力する工夫をしています。これにより、実行時間を大幅に短縮できます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    out = []
    
    it = iter(input_data[1:])
    for L_str, T_str in zip(it, it):
        L = int(L_str)
        T = int(T_str)
        
        ans = L // T
        R = L % T
        
        if R > 0 and R >= T // 2:
            ans += 1
            
        out.append(str(ans))
        
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    main()

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