今回は割と余裕をもって全完。
https://atcoder.jp/contests/abc292/tasks/abc292_g
問題
M桁の整数がN個与えられる。
ただし一部の整数の一部の桁の数字は不明である。
また、各整数はLeading Zeroがあってもよい。
不明の数字にそれぞれ0~9を当てはめたとき、このN個の整数が真に単調増加であるようなものは何通りか。
解法
f(n,L,R,d) := 上からn桁目まで見たとき、L個目から(R-1)個目までの整数が同じ値で、かつn桁目はd以上でなければならない場合のn+1桁目以降の組み合わせ
とする。この値は、
- n=Mの時は、R-L==1の時1、それ以外0 (真に単調増加でないといけないので)
- それ以外の場合、L個目からX個目まで(n+1)桁目にdを持ってくることを考えると、f(n+1,L,X+1,0)*f(n,X+1,R,d+1)を加算する。
といった要領で、メモ化再帰でO(M*N^3)で解ける。
int N,M; string S[40]; const ll mo=998244353; ll memo[41][41][41][10]; ll dfs(int C,int L,int R,int D) { if(L==R) return 1; if(D>=10) return 0; if(C==M) { if(L+1==R) return 1; return 0; } if(memo[C][L][R][D]>=0) return memo[C][L][R][D]; ll ret=0; ret+=dfs(C,L,R,D+1); for(int i=L;i<R;i++) { if(S[i][C]!='?'&&S[i][C]!=D+'0') break; (ret+=dfs(C+1,L,i+1,0)*dfs(C,i+1,R,D+1))%=mo; } return memo[C][L][R][D]=ret%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) cin>>S[i]; MINUS(memo); cout<<dfs(0,0,N,0)<<endl; }
まとめ
整数だと悩んじゃうけど、文字列で辞書順に並べると考えると割とすんなり思いつけた。