2017-09-17から1日間の記事一覧

ARC083 E: Bichrome Tree

E - Bichrome Tree 解き方 ある頂点iの部分木について、黒白それぞれの重みの和を、b_i, w_iとして、それを更新していく 黒白は入れ替えても問題ないので、違う色か同じ色かだけ考えれば良い 頂点iがleafの場合、色はどちらでもよく、重みはx_iになる 頂点i…

ARC083 D: Restoring Road Network

D - Restoring Road Network 解き方 これまでに追加した辺のコストの合計と、その辺による各都市間の最短距離(d[i][j])を保持、更新する 距離が小さい方から順に考えていく。 町i, j間の最短距離がcの時、 もし、d[i][j] == cならば、もう辺を追加する必要は…

ARC083 C: Sugar Water

C - Sugar Water 解き方 A, B, C, Dそれぞれの操作を何回するか、全探索 A, Bについては、100A <= F <= 30 * 100より、たかだか30回 C, Dについては、最大でF/2g溶ける(E=100の時)ので、たかだか1500回 合計で[tex:O(109)]なので、ダメでは?という気もす…

活動記録(2017/9/11-2017/9/17)

競技プログラミング ARC083 結果 97th, 1551->1679 (Perf: 2363) Cを3回WAしてダメかと思ったが、うまいことEまで解けた。 AOJ0189, AOJ2249, AOJ2200 蟻本練習問題。warshall floydだったりdijkstraだったり、最短経路問題の基本系 その他 金沢行ってきた W…