C - Folia

問題

atcoder.jp

考えたこと

おそらく貪欲で構築していくんだろうと思ったが、深さ であり、何も考えずに葉の数を最大化はできない。
また、根から適当に貪欲していくのも良くない。なぜなら、増やしすぎると、それ以降の葉の数と辻褄が合わなくなる。

解法

貪欲法。ただし、増やせる葉の数は上界が存在する。
深さにおける葉と、葉ではない要素を管理しながら解いていく。
厳密な証明は次のPDFに譲るとして、自分が必要だと感じた部分だけ書く。
PDF : https://img.atcoder.jp/nomura2020/editorial.pdf

深さにおける葉の数を, 葉ではない頂点の数を とする。

①　が成り立つ。
等号が成立するとき、すべてのが2つの子を持つ。

② 　が成り立つ

これはまぁ当たり前っちゃ当たり前で、これ以降の頂点の総数は増えることはあっても減ることはない。
　に対応する二分木の構築は不可能である。

ということで、頂点数は①と②でうまく抑えられる。そして、できるだけ大きい方の頂点数を決めて採用して行けば良い。
本当にこれに対応する二分木があるかどうかはPDFに証明がある。この証明まで思いつけるかというと……できません。

提出

#include <vector>
#include <string>
#include <iostream>
#include <numeric>
#include <functional>
using namespace std;

using Int = long long ;

int main(){
    
    Int N; cin >> N;
    vector<Int>v(N + 1);
    for(auto& e : v) cin >> e;
    
    if(N == 0){
        cout << (v.front() == 1 ? 1 : -1) << endl;
        return 0;
    }
    
    if(v.front() != 0) return cout << -1  << endl, 0;
    
    Int sum = accumulate(v.begin(),v.end(),0LL);
    Int ans = 0;
    Int nleaf = 1;
    
    for(int i = 0; i < v.size(); ++i){

        if( v[i] > nleaf ) {
            return cout << -1 << endl, 0;
        }
        
        nleaf -= v[i];
        ans += nleaf + v[i];
        sum -= v[i];
        nleaf = min(2 * nleaf, sum);
    }
    cout << ans << endl;
}