TDPC E 数
人と関わって成し遂げる事は難しいので、少なくとも一人でできることはちゃんとやろう。えぬわいです。
続きです。
DP週間です。
考えたこと
再帰関数で、和を足していけばよい。と考えていました。結果的に、全ての数を捻出する方法がわからなかったので、詰みました。答えというか桁DPについて、調べました。
桁DPとは
さすが、けんちょんさんだぜ👏 そこにシビれるあこがれウゥ。
けんちょんさんのブログがやはりわかりやすいです。
自分にとってのこの問題の肝は、再帰関数で、いかに全ての数字を羅列するかでした。
そこで、参照ブログを参考に、数字を羅列する桁DP前の再帰関数を書いてみました。
n = input() ans = [] def rec(pos, s, a): if pos == len(n): return ans.append("".join(a)) if s: for d in range(0, 9+1): a.append(str(d)) rec(pos+1, True, a) a.pop() else: # K と一致する場合 a.append(n[pos]) rec(pos+1, False, a) a.pop() for d in range(0, int(n[pos])): a.append(str(d)) rec(pos+1, True, a) a.pop() # 左の桁から 0 桁目は自由ではない rec(0, False, []) print(sorted(ans))
こんな感じで、a を呼び出した引数の記録媒体としています。 実行すると
% python keta_dp.py 100 ['000', '001', '002', '003', '004', '005', '006', '007', '008', '009', '010', '011', '012', '013', '014', '015', '016', '017', '018', '019', '020', '021', '022', '023', '024', '025', '026', '027', '028', '029', '030', '031', '032', '033', '034', '035', '036', '037', '038', '039', '040', '041', '042', '043', '044', '045', '046', '047', '048', '049', '050', '051', '052', '053', '054', '055', '056', '057', '058', '059', '060', '061', '062', '063', '064', '065', '066', '067', '068', '069', '070', '071', '072', '073', '074', '075', '076', '077', '078', '079', '080', '081', '082', '083', '084', '085', '086', '087', '088', '089', '090', '091', '092', '093', '094', '095', '096', '097', '098', '099', '100']
というように、全て羅列できることがわかります。ただし、0 も含まれているので、注意しなければなりません。
これをベースに、問題を解いていきます。
D = int(input()) n = input() MOD = 1e9+7 """ def rec(pos, s, a): if pos == len(n): return 1 if a == 0 else 0 ans = 0 if s: for d in range(0, 9+1): ans += rec(pos+1, True, (a+d)%D) else: # K と一致する場合 ans += rec(pos+1, False, (a+int(n[pos]))%D) for d in range(0, int(n[pos])): ans += rec(pos+1, True, (a+d)%D) return ans # 左の桁から 0 桁目は自由ではない print(rec(0, False, 0)-1) """ dp = [[[0 for k in range(D)] for j in range(2)] for i in range(len(n)+1)] dp[len(n)][0][0] = 1 dp[len(n)][1][0] = 1 for i in range(len(n)-1, -1, -1): for j in range(2): for k in range(D): if j == 1: for d in range(0, 9+1): dp[i][j][k] += dp[i+1][1][(k+d)%D] dp[i][j][k] %= MOD else: dp[i][j][k] += dp[i+1][0][(k+int(n[i]))%D] for d in range(0, int(n[i])): dp[i][j][k] += dp[i+1][1][(k+d)%D] dp[i][j][k] %= MOD print(int(dp[0][0][0]-1))
TLEになりました
C++ で書き直しました。
#include <cstdio>
#include <iostream>
using namespace std;
long long int dp[10001][2][100];
long long int MOD = 1e9+7;
int main() {
string N;
int D;
scanf("%d", &D);
cin >> N;
dp[N.size()][1][0] = 1;
for (int i = N.size()-1; i >= 0; i--) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < D; k++) {
if (j == 1) {
for (int d = 0; d < 10; d++) {
(dp[i][j][k] += dp[i+1][1][(k+d)%D]) %= MOD;
}
} else {
dp[i][j][k] += dp[i+1][0][(k+N[i]-'0')%D];
for (int d = 0; d < N[i]-'0'; d++) {
(dp[i][j][k] += dp[i+1][1][(k+d)%D]) %= MOD;
}
}
}
}
}
printf("%lld\n", dp[0][0][0]-1);
}
ACしました
いよいよ python で競プロはできないかもしれないと思い始めました。
