Codeforces #689 Div2 F. Mathematical Expression

本番通した人少ないのに、upsolve数多いな。
https://codeforces.com/contest/1461/problem/F

問題

一桁の数字の列と、利用可能な演算子(加算・減算・乗算)が与えられる。
数字の間に演算子を挿入し、式の値を最大化せよ。

解法

• 演算子が1種類なら選択肢はなく自明。
• 加算と減算のみ可能なら、すべて加算とする
• 乗算と減算のみ可能なら、最初の0の手前に減算を入れ、それ以外乗算とする。
• すべて使える、または加算と乗算が利用可能な時、減算をするメリットはないので、あとは加算と乗算をどう使う考える。
  • まず0の前後は、加算を入れる。
  • そうするとあとは0のない数字の列を考えればよい。先頭と末尾の1はまず加算としてしまおう。
  • 1でない数字同士は掛けてしまおう。すると、(大きな値),1,1,1,(大きな値),1,1,1...と、大きな値と1の連続が続くことになる。
  • 全部掛け合わせて十分大きい場合、全部掛けてしまおう。
  • そうでない場合、1の連続部分を加算にするか乗算にするか総当たりしてしまおう。

int N;
int A[101010];
string S;
int mask;

int pat[1<<20];
void out(vector<int> V) {
	if(V.size()==1) {
		cout<<V[0];
		return;
	}
	int i,j;
	int pre=0,suf=0;
	while(V.size()&&V.back()==1) suf++, V.pop_back();
	if(V.empty()) {
		FOR(i,suf) {
			if(i) cout<<"+";
			cout<<1;
		}
		return;
	}
	reverse(ALL(V));
	while(V.size()&&V.back()==1) pre++, V.pop_back();
	reverse(ALL(V));
	
	ll mul=1;
	FORR(v,V) {
		mul*=v;
		if(mul>10*V.size()) {
			FOR(i,pre) cout<<"1+";
			FOR(i,V.size()) {
				if(i) cout<<"*";
				cout<<V[i];
			}
			FOR(i,suf) cout<<"+1";
			return;
		}
	}
	
	vector<pair<int,vector<int>>> W;
	FORR(v,V) {
		if(W.empty()) {
			W.push_back({1,vector<int>()});
		}
		else if(v==1) {
			if(W.back().second[0]!=1) W.push_back({1,vector<int>()});
		}
		else {
			if(W.back().second[0]==1) W.push_back({1,vector<int>()});;
		}
		W.back().first*=v;
		W.back().second.push_back(v);
	}
	/*
	FORR(w,W) {
		cout<<w.first<<" ";
		FORR(v,w.second) cout<<v;
		cout<<endl;
	}
	*/
	assert(W.size()%2==1);
	int N=(W.size()-1)/2;
	int mask;
	FOR(mask,1<<N) {
		int sum=0;
		int cur=W[0].first;
		FOR(i,N) {
			if(mask&(1<<i)) {
				cur*=W[(i+1)*2].first;
			}
			else {
				sum+=cur+W[i*2+1].second.size();
				cur=W[(i+1)*2].first;
			}
		}
		pat[mask]=sum+cur;
	}
	
	mask=max_element(pat,pat+(1<<N))-pat;
	
	FOR(i,pre) cout<<"1+";
	
	FOR(i,W[0].second.size()) {
		if(i) cout<<"*";
		cout<<W[0].second[i];
	}
	FOR(i,N) {
		if(mask&(1<<i)) {
			FORR(v,W[i*2+1].second) cout<<"*"<<v;
			FORR(v,W[i*2+2].second) cout<<"*"<<v;
		}
		else {
			FORR(v,W[i*2+1].second) cout<<"+1";
			cout<<"+";
			FOR(j,W[i*2+2].second.size()) {
				if(j) cout<<"*";
				cout<<W[i*2+2].second[j];
			}
		}
	}
	
	FOR(i,suf) cout<<"+1";
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	cin>>S;
	FORR(c,S) {
		if(c=='+') mask|=1;
		if(c=='*') mask|=2;
		if(c=='-') mask|=4;
	}
	
	if(mask==1||mask==5) {
		cout<<A[0];
		FOR(i,N-1) cout<<"+"<<A[i+1];
		cout<<endl;
		return;
	}
	if(mask==2) {
		cout<<A[0];
		FOR(i,N-1) cout<<"*"<<A[i+1];
		cout<<endl;
		return;
	}
	if(mask==4) {
		cout<<A[0];
		FOR(i,N-1) cout<<"-"<<A[i+1];
		cout<<endl;
		return;
	}
	if(mask==6) {
		cout<<A[0];
		FOR(i,N-1) {
			if(A[i+1]==0) cout<<"-"<<A[i+1];
			else cout<<"*"<<A[i+1];
		}
		cout<<endl;
		return;
	}
	
	vector<vector<int>> V(1),W;
	FOR(i,N) {
		if(A[i]==0) {
			V.push_back(vector<int>());
			V.back().push_back(0);
			V.push_back(vector<int>());
		}
		else {
			V.back().push_back(A[i]);
		}
	}
	FORR(v,V) if(v.size()) W.push_back(v);
	
	FOR(i,W.size()) {
		if(i) cout<<"+";
		out(W[i]);
	}
	cout<<endl;
	
	
}

まとめ

意外に面倒くさい。