AOJ 2631 : Clique Coloring - arukukaの日記

なんとも微妙な方法で解いてしまった。

まずaを降順にソートしておく。
前2つの要素においては(a[0] - 1) + (a[1] - 1) + 1個の点が
どうしても必要になることが考えると分かる。
一番最初のサンプルのように、1つの頂点を定めてそれにぶら下がるイメージ。
3つ目はa[2] - 1よりもすでに1番目2番目で定めた頂点を
利用してぶら下がればa[2] - 2個の点で十分となる。
それ以降について、簡単にするために $a_i > 3$ のケースについて考えると
下の図のように、-3, -4としていけば最小になる。

f:id:arukuka:20170613051650p:plain

$a_i \leq 3$ について、 $a_i = 2$ のときは
1番目2番目で定めた頂点の間にリンクを張れば済む。
$a_i = 3$ のときは1番目2番目3番目で定めた頂点の間にリンクを張れば済む。
ただし、点や辺が足りなくなることもあるので、
そのときはしょうがないので点を1つ追加すると良い。