nomura2020C

C - Folia

• 
• 考えたこと
  • 可能かどうかだけじゃなくて頂点最大化するのが大変だな…
  • どういう時に頂点数が増えるのか？
  • なるべくスカスカにした方がよさそう？
  • あれ？同じだな？
    • 
  • 一意に決まるのでは…
  • まず1からスタートしてA0引いて2倍したのが次の高さの頂点数で、そこから葉になるA1を引いて、2倍して、次の高さの頂点になる
  • これが最後にちょうど0になったら実現可能
  • 頂点数は上記で求まるので一意
• 公式解説
  • あ、なるほど「子の個数は2以下」だから子が1個の頂点があってもいいのか。
    • 問題条件勘違い。改めて考える。
• 改めて考えたこと

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

  • 

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

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

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

    • 子の頂点がないと葉になっちゃうから
    • 子の頂点をなるべく束ねずにぶら下げれば子の数の総和まで頂点を作れる

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

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