B - Minimum Sum 解説 実装 B - Minimum Sum 問題へのリンク 解説 区間がたくさん与えられるので、その中のある値の和を求めよという問題は多くありますが、基本的に区間をすべて列挙して解くことはできません。今回も例によってそのパターンで、ある値が、…

問題へのリンク 解説 実装 公式解説 解説 公式解説とは異なる方針でACしたので記録を残しておきます。 まず、いわゆる主客転倒（寄与ゲー）と呼ばれる問題だと捉えます。 今回求めたいのは、の並びのうち、表のコインの数の期待値ですが、 これを期待値では…

問題へのリンク 解説 まず、「閉路のない無向グラフにおいて、連結成分数 = 頂点数 - 辺数」が成り立つことを使います。 すると、問題は以下のように言い換えられます。 頂点数は の計算でで求められます。は区間の長さです。 辺数に関しては、について考え…

解説 問題の言い換え 面積Sの計算 登場回数Cの数え上げ ~ xとyは独立 ~ シグマの計算 実装 問題へのリンク 解説 問題の言い換え 数え上げの典型として、「問われている対象を別のものの数え上げで考える」という方針があります。今回もその例に漏れず、出て…