AOJ 0537 - Bingo

問題

Bingo | Aizu Online Judge

問題概要

ビンゴカードは正方形となっているが，実際これは1次元配列として考えても差し支えがない．

つまり，「要素数がで，各要素の値が以上以下で，全ての要素の合計がであるような厳密に単調増加する数列として考えられる組み合わせの総数をで割った余りを求めよ」という問題．

• 
• 
• 

アイデア

まず，自分が考えた割とすんなりと思いついたDPは，dp[x][y]=前の要素の値がx，現在の合計がyを保存しながらこれを更新するのを回繰り返すというものだが，1回の更新のためにかかってしまうので，とてもじゃないけどきつい．

しかしながら，実は前の要素の値が何であったかなどを考える必要が実はない．「からの個の数字の中から個を選んでちょうどその合計をにできる組み合わせの個数」を考えれば良いということに気づく．なぜなら，数字を適当に選んでしまえば，それを後から小さい順に並べれば題意を満たすようなカードを作れるからだ．

よって，dp[x][y][z]=今xまで使うかどうかを決めて，現在y個使うことが決まっており，現在の合計値はzであるときの組み合わせの個数を持ちながら更新していけばよいということになる．ただし，これを配列として用意するのはメモリ的に厳しいので，遷移に注目するとxに関してはxからx+1にしか遷移することがないので，dp[2][y][z]を用意して交互に再利用していくだけでその遷移を実現することが可能である(実装ではdpからnewdpに遷移させ，そのターンでの遷移が終わったらnewdpをdpにコピーしている)．

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int dp[50][3001];
int newdp[50][3001];

int main()
{
    const int mod=100000;
    int n,m,s;
    while(cin >>n >>m >>s,n)
    {
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;

        //iを使うかどうか
        for(int i=1; i<=m; ++i)
        {
            memset(newdp,0,sizeof(newdp));

            rep(j,n*n+1)rep(k,s+1)
            {
                //使う
                if(j<n*n && k+i<=s)
                {
                    newdp[j+1][k+i]+=dp[j][k];
                    newdp[j+1][k+i]%=mod;
                }

                //使わない
                newdp[j][k]+=dp[j][k];
                newdp[j][k]%=mod;
            }

            //copy
            rep(j,n*n+1)rep(k,s+1) dp[j][k]=newdp[j][k];
        }

        cout << dp[n*n][s] << endl;
    }
    return 0;
}