メモ

yukicoderでゆるふわgolf

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

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

これはメモ化再帰が書きやすかった
予めKの分を処理しておくことでK=0の場合に帰着すると良い

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の分を処理
	if(s<0)puts("0");
	else printf("%d",f(n,s));
	return 0;
}

K=0の場合「i番目の人は、i-1番目の人よりa_i(≧0)円多く払うときの合計金額」を考えることになる(iは1-basedで、a_0=0とおく)
この時、i番目の人が払う金額は\sum_{j=1}^i a_jなので、合計金額は\sum_{i=1}^n \sum_{j=1}^i a_jとなる。
a_jが何回登場するかを考えて和の順を変えると\sum_{j=1}^n (n+1-j)a_jとなる。
よって結局、問題は次のように読み替えられる
「n,sが与えられた時、\sum_{j=1}^n (n+1-j)a_j=sを満たすような\{a_j\geq 0\}の組は何通りあるか?」
さらにaのindexを逆にする、すなわちa_ja_{n+1-j}と置き換えることで目的の式は\sum_{j=1}^n j a_j=sとなるので、これは「1~n円玉でちょうどs円払う方法は何通りか?」となりyukicoder No.41 貯金箱の溜息(EASY) - メモと同様の方法で求める事ができる
(No.41は「s円"以下"」であり、こちらは「"ちょうど"s円」という違いがある点に注意)

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