*桁DP [#f19701ea] このページは競技プログラミングに興味のある方向けに桁DPを簡単に説明するページです **桁DPって何? [#s55fbc77] 特定の条件を満たす数を探す(数え上げる)際に用いられる手法です~ 特に、使用できる(or禁止されている)数字が制限(or設定)されている場合によく用いられます~ **具体的に [#b2b37ef4] 桁DPを用いる問題の典型例は以下のような問題です~ 0からNまでの整数のうち、5を使用しない整数の数を求めよ ただし、N≦1000000とする **全探索で解けたんですけど [#f0c8c157] では、N≦10^20でやりましょう **できませんでした [#pfe1cf13] そんな時こそ桁DP **やり方は? [#xb243572] 最小桁からスタートする手法と最大桁からスタートする方法がありますが、今回は最小桁からスタートする方法でやりましょう~ このタイプの問題は~ ・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個となります~ 「**」に5が含まれていない場合の数は「"2桁の整数のうち5を用いない整数の数"と"1桁の整数のうち5が含まれていない整数の数"の和に等しい」です~ (「**」の形として「00」「01」「02」「03」「04」「06」「07」「08」「09」が合法で、この数は"1桁の整数のうち5が含まれていない整数の数"に等しい)~ つまり、「**」として合法な値は72+9通りです~ したがって3桁の整数のうち5を用いない整数は8×(72+9)=648個となります~ よってN≦1000のときの5を用いない整数の数は~ 576+72+9=657個となります~ 648+72+9=729個となります~ **なんか忘れてない? [#rac4013f] よく気が付きましたね!~ そう、N≦1000なので、N=1000の時も考えないといけないですね。~ この手の問題でありがちなミスです。~ 最後に1を足して658個。これで完了です~ 最後に1を足して730個。これで完了です~