コンビネーションサム (Combination Sum)
ターゲット値
N とプラスの整数を含む配列が与えられたとき、これらの数を合計して N を作り出す方法が何通りあるかを求めます。たとえば、許可される値が
[1, 2, 3] で、N が 4 の場合、以下の 7 通りの方法で合計して 4 を作ることができます。1, 2, 3 を使って 4 を作る 7 通りの例
- 1 + 1 + 1 + 1
- 1 + 1 + 2
- 1 + 2 + 1
- 2 + 1 + 1
- 1 + 3
- 3 + 1
- 2 + 2
これは、典型的な動的計画法 (dynamic programming) を用いる問題で、
d[sum] という状態を管理します。d[sum] は、「許可された数を組み合わせて sum を作る方法が何通りあるか」を表します。N = ...
nums = [...]
d = [0] * (N + 1) # d[i] は、i を作り上げることのできる全パターン数
d[0] = 1 # 0 を作る方法は何も選ばない 1 通りだけ
for i in range(1, N + 1): # 1 から N まで順番に作り上げる
for num in nums: # num を使って d[i] を更新
if i - num >= 0: # num を使って i を作り上げる事が可能かどうか
d[i] += d[i - num]
print(d[N])このように、
d[i] は「許可された数 nums を使って i を作る方法の総数」として定義します。まずはすべて 0 に初期化しますが、d[0] だけは 1 とします。これは、「何も選ばない方法で 0 を作る」手段がちょうど 1 通りあることを表しています。これ以外の数 i については、nums に含まれる数を使ってどのように i を作れるかを順に検討していきます。たとえば、もしある時点で 11 (
d[11]) を作る方法が 5 通りあって、さらに 8 (d[8]) を作る方法が 3 通りあるとします。そして、もし nums に 3 が含まれていれば、すでに見つかっている 11 を作る方法に加えて、8 を作る 3 通りそれぞれに 3 を追加する新たな方法も含まれると考えられます。下記は、サンプルの入力でこのアルゴリズムを追った例です。
nums = [1, 2, 3] と N = 4 の場合
d = [1, 0, 0, 0, 0]→ 0 を作る方法が 1 通り、ほかは 0
i = 1num = 1 ⇒ d[1] += d[0] ⇒ d = [1, 1, 0, 0, 0] num = 2 ⇒ i - num < 0 num = 3 ⇒ i - num < 0
i = 2num = 1 ⇒ d[2] += d[1] ⇒ d = [1, 1, 1, 0, 0] num = 2 ⇒ d[2] += d[0] ⇒ d = [1, 1, 2, 0, 0] num = 3 ⇒ i - num < 0
i = 3num = 1 ⇒ d[3] += d[2] ⇒ d = [1, 1, 2, 2, 0] num = 2 ⇒ d[3] += d[1] ⇒ d = [1, 1, 2, 3, 0] num = 3 ⇒ d[3] += d[0] ⇒ d = [1, 1, 2, 4, 0]
i = 4num = 1 ⇒ d[4] += d[3] ⇒ d = [1, 1, 2, 4, 4] num = 2 ⇒ d[4] += d[2] ⇒ d = [1, 1, 2, 4, 6] num = 3 ⇒ d[4] += d[1] ⇒ d = [1, 1, 2, 4, 7]
print(d[4])→ 7 が出力される
チャレンジ - サイコロの組み合わせ (Dice Combinations)
サイコロを投げると、出目は 1 から 6 のいずれかになります。このサイコロの出目を合計して数
n を作る方法が何通りあるかを求めてください。
入力
入力として、1 つの整数
n (1 ≤ n ≤ ) が与えられます。出力
このサイコロを何回でも投げることで合計を
n にする方法の数を求め、その結果を で割った値を出力してください。例
入力 | 出力 |
2 | 2 |
3 | 4 |
解説
- 2 → 1 + 1, 2
- 3 → 1 + 1 + 1, 1 + 2, 2 + 1, 3
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB