解けなかった問題を覚書程度に記す。
ABC149E
こういう問題をすっと解きたい。
ナイーブにやるとするとを上からとればいい。しかしこれは数列の長さがでありソートにも時間がかかるのでできない。困った。
ここで,この個の数列の特別な構造を用いる。例えばあらかじめ数列Aをソートしておけば,を固定した時のは単調増加の数列となる。つまりその中では2分探索などの強力なツールをで実行できる。完全にランダムなこの数列のときには,前処理に結局かかるので使えない。今回はで済んでいる。これがミソ。
幸福度が以上となるようなのペアの個数を探す。これはを固定した数列に対して二分探索を実行すれば求まるので,で済む。あとはについて二分探索することで,幸福度が全て以上であるようなペアが個以上あるような,の下限を求めることができる。
そのようなが求まれば,あとは各を固定した時の数列に対し,以上のものの和を求める。これはで表される累積和を用いればで求まる。ただし足しすぎ(M個以上足してしまう)に注意。
なお,幸福度が以上となるようなのペアの個数を探すところで,しゃくとり法も使える。数列Aをあらかじめ昇順ソートした後,テーブルの横軸が,縦軸がとなるように配置すれば結構綺麗な形になる。つまり,各を固定した行について幸福度が以上となる最小のは,下に行くにつれ単調に右にずれていく。
ABC149F
難しくない????????????????????(逆ギレ)
競プロという(一般的に見て)マイナーコンテンツの,年の瀬の,unratedのコンテストの時間内に,こんな難しい問題を解く人が100人以上いるなんて,日本の未来は明るいですよ。ほんとうに。いやほんと。
解き方1
editorialの解き方。まず期待値の線形性からこんな鮮やかに分割できるところがすばらしい。Sの穴あき度の期待値は,Sの頂点数の期待値から,Sに含まれる黒丸の期待値を引いたもの。Sは全ての黒丸を含むように構成しているのだから,後者についてはとなる。問題は前者。
Sの頂点数の期待値について,これまた各辺にバラして考えて,(各辺がSに含まれる期待値の合計)+1となる。ただし空グラフの分は除く。
各辺がSに含まれる期待値は,その辺により木が個と個の木に分解されるとして,
となる。あとはこれを枝について和を取る。まとめると,
(こたえ)
となる。この分母を,分子をとおき,とする。すると求めるは,
なので,けっきょくとはで割った余りを用意しておけば十分。
であり,なので(モジュラ逆数),これでやっと答えが出る。最後の方はこういう問題では当然なのかな。
解き方2
たぶん頂点ごとに見る方がはるかに見通しが立ちやすい(し方針も立てやすい)と思う。解説はいろんなサイトがしているからここには書かないけれど(じゃあeditorial丸写しもするな)。単なる木の再帰を全方位DPっていうみたい。言葉尻が強い。