M-SOLUTIONS プロコンオープン 2020 E - M's Solution (500)
最初の考察
人口の多い方から集落を通るようにして線を引くのを$ 2^nパターン試せば良さそう
それぞれのパターンで各本数の通りを引いたときに全集落で距離を計算する
$ O(2^n n^2)
例4が上に反しているので駄目
次の考察
それぞれの集落に、線を引かない、南北に引く、東西に引くの3パターンを持たせて全パターン試す
上と同じようにやると$ O(3^n n^2)で駄目
解説の方法
東西と南北でそれぞれ全パターンについてその方向での各集落の最短距離が$ O(2^n n^2)で求められる
これを用いると、各パターンでのある集落の最短距離が東西と南北の短い方という$ O(1)で求まる
全体で$ O(3^n n)にできる
全体で$ O(2^n n^2 + 3^n n)となり間に合う