AOJ0570
■問題
2947や71946などの各桁が増加、減少、増加…およびその逆となってる数字をジグザグ数とする。
A以上B以下のMの倍数であるジグザグ数の個数を求めよ。
■解法
制限が 1 <= A <= B <= 10^500 なので整数型には入らないため文字列として扱う。
A以上B以下はx以下のジグザグ数の個数をf(x)とすると、f(B) - f(A-1) となる。A-1なのは区間にAを含むためであり、Aの文字列から1引くために多倍長っぽいことをする。
Mの倍数かの判定は、Mで割り切れるかを調べるのだが文字列なので面倒である。
整数同士の割り算の筆算のように、”前の桁の余り*10 + 今の桁 % M = 今の桁の余り”というのをすべての桁に対してやり最後の値が0なら割り切れたと判断できる。
先ほど出てきたf(x)をどうやって作るかは、上位の桁から1つずつ決定していく方法でやります。
x = 256のとき、先頭の桁には0,1,2が成り得ます。しかし、その後の桁については場合によって異なり
x = 0,1 の時はその後の桁についてはどの数値でも採用でき、
x = 2 の時は次の桁では5まで、その次の桁では6までしか使えません。
このように、すでに上限の値以下になることが確定されたかどうか、0～9の数値を自由に選べるかのフラグが必要となります。
また、ジグザグ数になっていなければいけないため、今選んだ桁をk、直前に選んだものをbとすると、
一つ前が増加していたときは、k < b
一つ前が減少していたときは、k > b
にならなくてはなりません。
これらのすべての条件を満たせるように情報を持たせてメモ化再起するには、
dp[k桁目][直前の数字][直前が増加か減少か][自由に選べるか][前の桁での余り]
とし、値をk桁目までの値を決めた時のジグザグ数の数とすることで求められます。
また、五次元配列なので多めに確保しようとするとMLEになってしまうかもしれません。
また10^500は桁数としては501なので配列の数を気をつけましょう。
■ソース
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> using namespace std; //dp[何文字目か][直前の数字][上下][自由に選べるか][余り] //上:0 下:1 int m; string s; char z[555]; int dp[501][10][3][2][500]; int solve(int n,int be,int ud,int ok,int md){ if(n == (int)s.size()){ return md?0:1; } if(dp[n][be][ud][ok][md] >= 0) return dp[n][be][ud][ok][md]; int ret = 0; for(int i = 0; i <= ((ok)?9:(int)(s[n]-'0')); i++){ if(ud == 0 && be <= i) continue; if(ud == 1 && be >= i) continue; if(ud == 2 && be != 0 && be == i) continue; int u; if(ud == 2){ if(be == 0) u = 2; else if(be > i) u = 1; else u = 0; }else{ u = (ud+1)%2; } ret += solve(n+1,i,u,(ok || i != (int)(s[n]-'0'))?1:0,(md*10+i)%m); } return dp[n][be][ud][ok][md] = ret%10000; } int main(void){ string c,d; cin >> c >> d >> m; for(int i = (int)c.size()-1; i >= 0; i--){ if(c[i] == '0'){ c[i] = '9'; }else{ c[i]--; break; } } s = c; memset(dp,-1,sizeof(dp)); int a = solve(0,0,2,0,0); s = d; memset(dp,-1,sizeof(dp)); int b = solve(0,0,2,0,0); cout << (b + 10000 - a)%10000 << endl; }
