NOMURA プログラミングコンテスト 2020 C問題 Folia

問題のリンク

• 深さdの頂点数の最大値は、「深さdより下の葉の個数の総和」と「深さd-1の頂点のうち、葉でないもの」のうち小さい方になる。
• なので、深さ0から頂点数が最大になるように貪欲に頂点数を確定させていけばいい。
  
  
  したがって、以下のような実装を行えばいい。
  
  
  まず、根の頂点数は1より A_0 >= 2 は明らかに二分木を作れないので、-1を出力して終了。
  頂点数を格納しておく長さN+1の配列Cを用意する。i=1...Nについて、以下を繰り返す。

1. C_i = min((C_(i-1) - A_(i-1)) * 2 , Σk=i~N A_k) として頂点数を確定する。
2. ただし、i != NのときC_i - A_i <= 0であるなら、子がいないということになるので-1を出力して終了。
   AC code