エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
分割数のDPをO(Nsqrt(N))でやる - DEGwerのブログ
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
分割数のDPをO(Nsqrt(N))でやる - DEGwerのブログ
Petrozavodsk campの北朝鮮セットであった問題で知見を得たので書き記しておきます。 問題 分割数の N ... Petrozavodsk campの北朝鮮セットであった問題で知見を得たので書き記しておきます。 問題 分割数の N 番目を求めよ。 解法 まず、DP[N][K]: K個の和でNを作る場合の数 とする。 1を使う場合と使わない場合に分けると、DP[N][K]=DP[N-1][K-1]+DP[N-K][K] がわかる。このままやると O(N^2) となる。 B=floor(sqrt(N))として、K < B に対して、この DP を愚直に計算する。 K>=B に対しては、x[s][t]: B<=xに対する DP[s-tx][x] たちの和 とする。下の図の青線や緑線一本一本の和を、始点と傾きを変えながら全部求めると思えばよい。x[N][0] がわかれば OK 。 このとき、t (すなわち傾き) は、sqrt(N) までしか考えなくてよい。これは、傾きがそれ以上大きいとき、直線は前計算した赤い