競技プログラミングにおける桁DP問題まとめ

桁DP

• dp[桁数][条件][上限ギリギリか]
• 下から桁DPというのもある（繰り上がり的なのが発生する時はこっちで考えるべき？）
• 参考1 参考2

問題

• 普通の桁DP
  • ABC007 D. 禁止された数字
  • Typical DP Contest E. 数
  • EDPC Digit Sum 解説
  • ABC029 D. 1
  • yukicoder No.741 AscNumber(Easy) 解説
  • ECR50 Classy Numbers 解説
  • ABC117 XXOR 解説
  • CODE FESTIVAL 2014 予選A D. 壊れた電卓
  • RUPC2018 Day1 ごちうさ数 解説
  • ABC129 Sum Equals Xor 解説
  • yukicoderの桁DPタグ
  • JOI ジグザグ数 解説
  • CF Salazar Slytherin's Locket
  • 東京工業大学プログラミングコンテスト2015 F. レシート
  • 京都大学プログラミングコンテスト2015 H. Bit Count
  • yukicoder No.685 Logical Operations 解説 （2進数桁DP）
  • CC Awkward Pairs 解説
  • (難) CodeChef Chef and Digits
  • （難）CF New Year and Original Order 解説
  • CF458 Travelling Salesman and Special Numbers 解説
  • HE Holi and Friendship（TL厳しめ）
  • yukicoder No.737 PopCount 解説
• 下から桁DP
  • yukicoder No.636 硬貨の枚数2 解説
  • ABC155 Payment 解説

以下、短い解説

解説

ABC007 D. 禁止された数字

http://abc007.contest.atcoder.jp/submissions/1240777
dp[桁数][4か9が既に含まれているか][上限ギリギリか]

Typical DP Contest E. 数

http://tdpc.contest.atcoder.jp/submissions/1240757
dp[桁数][総和modD][上限ギリギリか]

ABC029 D. 1

http://abc029.contest.atcoder.jp/submissions/1240977
dp[桁数][これまでの1の数][上限ギリギリか]

CODE FESTIVAL 2014 予選A D. 壊れた電卓

http://code-festival-2014-quala.contest.atcoder.jp/submissions/1240951
dp[桁数][これまで使った数字のbit][最大か最小か]

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

http://ttpc2015.contest.atcoder.jp/submissions/1241865
dp[桁数][桁上りの有無] := 数が合っている桁数

京都大学プログラミングコンテスト2015 H. Bit Count

dp[2進数での桁数][ビットカウントの差][桁上りの有無] := Xの最小値
解けなかった...
http://mayokoex.hatenablog.com/entry/2015/10/25/193550
https://kimiyuki.net/blog/2015/10/24/kupc-2015-h/

CodeChef Chef and Digits

包除原理も使う