競技プログラミングの桁DP問題集

桁DPです。
だいたい では求めることができないものについて、与えられた条件をみたす数をDPで求めます。とか
再帰派とDP派(桁"DP"なのに)の二つがあるようですが僕は単純な問題以外は再帰の方がいいと思います(簡単なものはDPでよい(楽なので))
基本的には、
:= (上から)i桁まで見たときに、indexの状態を満たす総数
として求めることが多いような気がします。これで解けなかったのは以下の3の問題だけです。
クエリに高速に答えるためには配列の埋まり方を考慮する必要があります。(問題6.参照)
埋まり方を理解すると計算がNに依存しない部分のみになります。(とてもうれしい)

以下僕の解いていった順です。3以外は全て再帰で解きました。

1. D: 禁止された数字 - AtCoder Beginner Contest 007 | AtCoder

2. E: 数 - Typical DP Contest | AtCoder

3. D: 壊れた電卓 - CODE FESTIVAL 2014 予選A | AtCoder これ再帰で書けなくて悲しい

4. D: 1 - AtCoder Beginner Contest 029 | AtCoder

5. ジグザグ数 | Aizu Online Judge

6. Codeforces Manthan, Codefest 17 E Salazar Slytherin's Locket 理解するのに非常に良い?

7. No.189 SUPER HAPPY DAY - yukicoder

8. No.220 世界のなんとか2 - yukicoder

9. No.260 世界のなんとか3 - yukicoder

10. No.315 世界のなんとか3.5 - yukicoder ちょっと好き

11. No.319 happy b1rthday 2 me - yukicoder

12. No.372 It's automatic - yukicoder

13. No.362 門松ナンバー - yukicoder

14. F: レシート - 東京工業大学プログラミングコンテスト2015 | AtCoder

15. H: Bit Count - 京都大学プログラミングコンテスト2015 | AtCoder

16.

17.

18.

19.

20.

まだ
Investigation - LightOJ 1068 - Virtual Judge
LIDS | Toph
Problem - D - Codeforces
Palindromic Numbers - LightOJ 1205 - Virtual Judge
Contest Page | CodeChef
Problem - G - Codeforces
SPOJ.com - Problem TAP2012C
Digit Count - LightOJ 1122 - Virtual Judge
Contest Page | CodeChef
Dev Skill - Sanvi and Magical Numbers
SPOJ.com - Problem CPCRC1C
SPOJ.com - Problem PR003004
SPOJ.com - Problem RAONE
SPOJ.com - Problem LUCIFER
SPOJ.com - Problem NUMTSN
Contest Page | CodeChef