解説

各資料について、\(A_i\) ページを \(1\) 枚 \(B_i\) ページの用紙に印刷するときの枚数を求めます。これはちょうど切り上げ除算 \(\lceil A_i / B_i \rceil\) です。最後の \(1\) 枚は \(B_i\) ページ未満でもよいので、割り切れない場合に \(1\) 枚追加すればよいことになります。

このプログラムでは整数除算のテクニック \((A_i + B_i - 1) / B_i\) を使っています。正しい理由: \(A_i = q B_i + r\) (\(0 \leq r < B_i\)) と書くと、\((A_i + B_i - 1) / B_i = q + (r + B_i - 1) / B_i\) となり、\(r = 0\) のとき追加分は \(0\)、\(r \geq 1\) のとき \(B_i \leq r + B_i - 1 < 2 B_i\) より追加分は \(1\) になります。これは \(\lceil A_i / B_i \rceil\) と一致します。

ループは \(N\) 回回り、各回で入力・除算・出力を \(O(1)\) で行います。

計算量

• 時間: \(O(N)\)
• 空間: 入力を配列に保存せず逐次処理するため \(O(1)\)