[競プロ]未満フラグのDPを知る

はじめに

精進してますか？僕はしてます。
動的計画法はとても便利です。目的重視の考え方なので、データ構造さえ知ってしまえば、どんな問題にも応用できそうな気がします。

そんなつもりでしたが、今回とある問題にかなり詰まったので、未満フラグの真骨頂を伝授できればと思います。

N以下の非負正数でpopcountがKの総和を求めよ

これはABC406_Eの問題です。
一瞬「全bit探索で解けるか...？」と頭に過ぎったのですが、陳腐なforループではN以下という制限を守るような探索が出来ません。

そこで、このような考えを持つことが重要です。

1. Nを2進数に分解する
2. 各'1'に対して、それ未満でpopcountが特定の数値の総和を調べる
3. '1'の探索レベルを落とすたびに使えるpopcountの数を落としつつ、自分未満の数値の総和を調べる

これをすれば、論理的にはみ出ることも、総和が重複することもありません。考えついた人は天才だ...!

先ほど出た要件に基づくと、2^i未満の非負整数でpopcountがjの総和を保持する二次元配列が欲しいです。(そして、上記条件で数値の数を保持する別の二次元配列があれば、計算し放題です)

こういった要領で、未満フラグのDPは有効活用されるんですね〜

まとめ

精進せずに記事書いてる時間が途中で惜しくなったので、早々に切り上げました。(ｽﾐﾏｾﾝ)
このような美しい実装法を知ると、嫌でも頭に出てきそうですよね。レートを上げるという名目では非論理的ではありますが、あくまで競プロはゲームなので、それもまた一興と考えてます(灰er並感)


お疲れ様でした。