よくこれ一発で解けたな。
http://kupc2016.contest.atcoder.jp/tasks/kupc2016_f
問題
最大2ケタの整数と、2値の最大値・最小値を取る前置記法の演算子からなる計算式の文法がある。
計算式が与えられるので、最小でprefixを何文字まで見た時点で値が確定するか答えよ。
解法
prefixを総当たりし、値が1つに確定するか判定していく。
各項でありえる値の最小値・最大値を持って、計算式に沿って計算していけば良い。
int Q; int N; string S; int ptr,L; pair<int,int> hoge() { if(ptr>=L) return {0,99}; int x=ptr; if(S[x]=='0') { ptr++; return {0,0}; } else if(S[x]>='1' && S[x]<='9') { ptr++; if(x==L-1) { return {S[x]-'0',(S[x]-'0')*10+9}; } if(S[ptr]>='0' && S[ptr]<='9') { ptr++; return {(S[x]-'0')*10+(S[x+1]-'0'),(S[x]-'0')*10+(S[x+1]-'0')}; } else { return {S[x]-'0',S[x]-'0'}; } } else if(S[x]=='^' || S[x]=='_') { ptr++; ptr++; if(ptr>=L) return {0,99}; auto lh=hoge(),rh=lh; ptr++; if(ptr>=L) rh={0,99}; else rh=hoge(); ptr++; if(S[x]=='^') return {max(lh.first,rh.first),max(lh.second,rh.second)}; else return {min(lh.first,rh.first),min(lh.second,rh.second)}; } } void solve() { int i,j,k,l,r,x,y; string s; cin>>Q; while(Q--) { cin>>S; N=S.size(); for(i=1;i<=N;i++) { ptr=0; L=i; auto ret=hoge(); if(ret.first==ret.second) { cout<<ret.first<<" "<<i<<endl; break; } } } }
まとめ
よくこういう問題思いつくなぁ。