桁DP
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
*桁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を用いない整数の数"と"1桁の整数のうち5が含まれていない整数の数"の和に等しい」です~
(「**」の形として「00」「01」「02」「03」「04」「06」「07」「08」「09」が合法で、この数は"1桁の整数のうち5が含まれていない整数の数"に等しい)~
つまり、「**」として合法な値は72+9通りです~
したがって3桁の整数のうち5を用いない整数は8×(72+9)=648個となります~
よってN≦1000のときの5を用いない整数の数は~
648+72+9=729個となります~
**なんか忘れてない? [#rac4013f]
よく気が付きましたね!~
そう、N≦1000なので、N=1000の時も考えないといけないですね。~
この手の問題でありがちなミスです。~
最後に1を足して730個。これで完了です~
終了行:
*桁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を用いない整数の数"と"1桁の整数のうち5が含まれていない整数の数"の和に等しい」です~
(「**」の形として「00」「01」「02」「03」「04」「06」「07」「08」「09」が合法で、この数は"1桁の整数のうち5が含まれていない整数の数"に等しい)~
つまり、「**」として合法な値は72+9通りです~
したがって3桁の整数のうち5を用いない整数は8×(72+9)=648個となります~
よってN≦1000のときの5を用いない整数の数は~
648+72+9=729個となります~
**なんか忘れてない? [#rac4013f]
よく気が付きましたね!~
そう、N≦1000なので、N=1000の時も考えないといけないですね。~
この手の問題でありがちなミスです。~
最後に1を足して730個。これで完了です~
ページ名: