はまやんはまやんはまやん

hamayanhamayan's blog

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

桁DP

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

解説

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

包除原理も使う