問題名結構好き。
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; }
まとめ
難しさはそれほどなくて、実装面倒枠?
構文解析系、どうも面倒な印象がある。