TCO 2016 Round 1C Hard. PrimeStrings

問題概要

整数 A を二進数で表した時、長さ L=max(1, |A|-k) である部分列のうち最も大きいものを f(A) とする。 f(A)≦y であるような x 以下の正の整数 A はいくつあるか。

解法

L<|y| のときは確実に y 未満になるし、L>|y| のときは確実に y を超える。問題になるのは L=|y| のときである。

二進表記された整数 x から取り出せる長さ L の辞書順最大の文字列は次の方法で見つけることができる。

  1. x[i]==1 なら使う。
  2. x[i]==0 なら、使わないと長さが L に達しないことが確定しているときのみ使う。

これを利用して次のような DP を行う。

  • dp[ i 桁目まで見た ][ j 文字を部分列として採用した ][ x 未満であることが確定 ][ y 未満であることが確定 ] := この状態に至るパターン数

TCO 2016 Round 1C Hard. PrimeStrings

なかなか考えがまとまらず苦戦した。