解法

各カード種類 \(i\) について独立に考えます。\(i\) 種類目のカードはちょうど \(A_i\) 枚必要で、現在 \(B_i\) 枚持っています。

追加で \(x\) 枚買うと所持枚数は \(B_i + x\) 枚になるため、必要枚数を満たす条件は

\[ B_i + x \geq A_i \]

です。買う枚数 \(x\) は \(0\) 以上の整数なので、必要な最小枚数は

\[ \max(0, A_i - B_i) \]

となります。したがって、各 \(i\) についてこの値を \(1\) 行ずつ出力すればよいです。

結果は各カード種類について一意に定まるため、特別な tie-breaking はありません。

正しさの証明

任意の \(i\) を固定します。

• \(B_i \geq A_i\) のとき、すでに必要枚数以上を持っているため、追加で買う必要がある枚数は \(0\) 枚です。このとき \(A_i - B_i \leq 0\) なので、\(\max(0, A_i - B_i)=0\) となり、出力は正しいです。
• \(B_i < A_i\) のとき、必要枚数に達するには少なくとも \(A_i-B_i\) 枚追加する必要があります。また、実際に \(A_i-B_i\) 枚買えば所持枚数は \(B_i+(A_i-B_i)=A_i\) 枚になります。したがって最小の購入枚数は \(A_i-B_i\) であり、\(\max(0,A_i-B_i)=A_i-B_i\) となります。

よって、すべての \(i\) について出力される値は、必要枚数を揃えるために追加で買うべき最小枚数と一致します。

計算量

\(N\) 種類それぞれについて定数時間の計算を行うため、時間計算量は \(O(N)\) です。入力を \(1\) 種類ずつ読んで処理するため、補助空間計算量は \(O(1)\) です。