ferinの競プロ帳

競プロについてのメモ

2018-11-02から1日間の記事一覧

Codeforces Round #518 (Div. 1) B. Multihedgehog

問題ページ 考えたこと 各頂点を根として判定をするO(N^2)はできそう 全方位木DPかなあとか考える 冷静になると根になりそうなのはグラフの中心しかない 木の直径はdouble-sweepで求められるので直径を構成するパスの端点から距離が等しい頂点が中心 木の中…

2018-2019 ICPC, NEERC, Southern Subregional Contest C. Cloud Computing

問題ページ 解法 i日目に使用するplanはcoreの値段が安い方から順にK個取っていく貪欲で決定できる。 i日目に存在しているplanについて2つのBITを用いて管理する。cnt[i]=値段がiで使えるcoreの個数、sum[i]=値段がiのcoreを使うのにかかる値段の和とする。 …