ICFPの裏番組。吟味時間薄いや。
250 (level1)
ハードディスクが複数あって、壊れる確率がそれぞれ与えられるので、そのうちのN個が壊れる確率をそれぞれ求めよという問題。
それぞれ壊れた場合と、壊れなかった場合で分岐しつつ、テーブルを更新すればおしまい。
500 (level2)
N個の点から任意の三つを選んでできる円の種類を答えよという問題。
単純にdoubleの精度じゃうまくいかないよ、ってことが言いたかったらしい。分数クラスを書きましょう。(書いたけど本質的なところで使わなかったというダメっぷり。)
1000 (level3)
バブルソートの最外周ループの実行回数を答えよという問題。要素数は1M個まで。
自分の左側にある自分よりも小さい要素が、自分の右側にある自分よりも大きな要素のソートが終わるまでに自分の隣に来るかどうかで、自分が原因となる最外周ループを駆動するかどうかが分かる。というのをまじめにやればできるはず。
