AtCoder Beginner Contest 154 E - Almost Everywhere Zero

atcoder.jp

桁DPの典型的な問題。非常にNの大きい問題で、N以下で条件を満たすものの数を数えよ、という場合はだいたい桁DPでやるのがよい。

DPは上位の桁(文字列でIndex 0の文字)から見て、状態として「ある桁まで見たとき、0以外の数がK個」「ある桁まで見たとき、それまでの数字がすべてNに一致しているか否か」という状態を持って桁DPをすればよい。計算量はO(Nの桁数)

今回は既に桁に現れた0以外の数という状態が特殊だが、桁DPの場合上位の桁から見る場合は与えられたNと「ある桁まで一致しているか、それともN以下の数の桁が一回でも現れたか」という2個の状態を持って判断するのが鉄則。

感想：桁DP苦手だなと思ってたけどスラスラ行けたので意外とものにできてそう。