やっぱり俺の敵はDPだ・・・
— つたじろう (@_TTJR_) 2016年8月10日
DPは難しい、はっきりわかんだね。
問題概要
0 から 100 の数字から異なる n 個の数を取り出して合計が s となる組み合わせの数を出力せよ。
解説
私はDPが書けないのでDPの練習をしました。
dp[ i ][ j ] = dp[取り出す個数][合計] = 組み合わせの数
という dp テーブルを作ります。ここで重要なのが、 i のループは逆順であるということです。こうしないと、 dp テーブルの更新時に i に関して自分の一つ前を見る関係で、「重複を許した」組み合わせの数を計算することになってしまい、「異なる」 n 個の数、という制約を満たすことができません。この辺が難しいですよね。rep の順序もこの通りに書かないとうまくいきません。
#include <bits/stdc++.h> #define rep(i,a,n) for(int i=a; i<n; i++) #define repr(i,a,n) for(int i=a; i>=n; i--) using namespace std; int main() { ll dp[11][1010]; dp[0][0] = 1; rep(k,0,101) repr(i,9,0) rep(j,0,1001-k) { dp[i+1][j+k] += dp[i][j]; } int n, s; while(cin >> n >> s){ if(n == 0 && s == 0) break; cout << dp[n][s] << endl; } return 0; }
数をこなせばできるようになるんだろうか・・・
2017/2/3 追記: なんか人類が理解しにくいコードを書いていたので、もっとわかりやすく書きました。逆順ループは使っていません。
この問題は 0 があるのが非常に厄介なのですが、この組み合わせは (1 〜 100 から n 個選ぶときの組み合わせ) + (1 〜 100 から (n-1) 個選ぶときの組み合わせ) と等価になりますので、それで書いてあげればシンプルになります。
int dp[110][20][1010]; signed main() { int n, s; memset(dp, 0, sizeof(dp)); dp[0][0][0] = 1; repq(i,1,100) repq(j,0,15) repq(k,0,1000) { dp[i][j][k] = dp[i-1][j][k]; if(k - i < 0) continue; if(j != 0) dp[i][j][k] += dp[i-1][j-1][k-i]; } while(cin >> n >> s, n || s) { cout << dp[100][n][s] + dp[100][n-1][s] << endl; } return 0; }
配列再利用するなら (逆順ループ入ってもいいなら) こうも書けます。メモリ効率は良いですね。でもこれ元のやつとあまり大差ない気がする。
int dp[20][1010]; signed main() { int n, s; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; repq(i,1,100) repr(j,15,0) repq(k,0,1000) { if(k - i < 0) continue; if(j != 0) dp[j][k] += dp[j-1][k-i]; } while(std::cin >> n >> s, n || s) std::cout << dp[n][s] + dp[n-1][s] << std::endl; return 0; }
