478.1

結果は変わらないとは思うけれど、もっといいコンディションでやりたかったセット。

250

ある整数Xについて4X+3また8X+7に変換する処理をするとき、法Mの世界で0になるのは何ステップ目か、という問題。

かなり状態が合流するので、何も考えずにBFSで通った。合流することを利用すると、どっちの処理を何回、みたいなので計算可能になるらしいので、綺麗に解けるらしい。

500

見てない。

1000

N個の箱にK種類のリンゴがそれぞれ入っている。等確率で、空ではない箱集合のサブセットを選び、リンゴを一つの箱にまとめる。まとめた後で一個のリンゴを取り出すとき、それぞれの種類のリンゴが取得される確率を答えよ、という問題。

それぞれの箱について独立に計算でき、後で合算することを考える。つまり、ある箱集合のサブセットが決まれば、全体のリンゴの個数さえ分かっていれば、自分の箱の中のリンゴの分布だけを考える、というのをすべての箱について計算すれば良い。

個別の箱について、すべての箱集合のサブセットを考える必要があるので、箱集合のサブセットについて、リンゴの総数とそうなる組み合わせの数を計算する。すべての箱について、吟味したものを作っておけば、自分の箱の中身の数から、自分が含まれる箱集合のサブセットがどれかは判定できる。一番でかいケースは自分を常に含み、それから自分の大きさを引いたのは含まず、含まないのを引いても残っている分は含み...といった感じ。

で、自分の箱の中の各リンゴについての吟味は最後に別ループでやるとして、箱集合サブセットの組み合わせの数を箱集合のリンゴ総数で割ったものの総和というのを書く箱について計算しておく。後は各リンゴについての処理を最後にやる。(単純にやるとリンゴの種類倍だけ遅くなるので、ループを適切に分割しましょう、というだけのことなので、適当にループを作って答えがあうのを確認してから分割した方がいい。)