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

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.269 見栄っ張りの募金活動

問題はこちら
No.269 見栄っ張りの募金活動 - yukicoder

これはメモ化再帰が書きやすかった

int a[101][20001],l[101][20001];

int f(int n,int s){
	//k=0のときn人でちょうどs円払う方法
	if(l[n][s]++)return a[n][s];
	if(n==0)return !s;
	//0円は0人で払える
	return a[n][s]=(f(n-1,s)+(s<n?0:f(n,s-n)))%1000000007;
	//1人目が1円も払わない場合f(n-1,s)
	//1人目が"とりあえず"1円払う場合、n人全体でn円払うことが確定するので
	//残りn人でs-n円
}

int main(){
	int n,s,k,i,j;
	scanf("%d%d%d",&n,&s,&k);
	s-=n*(n-1)/2*k;
	//kの分を先に処理しておくことでk=0としてよい
	if(s<0)puts("0");
	else printf("%d",f(n,s));
	return 0;
}

予めKの分を処理しておくことでK=0としてよい

「i番目の人は、i-1番目の人よりa[i](≧0)円多く払うときの合計金額」を考えることになる(iは1-basedで、0番目の人は0円とおく)
この時に払われる合計金額はΣ[i=1~n]Σ[j=1~i]a[j]となるのでΣの順序を入れ替えて
Σ[j=1~n]a[j]*(n+1-j)となる。
(このことは以下の表を眺めていれば分かる)
(a={1,2,0,1,2}として、i番目の人の寄付額を縦棒グラフとして図式化したものを、横方向に合計する)

1
1
2
4
4
5
1 3 3 4 6

ということで、結局問題は次のように読み替えられる
「n,sが与えられた時、Σa[j]*(n+1-j)=s を満たすようなa[j]≧0は何通りあるか?」
さらに言えば(n+1-j)が1~nであることから
「1~n円玉でちょうどs円払う方法は何通りか?」となりyukicoder No.41 貯金箱の溜息(EASY) - メモと全じ方法で求める事ができる
こんな感じ

a['~~'],i,n,s,m=1e9+7;
main(j){
	*a=1;
	scanf("%d%d%d",&n,&s,&j);
	s-=~-n*n/2*j;
	for(i=1;i<=n;i++)for(j=1;j<s;j++)a[j+i]=(a[j+i]+a[j])%m;
	i=!printf("%d",s<0?0:a[s]);
}

(なお「a['~~']={1};」と記述するとFile size limit exceededなるエラーが出る。参考:C/C++でグローバル変数(配列)を0以外に初期化すると実行ファイルが巨大になる罠 - Qiita
ということでこれを縮めて

a['~~'],i,n,s,m=1e9+7;
main(j){
	*a=1;
	scanf("%d%d%d",&n,&s,&j);
	for(s-=~-n*n/2*j;i++<n;)for(j=i-1;j++<s;a[j]%=m)a[j]+=a[j-i];
	i=!printf("%d",s<0?0:a[s]);
}

ポインタを使うと1B縮んで

a['~~'],i,n,s,m=1e9+7,*p;
main(j){
	*a=1;
	scanf("%d%d%d",&n,&s,&j);
	for(s-=~-n*n/2*j;i++<n;)for(p=a;p-a<s;p++[i]%=m)p[i]+=*p;
	i=!printf("%d",s<0?0:a[s]);
}

148B