yukicoder No.385 カップ麺生活

問題はこちら
No.385 カップ麺生活 - yukicoder

まずは「ちょうどk円で買えるカップ麺の最大個数」を求める。
これは要するに「Ci円玉でちょうどk円払う時、最大で何枚の硬貨が使えるか」なので、DPでできる。
（c.f.yukicoder No.247 線形計画問題もどき - メモ）
「金欠チャンス」を使用する時、その順序は関係なく、可能な限り多くの金欠チャンスを使うことが良いのは明らか。
よって「(M-素数)円で買えるカップ麺の個数」を全ての素数にわたって合計すれば良い。
「金欠チャンス」を使い果たしたら、最後は一番安いものを買い込めばいいので最後にM/min(Ci)を加える

#define max(p,q)(p>q?p:q)
prime[2000]={2,3},s=2;
void makeprime(int m){
	int i,n;
	for(n=5;n<m;n+=2){
		for(i=3;i*i<=n;i+=2)if(n%i==0)break;
		if(n%i)prime[s++]=n;
	}
	prime[s]=1e6;//番兵
}

int c(int*a,int*b){return*a-*b;}
int main(){
	long ans=0;
	int i,j,m,n,a[30];ma[20010];
	makeprime(m);
	scanf("%d %d",&m,&n);
	for(i=0;i<n;i++)scanf("%d",a+i);
	qsort(a,n,4,c);
	ma[0]=1;
	for(i=0;i<10000;i++)for(j=0;j<n;j++)if(ma[i])ma[i+a[j]]=max(ma[i]+1,ma[i+a[j]]);
	//ma[i]には、「i円で買える最大個数+1」を保存する
	for(i=0;prime[i]<m;i++)if(ma[m-prime[i]])ans+=ma[m-prime[i]]-1;
	printf("%ld",ans+m/a[0]);
	return 0;
}

いつもどおり、DPする部分でわざわざCiを配列に保存する必要はない
min(Ci)も逐次更新すればいい
さらに素数の配列もいちいち作る必要はなさそう

q[20010],j,m,x=1e6,s,*p;
main(i){
	for(*q=scanf("%d%*d",&m);~scanf("%d",&j);x>j?x=j:0)for(p=q;p-q<1e4;p++)*p&&*p>=p[j]?p[j]=*p+1:0;
	//読み込みながらDP。Ciの最小値をxに保存
	for(s=m/x;++i<m;s+=!q[m-i]|i-j?0:q[m-i]-1)for(j=1;++j<i&&i%j;);
	//素数判定しながら合計
	x=!printf("%d",s);
}

配列の添字は逆にしたほうがわかりやすい。つまりq[i]には「所持金がi円になった時に買える最大個数+1」を保存
こうすると1つめのループがだいぶ長くなってしまうけど、2つ目のループがmのカウントダウンで書け、変数iが要らなくなったのでトータルでは得。
ところで、合計する部分でq[i]-1ってあるけど、q[i]に保存するものの正負を逆にすればこれは~q[i]で書ける。これも縮みそう
ということで出来上がったものがこちら

q['~~'],m,x=1e6,*p;
main(j){
	for(scanf("%d%*d",&m),q[m]--;~scanf("%d",&j);x>j?x=j:0)for(p=q+'()';q-p--;p[j]&&p[j]<=*p?*p=p[j]-1:0);
	for(x=m/x;j=--m>1;x+=!q[m]|m-j?0:~q[m])for(;m%++j;);
	x=!printf("%d",x);
}

Mが1のケースがあるからループ圧縮は無理そう
200B