TopCoder SRM 363 Div1 Meduim MirrorNumber

問題

ある数字がmirror numberであるとは、
その数字を鏡に映しても意味のある数字になっていることをいう。
数字を鏡に映すと、1は1のまま2は5に、5は2に、8は8に、0は0になり、
数字の順序が逆になる。
反転前または反転後にleading zeroがあることは許されない。

A以上B以下の数のうち、mirror numberである数の個数を求めよ。

制約条件

A,B≦10^18

方針

動的計画法による。
n以下のmirror numberの数を高速に数えられればよい。
m桁ちょうどのmirror numberの数を数えることを考える。

dp[i][s][t]を、
i桁目まで数字を頭から決めたとき、
s=0なら数字がnよりも小さくなっておらず、s=1なら数字がnよりも小さくなっている
t=0なら数字の末尾の部分がnよりも小さく、
t=1なら数字の末尾の部分がちょうどnの末尾に一致し、
t=2なら数字の末尾の部分がnよりも大きくなっているような状態の場合の数とする。

これを更新していくDPをすればよい。
半分の桁を決め終えた後、s=1であるか、t<2であれば、それはn以下のmirror numberとなっているので、答えにその数を足す。

ソースコード

int mirror(int n){
  if(n==2||n==5)return 7-n;
  return n;
}
int m,d[20],dp[20][2][3];
ll calc2(int m){
  memset(dp,0,sizeof(dp));
  dp[0][0][1]=1;
  ll res=0;
  rep(i,(m+1)/2)rep(s,2)rep(t,3){
    rep(j,10)if(j==0||j==1||j==2||j==5||j==8){
      int ns=s||j<d[i], nt=mirror(j)!=d[m-i-1]?mirror(j)<d[m-i-1]?0:2:t;
      if(!ns&&j>d[i])continue;
      if(i==0&&j==0||i*2+1==m&&(j==2||j==5))continue;
      if((i+1)*2<m)dp[i+1][ns][nt]+=dp[i][s][t];
      else if(ns||nt<2)res+=dp[i][s][t];
    }
  }
  return res;
}
ll calc(ll n){
  if(n<0)return 0;
  for(m=0;n;n/=10)d[m++]=n%10;
  reverse(d,d+m);
  
  ll res=1;
  for(int i=m;i>0;i--){
    res+=calc2(i);
    rep(j,m)d[j]=10;
  }
  return res;
}
class MirrorNumber {
  public:
  int count(string A, string B) {
    return calc(atoll(B.c_str()))-calc(atoll(A.c_str())-1);
  }
};