こんちゅう

エッセイ・小説・ブログ・楽譜置き場。 不定期更新。

AtCoder ABC 149

解けなかった問題を覚書程度に記す。

ABC149E

atcoder.jp

こういう問題をすっと解きたい。

ナイーブにやるとすると A_i+A_jを上からとればいい。しかしこれは数列の長さがO(N^2)でありソートにも時間がかかるのでできない。困った。

ここで,このN^2個の数列の特別な構造を用いる。例えばあらかじめ数列Aをソートしておけば,A_iを固定した時のA_i+A_jは単調増加の数列となる。つまりその中では2分探索などの強力なツールをO(logN)で実行できる。完全にランダムなN^2この数列のときには,前処理に結局O(N^2logN)かかるので使えない。今回はO(NlogN)で済んでいる。これがミソ。

幸福度がD以上となるようなA_i+A_jのペアの個数を探す。これはA_iを固定した数列に対して二分探索を実行すれば求まるので,O(NlogN)で済む。あとはDについて二分探索することで,幸福度が全てD以上であるようなペアがM個以上あるような,Dの下限を求めることができる。
そのようなDが求まれば,あとは各A_iを固定した時の数列に対し,D以上のものの和を求める。これはS_n=A_1+\cdots +A_nで表される累積和を用いればO(NlogN)で求まる。ただし足しすぎ(M個以上足してしまう)に注意。

なお,幸福度がD以上となるようなA_i+A_jのペアの個数を探すところで,しゃくとり法も使える。数列Aをあらかじめ昇順ソートした後,テーブルの横軸がA_1,A_2,\cdots A_N,縦軸がA_N, \cdots ,A_1となるように配置すれば結構綺麗な形になる。つまり,各A_iを固定した行について幸福度がD以上となる最小のA_jは,下に行くにつれ単調に右にずれていく。

ABC149F

atcoder.jp

難しくない????????????????????(逆ギレ)
競プロという(一般的に見て)マイナーコンテンツの,年の瀬の,unratedのコンテストの時間内に,こんな難しい問題を解く人が100人以上いるなんて,日本の未来は明るいですよ。ほんとうに。いやほんと。

解き方1

editorialの解き方。まず期待値の線形性からこんな鮮やかに分割できるところがすばらしい。Sの穴あき度の期待値は,Sの頂点数の期待値から,Sに含まれる黒丸の期待値を引いたもの。Sは全ての黒丸を含むように構成しているのだから,後者については\frac{N}{2}となる。問題は前者。
Sの頂点数の期待値について,これまた各辺にバラして考えて,(各辺がSに含まれる期待値の合計)+1となる。ただし空グラフの分は除く。
各辺がSに含まれる期待値は,その辺により木がx_e個とN-x_e個の木に分解されるとして,
(1-(\frac{1}{2})^{x_e})(1-(\frac{1}{2})^{N-x_e})
となる。あとはこれを枝について和を取る。まとめると,
(こたえ)=\sum_e (1-(\frac{1}{2})^{x_e})(1-(\frac{1}{2})^{N-x_e})+1-\frac{1}{2^N}-\frac{N}{2} \\
=\frac{1}{2^N}(N2^{N-1}+(N-2)-\sum_e (2^{x_e}+2^{N-x_e}))

となる。この分母をx,分子をyとおき,x=pM+x', y=qM+y'とする。すると求めるzは,
(pM+x')z \equiv (qM+y') (mod M)
なので,けっきょくxyMで割った余りを用意しておけば十分。
z=yx^{-1}であり,x^{-1}=x^{M-2}なので(モジュラ逆数),これでやっと答えが出る。最後の方はこういう問題では当然なのかな。

解き方2

たぶん頂点ごとに見る方がはるかに見通しが立ちやすい(し方針も立てやすい)と思う。解説はいろんなサイトがしているからここには書かないけれど(じゃあeditorial丸写しもするな)。単なる木の再帰を全方位DPっていうみたい。言葉尻が強い。