組み合わせ数からいって深さ優先探索は当然除外。
幅優先探索は使えるのか使えないのか不明。
メモ化探索した下記コードで一応正しい答えが出るものの速度が出ない。
どうとけばいいのだろう?
もしかして漸化式を立てて、升目サイズ、合計値、上限値の3次元空間で漸化式の計算をするのだろうか?
上限値がなければ漸化式が楽に立てれそうなのだけど?
恐ろしいのは高校生にしてこの問題を制限時間内に解いている人がいるというところだな。
発送が柔軟なんだろうな、高校生以下の俺って一体、、、、
"stdafx.h"
<stdio.h>
<map>
void calc(int n,int m,int s){
int size=n*n;
int t,sum;
std::map<int,int> memo[2002];
std::map<int,int>::iterator it;
s-=(size*(size+1))/2;
if(s==0){
printf("1\n");
return ;
}
memo[0][0]=1;
int ans=0;
for(int i=0;i<=size;i++){
t=size-i;
for(int j=0;j<m;j++){
if(size+j>m) break;
if(memo[j].empty()==true) break;
if(i==size){
it=memo[j].lower_bound(s-1);
}else{
it=memo[j].begin();
}
while(it!=memo[j].end()){
sum=(*it).first+t;
if(i==size-1){
if((*it).first==s){
ans+=(*it).second;
ans%=100000;
break;
}
}
if(sum>s) break;
if(memo[j+1].find(sum)==memo[j+1].end()){
memo[j+1][sum]=memo[j][(*it).first];
}else{
memo[j+1][sum]=(memo[j][(*it).first]+memo[j+1][sum])%100000;
}
it++;
}
}
/*
for(int k=0;k<m;k++){
it=memo[k].begin();
if(it==memo[k].end()) break;
printf("\n%d\n",k);
while(it!=memo[k].end()){
printf("<%d %d>",(*it).first,(*it).second );
it++;
}
}
*/
}
printf("%d\n",ans);
}
int main(){
int n,m,s;
scanf("%d %d %d",&n,&m,&s);
while(n!=0 || m!=0 || s!=0){
calc(n,m,s);
scanf("%d %d %d",&n,&m,&s);
}
}
最終更新:2011年08月06日 10:21