[Boot camp for Beginners] D - Caracal vs Monster [Rust]

概要

AtCoder Problems: Boot camp for Beginners をRustで解いてみる

• 今回の問題：D - Caracal vs Monster
• 書いたコード：提出 #47380360 - AtCoder Beginner Contest 153

学んだことmemo

• 2分木ができていく問題な気がする

4 ---- 2
  |    |--- 1
  |    `--- 1
  `--- 2
       |--- 1
       `--- 1

• すべて 1 になった場合は最終段とみなして、1の数を数えれば良さそう
• それ以外は h/2 を root とした2分木とみなして再帰的に解けそう
• 対照な木しかできないので、途中の計算は全部やらずに2倍すれば良い部分があることに気づけば深さが深くなっても計算量を抑えられることに気が付けば問題なかった