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 の辞書順最大の文字列は次の方法で見つけることができる。
- x[i]==1 なら使う。
- x[i]==0 なら、使わないと長さが L に達しないことが確定しているときのみ使う。
これを利用して次のような DP を行う。
- dp[ i 桁目まで見た ][ j 文字を部分列として採用した ][ x 未満であることが確定 ][ y 未満であることが確定 ] := この状態に至るパターン数
TCO 2016 Round 1C Hard. PrimeStrings
なかなか考えがまとまらず苦戦した。