yukicoder No.425 ジャンケンの必勝法

1回目：
勝ち→1/3
負け→1/3
あいこ→1/3

なので「前回があいこで、今回必勝法を使う確率がpのときに勝つ確率」をf(p)とすると、求めるべきは当然　1/3+1/3*f(p)　となる。

前回があいこで、今回必勝法を使う確率がpのとき：
必勝法で勝ち→p/2
必勝法であいこ→p/2
普通に勝ち→(1-p)/3
普通に負け→(1-p)/3
普通にあいこ→(1-p)/3

であることから
f(p)=p/2+p/2*f(p-q)+(1-p)/3+(1-p)/3*f(p+q)
が成立する。
fの定義域は[0,1]の0.01刻みの値しか取らないことから101元連立方程式に帰着された。
これを解くという方針がtester解

ところで、「前回があいこで、今回必勝法を使う確率がpのとき今回もあいこになる確率」はp/2+(1-p)/3=(2+p)/6なので高々1/2。つまり20回あいこになる確率は高々(1/2)^20<10^6。
ということで、結局20回くらいまでシミュレーションすればよい

double p,q;
double f(int n,double p){
	if(n>21)return 0;//[0,1]の適当な値を返せばよい
	return p/2+p/2*f(n+1,fmax(0,p-q))
		+(1-p)/3+(1-p)/3*f(n+1,fmin(1,p+q));
}
int main(){
	scanf("%lf%lf",&p,&q);
	p*=.01;q*=.01;
	printf("%.9f",f(1,p)/3+1/3.);
	return 0;
}

fの引数の型を書かないといけないのは長いので、pを100で割らないことにして適当にカッコでくくる

q;
double f(n,p){return n<22?p/2e2*(1+f(n+1,p<q?0:p-q))+(100-p)/3e2*(1+f(n+1,p>100-q?100:p+q)):0;}
main(p){
scanf("%d%d",&p,&q);
q=!printf("%.9f",(f(1,p)+1)/3);
}

scanfをfの引数に押し込むために引数の順序を入れ替えて、またfの返り値をfloatにしても通ることを確認

q;
float f(p,n){return n<23?p/2e2*(1+f(p<q?0:p-q,++n))+(100-p)/3e2*(1+f(p>100-q?100:p+q,n)):0;}
main(p){q=!printf("%.9f",(f(p,scanf("%d%d",&p,&q))+1)/3);}

152B

2016/10/17追記
三項演算子の前後を入れ替えて1B短縮

q;
float f(p,n){return n>22?:p/2e2*(1+f(p<q?0:p-q,++n))+(100-p)/3e2*(1+f(p>100-q?100:p+q,n));}
main(p){q=!printf("%.9f",(f(p,scanf("%d%d",&p,&q))+1)/3);}

151B

2017/07/26追記

float f(p,n){return n>22?:p/2e2*(1+f(p<q?0:p-q,++n))+(100-p)/3e2*(1+f(p>100-q?100:p+q,n));}
//nをincするタイミングの変更
float f(p,n){return++n>23?:p/2e2*(1+f(p<q?0:p-q,n))+(100-p)/3e2*(1+f(p>100-q?100:p+q,n));}
//f+1をfと置換
float f(p,n){return++n>23?:p/2e2*f(p<q?0:p-q,n)+(100-p)/3e2*f(p>100-q?100:p+q,n)+1;}

出力はデフォルトが6桁であり、これでどうにか精度が足りるらしい

q;
float f(p,n){return++n>23?:p/2e2*f(p<q?0:p-q,n)+(100-p)/3e2*f(p>100-q?100:p+q,n)+1;}
main(p){printf("%f",f(p,scanf("%d%d",&p,&q))/3);}

135B

メモ

yukicoderでゆるふわgolf

yukicoder No.425 ジャンケンの必勝法