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

メモ

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

yukicoder No.118 門松列(2)

問題はこちら
No.118 門松列(2) - yukicoder

竹は互いに区別するので、例えば長さが相異なるi,j,kである竹が各a,b,c本あれば、求める値はa*b*cになることがすぐ分かる
竹の長さは100以下なので、各長さの竹が何本あるかを調べて合計を求めれば良い

int main(){
	int n,i,j,k;
	long s=0,a[101]={};
	scanf("%d",&n);
	while(n--){
		scanf("%d",&i);
		a[i]++;
	}
	for(;++k<101;)for(j=k;++j<101;)for(i=j;++i<101;)s+=a[i]*a[j]*a[k];
	printf("%d",s%=1000000007);
	return 0;
}

潰す

long s,a[101];
j,k;
main(i){
	for(gets(a);~scanf("%d",&i);a[i]++);
	for(;++k<101;)for(j=k;--j;)for(i=j;--i;)s+=a[i]*a[j]*a[k];
	s=!printf("%d",s%=i=1e9+7);
}

ループを順に潰す

for(j=k;--j;)for(i=j;--i;)s+=a[i]*a[j]*a[k];
//↓1つめ
for(j=k;i--?s+=a[i]*a[j]*a[k],1:(i=--j););
//iの初期値とa[0]を0にしなければならなくなった

for(;++k<101;)for(j=k;i--?s+=a[i]*a[j]*a[k],1:(i=--j););
//↓2つめ
for(k=101;i--?s+=a[i]*a[j]*a[k],1:(i=--j)?:(j=--k););
//jの初期値を1にしなければならなくなった

for(gets(a);~scanf("%d",&i);a[i]++);for(;i--?s+=a[i]*a[j]*a[k],1:(i=--j)?:(j=--k););
//↓3つめ
for(gets(&t);~scanf("%d",&t)?++a[t]:i--?s+=a[i]*a[j]*a[k],1:(i=--j)?:(j=--k););
//a[0]とiのために別変数tを用意した

以上をまとめて

long s,a[101];
i,t,k=101;
main(j){
	for(gets(&t);~scanf("%d",&t)?++a[t]:i--?s+=a[i]*a[j]*a[k],1:(i=--j)?:(j=--k););
	s=!printf("%d",s%=i=1e9+7);
}

140B