Codeforces 9D
良く見たらDiv2の問題でしたよ、と。
問題
二分探索木のうち、ノード数Nで深さK以上のものの個数を答えよ、という問題。
解答例
DPするだけ。ノードがA個あるとき、左右に適当に振り分ける方法はA通りで、それぞれの部分木の深さは高々ノード数となるので、左右の木の深さの深い方+1が今の自分の深さになる。O(A^3)で計算できるので、後はAを0からNまで全部計算する。最終的にはO(N^4)ということになる。コードも四重ループになるので極めて自然。
良く見たらDiv2の問題でしたよ、と。
二分探索木のうち、ノード数Nで深さK以上のものの個数を答えよ、という問題。
DPするだけ。ノードがA個あるとき、左右に適当に振り分ける方法はA通りで、それぞれの部分木の深さは高々ノード数となるので、左右の木の深さの深い方+1が今の自分の深さになる。O(A^3)で計算できるので、後はAを0からNまで全部計算する。最終的にはO(N^4)ということになる。コードも四重ループになるので極めて自然。