kmjp's blog

競技プログラミング参加記です

AtCoder ABC #292 : G - Count Strictly Increasing Sequences

今回は割と余裕をもって全完。
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;
	
}

まとめ

整数だと悩んじゃうけど、文字列で辞書順に並べると考えると割とすんなり思いつけた。