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

メモ

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

yukicoder No.250 atetubouのzetubou

問題はこちら
No.250 atetubouのzetubou - yukicoder

互いに区別されるD個の箱に、ちょうどX個の玉をいれる場合の数に等しい
これは重複組合せで求める事ができ
\begin{eqnarray*}_DH_X&=&_{D+X-1}C_{D-1}\\&=&\frac{(X+D-1)!}{X!(D-1)!}\\&=&\frac{X+D-1}{D-1}\frac{X+D-2}{D-2}...\frac{X+1}{1}\end{eqnarray*}
となる
ところで最後の式の後ろからi項の部分積\frac{X+i}{i}\frac{X+i-1}{i-1}...\frac{X+1}{1}はもちろん_{i+1}H_Xなので整数であることから、整数の範囲で後ろから順番に計算していくことができる
また、そこに登場する各分数は(分子)-(分母)=X>0なので1より大きく、この部分積は単調増加だから、いったんTより大きくなったらそこで打ち切って良い
さらに、D,X≦1000、T≦10^15なので、64bitなら計算の途中でオーバーフローしない

int main(){
	int q,d,x,i;
	long s,t;
	scanf("%d",&q);
	while(q--){
		scanf("%d%d%ld",&d,&x,&t);
		s=1;
		for(i=1;i<d;i++){
			s=s*(x+i)/i;
			if(s>t)break;
		}
		puts(s<=t?"AC":"ZETUBOU");
	}
	return 0;
}

ささっと縮める

long t,s;
x,d;
main(i){
	for(gets(&i);s=~scanf("%d%d%ld",&d,&x,&t);puts(s>t?"ZETUBOU":"AC"))
		for(s=i=1;i<d&s<=t;s/=i++)s*=x+i;
}

でループ圧縮したいなあと睨んでみた

for(gets(&i);s=i=scanf("%d%d%ld",&d,&x,&t)>0;puts(s>t?"ZETUBOU":"AC"))for(;i<d&s<=t;s/=i++)s*=x+i;
//これではRE
for(;i<d&s<2e15?s*=x+i,s/=i++:(i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),s=i););
//ループ圧縮してみた
for(;s=i<d&s<2e15?s*(x+i)/i++:(i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),i););
//sへの代入をくくりだした
for(;s=i>=d|s>2e15?i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),i:s*(x+i)/i++;);
//三項演算子の真偽を入れ替えてカッコを外した

途中を全部投げたわけではないのでわからないけれど、

//下から二番目
long t,s;x,d;main(i){for(;s=i<d&s<2e15?s*(x+i)/i++:(i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),i););}
//↑RE ↓AC
long t,s;i,d;main(x){for(;s=i>=d|s>2e15?i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),i:s*(x+i)/i++;);}
//一番下

となって、REになったりならなかったりするのがよくわからない

117B