解法 まず、各区間についてネコババした時の期待値を求める(O(n))。 （監査に引っかかってもネコババ分は手に入るのに注意。）次に、各人どの区間ネコババするかを考える。 愚直にやるとO(m*n*n)だが、セグメントツリーを使うことでO(2*n + m*logn)になる。…

なぜこどふぉか Topcoder Topcoderは全探索とDPしか出ないという風説はあまりにも有名です。それに比べ、こどふぉはいろいろな問題(グラフや幾何、文字列など？)があるので、解いていて楽しいです。また、TopCoderはアリーナを起動するのが面倒ですし、どの…