SRM300 div1 medium
calc(n)をn以下のjumpyNumを求める関数とする
答えはcalc(high)-calc(low-1)
ーーーーーーーーーーーーcalc(n)の説明ーーーーーーーーーーーー
数字を文字列にして考える
n=123456789のとき
m=12345....なら、mはnにpos=4(0-indexed)までマッチしているということにする
DP[match][pos][digit]を数を左から右に考えていったとき、
場所posがdigit(0-9)なら何通りのjumpyNumが存在するかとしてDPする。
(matchはpos=0からpos=pos-1までがマッチしているかどうかを格納する)
#include <string> #include <sstream> using namespace std; int ABS(int n) { return (n<0)?-n:n; } class JumpyNum { public: int calc(int input) { stringstream ss; ss<<input; string num=ss.str(); int n=num.size(); int DP[2][15][10]; for(int pos=n-1;0<=pos;pos--) for(int digit=0;digit<10;digit++) for(int match=0;match<2;match++) if(pos==n-1) { if(match) DP[match][pos][digit]=(digit<=num[pos]-'0')?1:0; else DP[match][pos][digit]=1; } else { if(match) { DP[match][pos][digit]=0; if(digit<num[pos]-'0') for(int nd=0;nd<10;nd++) { if(2<=ABS(digit-nd)) DP[match][pos][digit]+=DP[0][pos+1][nd]; } else if(digit==num[pos]-'0') for(int nd=0;nd<10;nd++) { if(2<=ABS(digit-nd)) DP[match][pos][digit]+=DP[1][pos+1][nd]; } else ; } else { DP[match][pos][digit]=0; for(int nd=0;nd<10;nd++) if(2<=ABS(digit-nd)) DP[match][pos][digit]+=DP[0][pos+1][nd]; } } int ans=0; for(int len=1;len<=n;len++) { if(len==n) { for(int first=1;first<num[0]-'0';first++) ans+=DP[0][0][first]; if(0<num[0]-'0') ans+=DP[1][0][num[0]-'0']; } else { for(int first=1;first<10;first++) ans+=DP[0][n-len][first]; } } return ans; } int howMany(int low, int high) { return calc(high)-calc(low-1); } };