A – コンテスト 解説 (Typical DP Contest)

2020年3月10日AtCoder数え上げ, DP, 競プロ, ナップサック, 合計得点が何通りか

問題へのリンク

問題概要

N 問の問題があるコンテストがあり、i 問目の問題の配点は pi 点である。合計得点は何通り考えられるか?

制約

  • 1 ≤ N ≤ 100
  • 1 ≤ pi ≤ 100

考え方

単純に考えると、正解する問題の選び方で \(2^N\) の全探索をして、合計得点が何種類生じるか探索する方法があります。しかし、これでは \(O(2^N)\) の計算時間になって間に合いません。

pi や N が小さいことに注目すると、この問題はナップサック問題と同様のDPを用いることで、高速に計算することができます。

i+1 番目の問題を使用して合計得点が sum になるかを考えてみましょう。これは、

  • i 番目までの問題によって合計得点が \(sum-p_i\) になり、i+1 番目が解ける
  • i 番目までの問題によって合計得点が \(sum\) になり、i+1 番目が解けない

のどちらかが成立すれば成り立ちます。この性質をもちいれば、以下のようなDPで計算することが可能です。

dp[ i ][ sum ] := i 問目までの問題を使って、合計得点が sum になるかの真偽値

初期化

  • dp[ i ][ 0 ] := true

更新

配るDP を用いると以下の通りになります。

  • dp[ i ][ sum ] が true なら、dp[ i+1 ][ sum+p[ i ] ] は true
  • dp[ i ][ sum ] が true なら、dp[ i+1 ][ sum ] は true

貰うDP を用いると以下の通りです。

  • dp[ i ][ sum-p[ i ] ] が true なら、dp[ i+1 ][ sum ] は true
  • dp[ i ][ sum ] が true なら、dp[ i+1 ][ sum ] は true

合計得点は最大でも 10000 までにしかなりません。よって、10000×N の計算時間なので十分に間に合います。

実装例