cormoran's note


cormoran

競技プログラミング・電子工作・ロボットなどで遊びます



Recent Post




AOJ-0537-Bingo

AOJ 0537 Bingo

典型的なDP

問題概要

N*Nマスのビンゴカードを作る。

各マスに入る数字は以下の条件を満たす必要がある。

  • 1以上M以下

  • どの行も数字は昇順に並ぶ。

  • どのマスの数も、それより左の列のどの数よりも大きい。

N*N個のマスの数字の総和がSとなるようなカードは何とおり作れるか

解法

配る形のDP、ICPCの問題で見たことがある気がする。

結局、上の条件は各列をつなげて1列にすると単調増加列になる、ということなので、

N*N個数字を選んだらそれぞれの場所は自動的に決まり、その数の組で作れるカードの種類は1通り。

$$ DP[i][j] := i個の数字を総和がjになるように選ぶ場合の数 $$ として、

1を加える、2を加える,…Mを加える、としていけばいい

たとえば、kを加える時は

$$ DP[i+1][j + k] += DP[i][j] $$

を、全てのi,jに対して行えばいい。

ただし、kを使えるのは各1回だけなので、すでにkを加えた部分に再度kが加えられないよう、DPテーブルを上から(iが大きい方から)更新していく必要がある。


#include<iostream>
#include<vector>
using namespace std;

typedef long long ll;
typedef ll int__;
#define rep(i,j) for(int__ i=0;i<(int__)(j);i++)
#define repeat(i,j,k) for(int__ i=(j);i<(int__)(k);i++)

const int MOD = 100000;

bool solve(){
    int N, M, S; cin >> N >> M >> S;
    if(N == 0) return false;
    vector<vector<int>> dp(N*N+1, vector<int>(S+1));
    // dp[i][j] := i個選んで総和がjの組み合わせ数
    dp[0][0] = 1;
    repeat(i, 1, M+1){
        for(int j = N*N-1; j >= 0; j--){
            rep(k, S+1-i){
                dp[j+1][k+i] += dp[j][k];
                dp[j+1][k+i] %= MOD;
            }
        }
    }
    cout << dp[N*N][S] << endl;
    
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    while(solve());
    return 0;
}


comments powered by Disqus