ICPC 国内予選 2010-c ポロック予想
概要
ICPC 国内予選2010年のc問題を解きました。
概要
x(x+1)(x+2)/6で表される数があって、 それを正四面体数と呼ぶ。
正四面体数をいくつか選んでその和が入力Nになるようにするときに、最小で何個選べばいいか?
解法
- 動的計画法
- アリ本だと、p62の個数制限付き部分和問題とか似てた。
ポイント
- 先に10**6までの作り方を全て計算しておいて、queryをO(1)で処理する
- 先に正四面体数を計算しておく
先に処理することとDPなのが、重要ポイント!!
計算量
10*6200くらいの計算してて、pythonだとTLEしちゃいそう。 c++は通るから、強い
