読者です 読者をやめる 読者になる 読者になる

hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

AOJ 0097: Sum of Integers II

DPは難しい、はっきりわかんだね。

問題概要

原文 → 整数の和 | Aizu Online Judge

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;
}