Sum of Different Primes 解説

問題名：Sum of Different Primes (PKU)
出典：Problem D, ACM/ICPC Asia Regional Contest, Yokohama, 2006-11-05
難易度：☆☆☆
問題の種類：DP
解法：メモ化探索
解答ソースコード：
- 3132-deq.cpp

アルゴリズムの概略

n=1120以下の素数の数をp，組み合わせる素数の数をkとすると全探索が _pC_k となりますが， p = 187, k = 14 なので ₁₈₇C₁₄ > 10²⁰ というおそろしい組み合わせ数になりそうです（実際にはすぐに n を超えてしまうので探索が打ち切られてしまいますが，それでも組み合わせ数は指数関数的に爆発します）。

こういうときはまずDPを適用できるかを考えます。で，この問題は実際にDPが適用できます。例えば n=6, k=2 であれば，「n=4, k=1（素数2を使った場合）」，「n=3, k=1（素数3を使った場合）」，「n=1, k=1（素数5を使った場合）」の3通りの結果を合計すれば求められるはずです。なので一度求めた結果をメモ化しておけばOKです。ただし，同じ素数を重複して使うことは許されないので，小さい順から埋めていく，つまり再帰関数に「どの素数まで使ったのか」という情報も渡さなければなりません。上記の例だと，「n=4, k=1, last=2」，「n=3, k=1, last=3」，「n=1, k=1, last=5」という感じです。

この問題は典型的なDP問題に分類されます。

アルゴリズムの計算量

n=1120, k=14, p=187 なので多くとも n×k×p = 2,932,160 回計算すれば1つの問題セットに解答できます（p=187というのは実際にn=1120までの素数を全て列挙するプログラムを書いて初めて分かることですが）。再帰関数で関数呼び出し（スタック）を使いまくるとしても，3Mは現実的に計算可能な値に思えます。また，3M×4バイト = 12MB 程度であればメモリも足りそうです。

アルゴリズムの実装

再帰関数でメモ化探索する場合，メモ化（キャッシュ）の部分は全く作らずに再帰関数を書きます。そしてそのプログラムで答えを出力してみて，答えは合っているけれどもプログラムが終了しないのを見て，その後にメモ化すればいいでしょう。典型的に，メモ化に必要な作業は4行の追加だけで済むのですから（宣言，初期化，代入，参照）。

また，n = 1120までの素数を列挙する（小さい順から配列に持つ）方法には，例えば「小さい順から調べていって，今までに見つかった全ての素数で割り切れなければ素数である」という判定方法があります。これはプログラムを擬似コーディングすれば

p = [2]  // 最初は 2 だけ
for (i = 3; i <= 1120; i += 2):
  add = true
  for j in [0, p.size):
    if p[j]*p[j] > i:
      break  // sqrt(i) を超えれば抜ける
    if i % p[j] == 0:
      add = false
      break
  if add:
    p.push(i)

という感じになります。素数表（ルックアップテーブル）を作りたいような場合は「エラトステネスの篩」というアルゴリズムが存在するので，詳しくは「Dirichlet's Theorem on Arithmetic Progressions」の解説あたりを参考にしてください（とはいっても，ここで述べた方法も幾分遅いですが本質的には「エラトステネスの篩」と同じ考え方です）。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $

deq notes