kmjp's blog

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

Codeforces #465 Div2 E. Fafa and Ancient Mathematics

手間取ったけどなんとか全完。
http://codeforces.com/contest/935/problem/E

問題

括弧と1桁の数字と演算子で構成された数式が与えられる。
ただし演算子の種別は不明で、+と-の総数だけが与えられている。

  1. と-を最適に配置すると、この式の最大値はいくつになるか。

なお、+-のどちらかは100個以下である。

解法

数式をDFSの要領でParseしつつ、+-の少ない方に対し、使用回数毎に数式の最大値を最小値を求め、DPしていこう。

string E;
int P,M;
int cur;

vector<pair<int,int>> hoge() {
	vector<pair<int,int>> R;
	int S=min(P,M);
	int i;
	FOR(i,S+1) R.push_back({-1<<20,1<<20});
	
	
	if(E[cur]=='(') {
		cur++;
		vector<pair<int,int>> A,B;
		A=hoge();
		assert(E[cur]=='?');
		cur++;
		B=hoge();
		assert(E[cur]==')');
		cur++;
		
		int x,y;
		if(P<=M) {
			FOR(x,P+1) FOR(y,P+1) {
				if(x+y<=P) {
					R[x+y].first=max(R[x+y].first,A[x].first-B[y].second);
					R[x+y].second=min(R[x+y].second,A[x].second-B[y].first);
					if(x+y+1<=P) {
						R[x+y+1].first=max(R[x+y+1].first,A[x].first+B[y].first);
						R[x+y+1].second=min(R[x+y+1].second,A[x].second+B[y].second);
					}
				}
			}
		}
		else {
			FOR(x,M+1) FOR(y,M+1) {
				if(x+y<=M) {
					R[x+y].first=max(R[x+y].first,A[x].first+B[y].first);
					R[x+y].second=min(R[x+y].second,A[x].second+B[y].second);
					if(x+y+1<=M) {
						R[x+y+1].first=max(R[x+y+1].first,A[x].first-B[y].second);
						R[x+y+1].second=min(R[x+y+1].second,A[x].second-B[y].first);
					}
				}
			}
		}
	}
	else {
		R[0]={(int)(E[cur]-'0'),(int)(E[cur]-'0')};
		cur++;
	}
	return R;
	
}

void solve() {
	int i,j,k,l,x,y; string s;
	
	cin>>E;
	cin>>P>>M;
	auto r=hoge();
	cout<<r[min(P,M)].first<<endl;
}

まとめ

    • のどちらかだけ数の上限が指定される、って珍しいな。