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

裏紙

ほぼ競プロ、たまに日記

AOJ 0537 - Bingo

問題

Bingo | Aizu Online Judge

問題概要

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

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

  •  1 \le N \le 7
  •  1 \le M \le 2000
  •  1 \le S \le 3000

イデア

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

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

よって,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;
}