kmjp's blog

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

KUPC2016 : F - 早解き / Speed Solving

よくこれ一発で解けたな。
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;
			}
		}
	}
	
}

まとめ

よくこういう問題思いつくなぁ。