Pythonで桁和ごとにボールを仕分けし、最も多くのボールが入る箱の数を求める方法

問題概要

あるボール工場では、lからrまで（両端を含む）の番号が付いたn個のボールを生産しており、1番から無限大まで番号の付いた箱が無限に用意されています。各ボールは、そのボール番号の各桁の合計（桁和）と同じ番号の箱に入れるというルールがあります。

例えば、ボール番号123であれば、1 + 2 + 3 = 6 となるため、6番の箱に入ります。このとき、2つの値lとrが与えられた場合、最も多くのボールが入っている箱のボール数を求めるのがこの問題の目的です。

具体例で確認する

入力が l = 15、r = 25 の場合を考えてみましょう。各ボールは次のように振り分けられます。

• ボール15 → 1+5 = 6 → 6番の箱へ
• ボール16 → 1+6 = 7 → 7番の箱へ
• ボール17 → 1+7 = 8 → 8番の箱へ
• ボール18 → 1+8 = 9 → 9番の箱へ
• ボール19 → 1+9 = 10 → 10番の箱へ
• ボール20 → 2+0 = 2 → 2番の箱へ
• ボール21 → 2+1 = 3 → 3番の箱へ
• ボール22 → 2+2 = 4 → 4番の箱へ
• ボール23 → 2+3 = 5 → 5番の箱へ
• ボール24 → 2+4 = 6 → 6番の箱へ
• ボール25 → 2+5 = 7 → 7番の箱へ

この結果を見ると、6番の箱にはボール15と24の2個、7番の箱にもボール16と25の2個が入っており、他の箱より多くなっています。したがって、答えは 2 となります。

解法のアプローチ

この問題は、ハッシュマップ（辞書）を使って各箱のボール数を集計することで効率的に解けます。手順は以下の通りです。

1. カウント用の空の辞書（dict）を作成します。
2. i を l から r まで順にループ処理します。
3. 変数 total を 0 で初期化します。
4. i の各桁 j を取り出し、total に加算して桁和を計算します。
5. total がまだ辞書に存在しない場合は、dict[total] = 0 として初期化します。
6. dict[total] に 1 を加算してカウントします。
7. 全ての処理が完了したら、辞書内の値の最大値を返します。

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

def solve(l, r):
    counts = {}
    for i in range(l, r + 1):
        # 各桁の合計（桁和）を計算
        total = sum(int(j) for j in str(i))
        counts[total] = counts.get(total, 0) + 1
    return max(counts.values())

l = 15
r = 25
print(solve(l, r))

なお、桁和の計算は sum(map(int, str(i))) のように書くこともでき、より簡潔に表現できます。

入力

15, 25

出力

2

計算量について

このアルゴリズムの時間計算量は O((r − l + 1) × d) です。ここで d は数値の桁数を表します。範囲内の各数値に対して一度だけ桁和を計算すればよいため、非常にシンプルかつ効率的な解法となっています。空間計算量も、箱の種類数（最大でも桁和のバリエーション数）に比例するだけなので、O(1) とみなせるほど小さく抑えられます。