nomura2020C

https://gyazo.com/7f80f1a1ef30beceaa1abc2ff094f93c

考えたこと

可能かどうかだけじゃなくて頂点最大化するのが大変だな…

どういう時に頂点数が増えるのか？

なるべくスカスカにした方がよさそう？

あれ？同じだな？

https://gyazo.com/0c74cabd6084255d9b2a3449d48767c6

一意に決まるのでは…

まず1からスタートしてA0引いて2倍したのが次の高さの頂点数で、そこから葉になるA1を引いて、2倍して、次の高さの頂点になる

これが最後にちょうど0になったら実現可能

頂点数は上記で求まるので一意

公式解説

あ、なるほど「子の個数は2以下」だから子が1個の頂点があってもいいのか。

問題条件勘違い。改めて考える。

改めて考えたこと

つまりこういう時に差が出る

https://gyazo.com/ba00c9de4d2861b76f5a1520806c4abe

上の高さの頂点をxとすると、今の高さには最大2x個の頂点を置ける

その内Ai個は葉として用途が決められる

2x-Ai個全部頂点にすることはできない

子の頂点がないと葉になっちゃうから

子の頂点をなるべく束ねずにぶら下げれば子の数の総和まで頂点を作れる

2つの値の小さい方でやる

公式解説

上記の方法でなるべくたくさん頂点を置いていくのが最適であることを証明している