ABC149の解説です。
全完して暇なので解説を書きます。
実はこれがQiitaへの最初の投稿です。
最初の方の解説は適当にやるので、ABCのBまでが解けない感じの人はそっと閉じて勉強したほうがよさそうです。
A問題
文字列を入力して逆順に出力するだけです。
特に言うことはありません。
B問題
次の3つの場合分けをします。
・高橋君のクッキーだけを食べる場合
・両方のクッキーを食べ、クッキーが足りる場合
・両方のクッキーを食べ、かつクッキーが足りない場合
それぞれ
・$K<=A$
・$A<K$ かつ $K<=A+B$
・$A+B<K$
が対応し、出力する答えは
・$A-K,B$
・$0,A+B-K$
・$0,0$
となります。コーナーケースなどはなさそうです。
C問題
・$X$ からどんどん数を増やしていき、はじめて素数になったらそれを出力してプログラムを終了すればよいです。
素数かどうかは、$2$ から $\sqrt N$ までで数を割り、ひとつも割り切れないかどうかで判定できます。
大きい数では、他の素数判定法のほうが高速な場合が多いですが、この問題の制約ではこれで十分です。
実際に素数定理などを使って近似すると、$X=100000$ 近辺でも、およそ $1 / 11$ 程度の確率で素数が含まれると考えられるので、この方法で十分高速だとわかります。
$100003$ は実際に素数らしいです。（公式解説より）
D問題
この問題は、前から貪欲法を使っていくことで解くことができます。以下に示します。
じゃんけんの回数は$0$-indexedで数えるものとします。
$R,S,P$ の値は正なので、勝ち数を最大化します。
$i$ 番目のじゃんけんで勝てるとき、勝つべきかどうかを考えます。（勝てない時は好きな手を選べるので、$i+K$ 番目に影響を及ぼさないような手の出し方ができます）
$i+K$ 番目の手を出すとき、 $i$ 番目に筐体が出してくる手と $i+K$ 番目に筐体が出してくる手が同じで、かつ $i$ 番目に筐体に勝っていれば $i+K$ 番目で勝つことはできず、逆にそうでなければ必ず勝つことができます。
$i$ 番目の筐体の手が $i+K$ 番目の筐体の手と異なる場合、$i+K$ 番目では必ず勝つことができるので、 $i$ 番目でも勝っておくのが明らかに最善です。
そうでない場合について考えます。
まず、$i$ 番目も $i+K$ 番目も勝たないのは、最善ではないことは明らかで、どちらかを選んで勝つことになります。
$i+K$ 番目のじゃんけんが終わった後を考えると、それぞれの選び方で勝数は変わりません。
しかし、$i+K$ 番目を選んだ場合は $i+2K$ 番目のじゃんけんに制約がかかり、 $i$ 番目を選んだ場合はかからないので、 $i$ 番目を選ぶのが最善と言えます。
以上より、この問題が貪欲法によって、 $O(N)$ で解けることが示されました。
E問題
高橋君が行える握手の組み合わせをすべて列挙し、その中から、大きい $M$ 個を選んで和をとるのが最善ですが、愚直にこれを行うと計算量は $O(N^2)$ となり、間に合いません。
高橋君がする握手のうち、寄与する幸福度の最小値を $K$ とします。このとき、幸福度が $K$ より大きく上がるすべての握手を高橋君は必ずすることになります。この個数を $H$ とします。これが $M$ を下回れば高橋君はその握手をすべてし尽すことが可能で、そうでなければ不可能です。
$H$ は $K$ から一意に定まり、$K$ が増加すれば $H$ は必ず減少します。
よって、 $H$ が $M$ 以上とならない $K$ の最小値を二分探索で求めることができ、これを選ぶのが最適です。
$H$ を計算するのは、 それぞれの $A_i$ について $A_i+A_j\leqq K$ を満たすjの個数を数えればいいので、事前に $A$ をソートしておけば二分探索で求められます。
$K$ が求まれば、累積和と二分探索などを用いて上昇する幸福度が $K$ 以上になる組み合わせの幸福度の総和を $O(N\ log\ N)$ で求められます。
前処理のソートに $O(N\ log\ N)$、$H$ を求めるのに $O(N\ log\ N)$、$K$ の二分探索に $O(log\ max(A))$ かかるので、合計 $O(N\ log\ N\ log\ max(A))$ でこの問題が解けました。
別解として、多項式乗算を使ったものもあります。
$A_i=m$ となる $i$ の数を $m$ 次の項の係数とした多項式を $2$ 乗し、次数が高いものから見て、係数の和が $M$ と等しくなるまで次数と係数の積を加算すればよいです。
多項式の積は、Karatsuba法では $O(N^{1.58})$, FFTでは $O(N\ log\ N)$ で計算できるので、余裕を持って間に合います。
どちらの解法でも、握手をするかどうかの境界が上昇する幸福度の境界と一致するとは限らない（同じ幸福度でも、する握手としない握手がある場合がある）ので、端の処理に気を付けてください。
F問題
各頂点についてだけ「穴あき度」に加算される量の期待値を求めてすべて足せば、全体の穴あき度の総和が求まります。
グラフが木であることを考えると、黒く塗られた頂点の組が存在するとき、その間のパスは1本しか存在せず、そのパスは黒く塗られた頂点の全域木にかならず含まれるので、パス上の頂点はかならず全域木に含まれることが分かります。
よって、頂点 $u$ が穴あき度に加算されないのは、黒く塗られた頂点どうしのパス上に決して $u$ がないことと同値であり、 逆に $u$ が穴あき度に加算される確率は、 $1$ から「黒く塗られた頂点どうしのいかなるパスにも $u$ が含まれない確率」を引いて $2$ で割ったものと考えられます。
「$u$ が黒く塗られた頂点どうしのいかなるパスにも含まれない」のは、さらに以下へ言い換えられます。
・ $u$ を端点とする辺のうち、 $u$ から見てその先に黒い頂点が存在するものが $1$ 個以下である。
このような辺が $0$ 本の場合、 $u$ 以外の頂点はすべて白く塗られるので、そのような確率は $\frac{1}{2^{n-1}}$です。
$1$ 本の場合、$u$ を端点にもつ各辺について、その先にある頂点の個数を $x$ とすると、$(1-\frac{1}{2^x})\frac{1}{2^{n-x-1}}=\frac{2^x-1}{2^{n-1}}$ の総和として求まります。
各辺の先にある頂点の数は、任意の点を始点としてDFSをするなどして求められるので、この問題は $O(N)$ で解けました。
おわりに
Unratedが無限に悲しいです
このあとのこどふぉで爆上げしていこうと思います（フラグ）
※2019/12/30 10:54追記 フラグ回収しました
これからもABC全完したら適当に解説記事を書くのでよろしくお願いします！