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

メモ

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

yukicoder No.338 アンケート機能

問題はこちら
No.338 アンケート機能 - yukicoder

以下では「四捨五入」「切り捨て」などはすべて「小数点以下~」のことを表す

200人いれば必ず達成できる
なぜなら、A+Bが100のときはそれぞれ2A人,2B人いればOK
A+Bが101のときはそれぞれ(2A-1)人、(2B-1)人いればOK
(この時(2A-1)/200*100=A-0.5であり、四捨五入するとAになる。Bも同様)
ということで、「i人中j人がYesと答えた」という場合についてiが小さい方から総当りすれば良い(0≦j≦i、1≦i≦200なので2万通り程度)
この時、百分率での割合はj/i*100となるので、これを四捨五入することを考える
「四捨五入する」は「0.5を足して小切り捨てる」と同値なので、j/i*100を四捨五入したものは
floor(j/i*100+0.5)=floor( (j*100+i/2)/i) となる
ここでi,jは整数なので、これはfloor( (j*100+floor(i/2))/i)に等しく、結局整数の範囲で計算して良いことが分かる

int main(){
	int i,j,a,b;
	scanf("%d%d",&a,&b);
	for(i=1;;i++)for(j=0;j<=i;j++){
		if(a==(j*100+i/2)/i&&b==((i-j)*100+i/2)/i){
			printf("%d",i);
			return 0;
		}
	}
}

ということでこれを縮めていって

j,a,b;main(i,f){for(scanf("%d%d",&a,&b);f;i++)for(j=0;a-(j*100+i/2)/i|b-((i-j)*100+i/2)/i?j++<i:(f=!printf("%d",i)););}
//フラグで管理
i,a,b;main(j){for(j=-scanf("%d%d",&a,&b);j<0;)for(j=++i;a-(j*100+i/2)/i|b-((i-j)*100+i/2)/i?j--:!printf("%d",i););}
//jを逆にした
i,a,b;main(j){for(j=-scanf("%d%d",&a,&b);j<0?j=++i:a-(j*100+i/2)/i|b-((i-j)*100+i/2)/i?j--,1:!printf("%d",i););}
//変則的ループ圧縮

112B

「i人中j人がA%」となるようなi,jを直接求めるのは (A/100-0.5)*i≦j<(A/100+0.5)*i を解くことになり、iごとにjを求めるだけでも結構めんどくさい

16/06/16追記
よく考えればjの正負を逆にすれば縮む

i,a,b;main(j){for(scanf("%d%d",&a,&b);j>0?j=-++i:a+(j*100-i/2)/i|b-((i+j)*100+i/2)/i?j++,1:!printf("%d",i););}

110B


16/10/20追記
,1っていうのがどう見ても冗長。どうにかできないか。
j++が0にならないように、jには-i-1から-1まで動いて欲しい

j,i,a;main(b){for(scanf("%d%d",&a,&b);!j?j=~++i:a-(~j*100+i/2)/i|b-((i-~j)*100+i/2)/i?j++:!printf("%d",i););}

…いやこれよく考えたらjのincの位置変えれば縮むよね?
これで再びjは-iから0までを動くようになった

j,i,a;main(b){for(scanf("%d%d",&a,&b);!j++?j=~++i:a+(j*100-i/2)/i|b-((i+j)*100+i/2)/i?:!printf("%d",i););}

106B