「会津大学オンラインジャッジ思考中問題一覧」の編集履歴（バックアップ）一覧に戻る

会津大学オンラインジャッジ思考中問題一覧 - (2011/08/06 (土) 10:21:27) のソース

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

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

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



// 0537bingo.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

#include "stdafx.h"

#include<stdio.h>
#include<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);
	}
}