読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

AtCoder Grand Contest 005: C. Tree Restoring

http://agc005.contest.atcoder.jp/tasks/agc005_c

解法

まず直径のパスを先に作ろう。直径は a[i] の最大値。

たとえば直径が 5 だったら先に次のパスを構築する。

f:id:pekempey:20161002034853p:plain

この段階で作れないなら Impossible。

もし a[i]≦3 が余ってたら、どうやっても構成不可能。一方で、a[i]>3は大量に余っていても問題にならない。

例えば 4 が余ってたら、次のように繋いでおけばいい。

f:id:pekempey:20161002035158p:plain

もう一個 4 が余ってたら、次のように繋いでおけばいい。

f:id:pekempey:20161002035253p:plain

というように、a[i]>3はどうにでもなる。

CFのBあたりに構築ゲーとして出てきそうな問題。