B - Poly-Polygons

2 secs 1024 MB
Yourein's icon Yourein

Editorial

一つの多角形を連結するときに必要な辺の数をコストとして考えてみると、まだ何も連結されていない状態で1つ置くときはnnだけコストがかかります。しかし、それ以降はちょうどn1n-1だけコストがかかることがわかります。

したがって、求める答えはn+(n1)(k1)n+(n-1)(k-1)です。(ところで、n=(n1)+1n = (n-1)+1ですね?)

実装例(Ruby)

実装例(Python)