期待値のいい性質
前書き～あれ400なのマ～ジ？～
こんにちはこんばんはおはようございます、B600点でWAが取れない、ヤカタです。 AtCoder Grand Contest 049 - AtCoderにレート44吸われたために落ち込んでますが、上の人たちがパフォーマンス2000台叩き出しているのを見ると、1回そういうことがあったからとかあんまり気にせずに色々やっていくべきなんだろうななどと思うわけです。
ということで、理屈は分かっていたBは置いておいて、歯が立たなかったAを見ていこうと思います。
AGC049_A
まず、Nを105で出している時点で、O(N2)、つまりある頂点とその関係を見る、みたいなことを拒否されているわけなんだから、「ある頂点ごとに状態Xがまとめられて、その状態XをN個集めると答えになる」というような状態Xを見つける必要がある。
今回で言えば、期待値でかつ、それぞれの頂点がたかだか一度しか選ばれないことを利用して（後者はいらないかも）、状態X＝その頂点が選ばれる確率 とできる。ここに気づけたら、何とか状態を書きだせないかとやってみるとうまくいく。（ここまで見れば解説読んでわかる）
期待値のいい性質
Wikiに普通にまとまってたので引用。重要なのは線形性。単調性も時々使うイメージ
