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