htkb-proconの日記

初心者がPythonで問題解いた記録

Educational DP Contest S - Digit Sum 桁DP

めんどくさすぎるイメージを持っていた桁DP、久しぶりに遭遇して解いたら割とソラで書けたのはいいけどTLEで、考察したらそもそも無駄に配列の次元を深くしたりしなくていいんじゃないの??と思ったので書き残してみる。

f:id:htkb:20190109210051j:plain

桁DPの状態遷移はこのように上の桁から見ていって、次の桁に取る数を考えながら1桁ずつ数字の総数をDPでまとめて数えていく。でこのときに面倒なのが境界ギリギリの数字のことで、上の例で言えば10の位が0〜2のときは1の位に0〜9を取れる(ただし問題では1以上N以下の数なので00は後で除外)んでまとめてループしちゃえばいいのだけど、10の位が3のときは1の位は0〜2までしか取れない。だからこの境界ギリギリの部分を別口に処理しなければならないわけ。

これのやり方を、巷では一般的に

dp[桁][境界ギリギリかどうか][数えたい数の種類(今回の問題ではmod D)]

みたいに取るように書いてあることが多く、次の桁が2だとすると

dp[0][境界ギリギリ][x] → dp[1][境界ギリギリじゃない][x]
dp[0][境界ギリギリ][x] → dp[1][境界ギリギリじゃない][x+1]
dp[0][境界ギリギリ][x] → dp[1][境界ギリギリ][x+2]

みたいに遷移させるようだ。自分もそのように覚えていたけど、dpの次元が増えすぎて混乱するし速度的にもメモリ的にもキツイ。何より境界の数ってのは桁ごとに1種類しかないのだから、dp[d][境界ギリギリ]は常に一つの要素だけ1で他全部0なわけで、これわざわざdpを一段深くする必要あるの??と境界の数を変数にそのまま持たせてみたら普通にうまく行った。

コメント付けたので詳しくはソースのほうを
Submission #3967551 - Educational DP Contest / DP まとめコンテスト

borderが境界ギリギリの数のそれまでの桁和 mod Dを持ってるので、+0〜(次の桁-1)まではdpのほうに合流させてborder += 次の桁して遷移させていく。めちゃくちゃ見通しが良くなって自分のように脳のメモリ控えめの人にも優しい。

わざわざdpの次元一つ掘って保持するのが桁DPの定番の持ち方になってるのは多分難しい問題ではそれが必要だからだと思うので、定番の方も覚えておくべきと思うけど、易しめの桁DP問題はこっちのが実装が軽いだけじゃなく何やってるか明確なので混乱しにくいと思う。

同じように解けた桁DP問題