Kickstart2020 RoundA : Allocation

Kickstart2020 RoundAのAllocationの問題です。

問題

売り出し中のN軒の家の価格（i番目の価格は$A_i$）と、使用可能なバジェットBが与えられた時に、最大で何軒購入できるかを求める問題です。
https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f56

$1 \leq B \leq 10^5$、$1 \leq A_i \leq 1000$で、またTest set1では$1 \leq N \leq 100$、Test set2では$1 \leq N \leq 10^5$という条件です。

アルゴリズム

直感的に、最も安いものから買っていくと購入数を最大に出来るのではと思われます。実際、この考え方を実装して実行すると、解を求めることが可能です。
価格リストを昇順にソートして、先頭から順にBを価格分減らしていき、Bが負になった時点で終了となり（Bが０の時はギリギリ予算内）、それまでに購入できた数が求めたい値になります。ソートはsortedなどを使った場合は計算量がO(NlogN)となりますが、$1 \leq A_i \leq 1000$と決まっているので、Counting sortを使うとO(N）となります（count arrayの初期化、各値のカウント、カウントの累積値計算、ソート済み配列への代入はN回のループ）。

実装

def counting_sort(A):
    max_A = 1000
    counts = [0 for _ in range(max_A + 1)]
    for a in A:
        counts[a] += 1
    for i in range(1, len(counts)):
        counts[i] += counts[i - 1]
    sorted_A = [0 for _ in range(len(A))]
    for i in range(len(A) - 1, -1, -1):
        sorted_A[counts[A[i]] - 1] = A[i]
        counts[A[i]] -= 1
    return sorted_A


T = int(input())
for x in range(1, T + 1):
    N, B = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A = counting_sort(A)
    res = 0
    for a in A:
        B -= a
        if B < 0:
            break
        res += 1
    print('Case #{}: {}'.format(x, res))

アルゴリズムが求める解が最適であることの証明

Analysisのところには証明が書かれているのだが、詳しく理解できなかった...