349.1

なんかひどいセット...。

250

円のパラメータが与えられるので、交点はいくつありますか、という問題。

やるだけ。

500

面の数がまちまちなサイコロセットが与えられるので、全部振ったときに出る目のパターンとして可能なものはいくつあるか答えよ、という問題。

こういう問題を見たら、取り敢えず何も考えずにサイコロの面の数でソートしてから考えると良いような気がする。ということでソート。こうしてやって、サイコロを順番に振っていくことにする。

面数の少ないサイコロがどう頑張っても出せない目を出す場合、パターンは増える。しかし、それ以外の場合では、既に出ている盤面と合流する可能性がある。これを整理すると、今までに出た目の最大値以上の目を出せば、新しい盤面になり、そうでなければ既存の盤面と合流する。なので、振ったサイコロの数と、今までに出た最大値の目の値でDPすれば良い。

1000

袋の中に赤い玉がR個と青い玉がB個入っており、そのうちのK個を中身を見ずに取り除いた状態になっている。このとき、1個以上3個以下の玉を交互に取り出し、最後の赤い玉を取り出した方が負けとして、勝率の期待値を答えよ、という問題。

袋の中身が分かっていればただのDPをやるだけ。それが分からないので、各盤面のときに取る数と勝率をメモしておき、それぞれの盤面の確率を覚えておいて、取った数ごとに勝率を計算してやるようなDPにすれば良さそう。後でちゃんとやる。