人権なし

競プロで解いた問題や開発の進捗などの記録です

diverta 2019 Programming Contest 2:B - Picking Up

問題

atcoder.jp

解法

まず,N^2 個(正確にはもっと少ない)ある (p, q) の組を全列挙する.その後,各 (p, q) の組について必要となるコストの回数を計算する.ある頂点 v から移動量が (p, q) または (-p, -q) であるような頂点 u があれば,v と u を同じ集合に属させる.これを繰り返すことで,1 ~ N の数字はいくつかの集合に分かれることになる.この集合の個数が必要なコストの回数になる.集合の管理には Union-Find 木を使えばよく,集合の数は各部分木の一番上の親の頂点の index の種類数と同じになるので,これも求まる.O(N^4).

解答

atcoder.jp

f:id:babcs2035:20190615231652p:plain