※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0537
0537 Bingo
これ難しいなあ、本当に高校生2年生向けプログラムコンテストの予選問題?
問題的にいえばs-(n*n*(n*n+1))/2=1*A1+2*A2+,,,,+n^2*An^2;
Aiは0以上の整数。
ベクトルB={A1,A2,,,An^2}
この条件を満たすベクトルBが何本あるか答えよという問題なのだが。
うーん?

組み合わせ数からいって深さ優先探索は当然除外。
幅優先探索は使えるのか使えないのか不明。
メモ化探索した下記コードで一応正しい答えが出るものの速度が出ない。
どうとけばいいのだろう?

もしかして漸化式を立てて、升目サイズ、合計値、上限値の3次元空間で漸化式の計算をするのだろうか?
上限値がなければ漸化式が楽に立てれそうなのだけど?
恐ろしいのは高校生にしてこの問題を制限時間内に解いている人がいるというところだな。
発送が柔軟なんだろうな、高校生以下の俺って一体、、、、




#include plugin Error : 指定されたページはございません。
"stdafx.h"

#include plugin Error : 指定されたページはございません。
<stdio.h>
#include plugin Error : 指定されたページはございません。
<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);
}
}