概要

“最下層を除くどのボールも自身の直下にある2つのボールよりも小さい数字となる”という制約は二分ヒープに類似しています.

この問題でも, (0, 0), (1, 0), (1, 1), (2, 0)…という順番にヒープへの追加と同じ操作を行えばACすることができます.

なお追加する際は, 最上層と両端を除く全てのボールが2つの親ボールを持つと考え, 入れ替えは制約を満たすようにより大きな数字を持つ親ボールと行う必要があります.

余談

なお, この問題のようなヒープのことをBeapと呼ぶそうです.