2017-09-17から1日間の記事一覧
E - Bichrome Tree 解き方 ある頂点iの部分木について、黒白それぞれの重みの和を、b_i, w_iとして、それを更新していく 黒白は入れ替えても問題ないので、違う色か同じ色かだけ考えれば良い 頂点iがleafの場合、色はどちらでもよく、重みはx_iになる 頂点i…
D - Restoring Road Network 解き方 これまでに追加した辺のコストの合計と、その辺による各都市間の最短距離(d[i][j])を保持、更新する 距離が小さい方から順に考えていく。 町i, j間の最短距離がcの時、 もし、d[i][j] == cならば、もう辺を追加する必要は…
C - Sugar Water 解き方 A, B, C, Dそれぞれの操作を何回するか、全探索 A, Bについては、100A <= F <= 30 * 100より、たかだか30回 C, Dについては、最大でF/2g溶ける(E=100の時)ので、たかだか1500回 合計で[tex:O(109)]なので、ダメでは?という気もす…
競技プログラミング ARC083 結果 97th, 1551->1679 (Perf: 2363) Cを3回WAしてダメかと思ったが、うまいことEまで解けた。 AOJ0189, AOJ2249, AOJ2200 蟻本練習問題。warshall floydだったりdijkstraだったり、最短経路問題の基本系 その他 金沢行ってきた W…