AtCoder-Typical DP Contest A問題を解きました
AtCoderのTypical DP ContestのA問題を解いてみました
AtCoderというのは、毎週アルゴリズム系のプログラミングコンテストを開催している所謂競プロの主催者です。
このコンテストの問題は、コンテスト後も公開されているので練習がてら解くことができます。
その中でもTypical DP Contestというのは、動的計画法(Dynamic Programming)と呼ばれるアルゴリズムを用いて
解ける典型的な問題を集めたコンテストとなっています。といえども、初心者のうちは、DPで自分でパラメータを設定することが難しく、典型的とはいってもなかなか骨のある問題集となっています。
今回解いたのはTypical DP のA問題です。問題文は以下
A: コンテスト - Typical DP Contest | AtCoder
Problem Statement N 問の問題があるコンテストがあり、i 問目の問題の配点は pi 点である。コンテスタントは、 この問題の中から何問か解き、解いた問題の配点の合計が得点となる。 このコンテストの得点は何通り考えられるか。 Constraints 1≤N≤100 1≤pi≤100 Input Format 入力は以下の形式で標準入力から与えられる。 N p1p2…pN
書いたソースは続きより
#include<stdio.h> int N; int p[101]; int dp[10001]={0}; void DP() { dp[0] = 1; int j,i; for(j=1;j<=N;j++) for(i=10000;i>=0;i--) if(dp[i] == 1) dp[p[j]+i] = 1; } int main() { int i,j,result=0; scanf("%d",&N); for(i=1;i<=N;i++) scanf("%d",&p[i]); DP(); for(i=0;i<=10000;i++) result += dp[i]; printf("%d\n",result); }
メモ化再帰も用いず、ループで簡潔に書けました。
動的計画法は漸化式を考えるのが常套ですが、今回は
n問あって取得可能性のある点数(p)のベクトル(可能1/不可能0)のブール配列dp[p]があったとき、そこに+1問(点数(q))しようとすると、どのようにしてdpを変更すればよいかというところに着目するとよいと思います。dp[p]が1のときのみ、dp[p+q]=1としていけばよいことに気づけば、簡単です。ループを上から回していくのは、増えた点数パターンにさらに点数を加算することを防ぐためです。最後にdpを全部加算すると、得点しうる点数のパターンの合計が得られます。