No.362

$A(n)$ を $n$ 以下の $n$ と同じ桁数の門松ナンバーの数とする.

これは桁DPを使って, dp[何桁目まで見たか][最大値か][下から2つめの桁][下から1つ目の桁] = 門松ナンバーの数 という数を更新していけばいい.

dp[3][j][k][l] は最初に自力で計算しておけばややこしそうな場合分けは必要ない.

$B(n)$ を $n$ 以下の門松ナンバーの数とすると, $B(n) = A(999) + A(9999) + \dots + A(n)$ となる. $A(999) + A(9999) + \dots$ の部分はあらかじめ計算しておく.

$B(n)$ が計算できるならば, あとは二分探索である.