桁DP †

このページは競技プログラミングに興味のある方向けに桁DPを簡単に説明するページです

↑

桁DPって何？ †

特定の条件を満たす数を探す(数え上げる)際に用いられる手法です
特に、使用できる(or禁止されている)数字が制限(or設定)されている場合によく用いられます

↑

具体的に †

桁DPを用いる問題の典型例は以下のような問題です

0からNまでの整数のうち、5を使用しない整数の数を求めよ
ただし、N≦1000000とする
↑

全探索で解けたんですけど †

では、N≦10^20でやりましょう

↑

できませんでした †

そんな時こそ桁DP

↑

やり方は？ †

最小桁からスタートする手法と最大桁からスタートする方法がありますが、今回は最小桁からスタートする方法でやりましょう

このタイプの問題は
・5を使わない整数を数え上げる
・5を使う整数を数え上げて、最後に全体から引く
の二通りがありますが、好きなほうを用いてもらって結構です
しかし、一般に前者のほうが数が簡単です

今回は、手計算でもできるようにN≦1000でやってみましょう

まず、1桁の数のうち5を用いない整数を数え上げます
これは自明で9通りです

次に、2桁の数のうち5を用いない整数を数え上げます
2桁の整数は「1*」「2*」「3*」「4*」「5*」「6*」「7*」「8*」「9*」
であらわされます(*は任意の値)。このうち「5*」は*の値に関係なくNGです
そして、*は5であってはいけないので*は9通りしかありません
したがって2桁の整数のうち5を用いない整数は8×9＝72個となります
このとき 8×"9" の9は「1ケタの数のうち5を用いない整数の数」です(ここがDP要素)

次に、3桁の数のうち5を用いない整数を数え上げます
3桁の整数は「1**」「2**」「3**」「4**」「5**」「6**」「7**」「8**」「9**」
であらわされます(*は任意の値)。このうち「5**」は「**」の値に関係なくNGです そして、**に5が含まれてはいけません
「**」に5が含まれていない場合の数は「2桁の整数のうち5を用いない整数の数に等しい」です
つまり、「**」として合法な値は72通りです
したがって3桁の整数のうち5を用いない整数は8×72＝576個となります

よってN≦1000のときの5を用いない整数の数は
576＋72＋9＝657個となります

↑

なんか忘れてない？ †

よく気が付きましたね！
そう、N≦1000なので、N＝1000の時も考えないといけないですね。
この手の問題でありがちなミスです。
最後に1を足して658個。これで完了です

トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS