kmjp's blog

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

LeetCode Weekly Contest 182 : 1397. Find All Good Strings

久々の難易度8。
https://leetcode.com/contest/weekly-contest-182/problems/find-all-good-strings/

問題

正整数Nと、N文字の文字列s1,s2、あと別の文字列evilが与えられる。
N文字のアルファベット小文字の文字列のうち、辞書順でs1以上s2以下でevilを部分文字列に含まないものは何通りか。

解法

evilに対しKMP法のテーブルを作っておけば、状態として
(N文字中prefixを何文字定めたか, s1より大きいことが確定したか, s2より小さいことが確定したか, テーブル上の位置)
を持ってあとは桁DPと似た要領で上の文字から総当たりしていくだけ。

int stt[52][26];
const char base='a';
void CreateSTT(string& pat) {
	int x,y,z,l;
	ZERO(stt);
	l=pat.size();
	FOR(x,l) {
		FOR(y,26) {
			if(base+y == pat[x]) stt[x][y]=x+1;
			else {
				string pre=pat.substr(0,x)+(char)(base+y);
				for(z=1;z<=x;z++) if(pre.substr(pre.size()-z) == pat.substr(0,z)) stt[x][y]=z;
			}
		}
	}
	FOR(y,26) stt[l][y]=l;
}

int N;
ll dp[505][52][2][2];
const ll mod=1000000007;
string S1,S2,E;

class Solution {
public:
	ll hoge(int cur,int ev,int mo,int le) {
		if(cur==N) return (ev<E.size());
		ll& ret=dp[cur][ev][mo][le];
		if(ret>=0) return ret;
		ret=0;
		int i;
		FOR(i,26) {
			if(mo==0 && i<S1[cur]-'a') continue;
			if(le==0 && i>S2[cur]-'a') continue;
			int nmo=mo | (i>S1[cur]-'a');
			int nle=le | (i<S2[cur]-'a');
			int nev=stt[ev][i];
			ret+=hoge(cur+1,nev,nmo,nle);
		}
		ret%=mod;
		return ret;
	}
	
    int findGoodStrings(int n, string s1, string s2, string evil) {
		MINUS(dp);
		CreateSTT(evil);
		S1=s1;
		S2=s2;
		E=evil;
		N=n;
		return hoge(0,0,0,0);
        
    }
};

まとめ

なんで出題までに問題No確定させてくれないの…?