寝癖頭の解法

勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #F - ビンゴ

第8回日本情報オリンピック 予選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#F - ビンゴ

atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#F - ビンゴ
https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_f
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=100000;
int main(void){
  ll n,m,s;
  cin>>n>>m>>s;
  vector<vector<ll>> dp(s+1,vector<ll>(m+1,0));
  for(ll i=1;i<=m;i++){
    if(i>s){
      break;
    }
    for(ll j=i;j<=m;j++){
      dp[i][j]=1;
    }
  }
  for(ll i=1;i<n*n;i++){
    vector<vector<ll>> dp2(s+1,vector<ll>(m+1,0));
    for(ll j=1;j<=s;j++){
      for(ll k=1;k<=m;k++){
        dp2[j][k]=dp2[j][k-1];
        if(j>=k){
          dp2[j][k]+=dp[j-k][k-1];
        }
        dp2[j][k]%=mod;
      }
    }
    dp=dp2;
  }
  cout<<dp[s][m]<<endl;
  return 0;
}