2015年2月8日日曜日

yukicoder 144 エラトステネスのざる

問題

http://yukicoder.me/problems/242

解法

2~Nの間の各数字iに対してPr{iが生き残る}を計算する.
E{残った数字の個数} = Σ( E{1{iが生き残る}}) = ΣPr{iが生き残る}
となるので計算したものの総和でおk.
Pr{iが生き残る}はエラトステネスで倍数のやつに1-p倍するみたいなことをする.

こういう問題をぱっと解けるようになりたい



0 件のコメント:

コメントを投稿

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...