kmjp's blog

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

yukicoder : No.1677 mæx

問題名結構好き。
https://yukicoder.me/problems/no/1677

問題

0,1,2,max,mexで構成される式が与えられる。max,mexの引数は2個固定である。
ただし、

  • 一部、0,1,2のいずれか不定な箇所がある
  • 一部、max,mexのいずれか不定な箇所がある

とき、不定な箇所の埋め方のうち、式の評価値がKになるのは何通りか。

解法

愚直に式を構文解析し、値が0,1,2となるケースを数え上げて行けばよい。

int cur;
string S;
int K;
const ll mo=998244353;
vector<ll> dfs() {
	if(S[cur]=='m') {
		char c=S[cur+1];
		cur+=4;
		vector<ll> A=dfs();
		cur++;
		vector<ll> B=dfs();
		cur++;
		
		vector<ll> C={0,0,0};
		int a,b;
		FOR(a,3) FOR(b,3) {
			if(c=='a'||c=='?') {
				(C[max(a,b)]+=A[a]*B[b])%=mo;
			}
			if(c=='e'||c=='?') {
				int ne=0;
				if(ne==a||ne==b) ne++;
				if(ne==a||ne==b) ne++;
				if(ne==a||ne==b) ne++;
				(C[ne]+=A[a]*B[b])%=mo;
			}
		}
		return C;
		
	}
	else {
		char c=S[cur++];
		if(c=='0') return {1,0,0};
		if(c=='1') return {0,1,0};
		if(c=='2') return {0,0,1};
		return {1,1,1};
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>K;
	auto A=dfs();
	cout<<A[K]<<endl;
}

まとめ

難しさはそれほどなくて、実装面倒枠?
構文解析系、どうも面倒な印象がある。