Codeforces #347 Div1. A. Rebus

久々の通常回だけどunratedなのね。Bで苦戦したけど一応解けきれた。
http://codeforces.com/contest/663/problem/A

問題

? + ? - ? = N
のように？と＋・－で構成された式が与えられる。
右辺の値をNとするとき、?に1～Nのいずれかを設定し、式が成り立つようにせよ。

解法

いくつか方法があるようだ。
加算される？の数と減算される？の数を求めよう。
自分は以下の何れかのうち条件を満たすものを求めた。

• 加算される？にすべて下限の1を設定し、あとは両辺が一致するよう適切に減算される？を設定する。
• 加算される？にすべて上限のNを設定し、あとは両辺が一致するよう適切に減算される？を設定する。
• 減算される？にすべて下限の1を設定し、あとは両辺が一致するよう適切に加算される？を設定する。
• 減算される？にすべて上限のNを設定し、あとは両辺が一致するよう適切に加算される？を設定する。

vector<int> S[2];
int P[101];
int res;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int p=0;
	x=0;
	while(1) {
		cin>>s;
		S[p].push_back(x);
		P[x]=p;
		x++;
		cin>>s;
		if(s=="+") p=0;
		if(s=="-") p=1;
		if(s=="=") {
			cin>>res;
			break;
		}
	}
	int mipl=S[0].size(),mapl=S[0].size()*res;
	int mimi=S[1].size(),mami=S[1].size()*res;
	
	x=-1,y=-1;
	if(mipl-mimi>=res && mipl-mami<=res) x=mipl, y=res-x;
	if(mapl-mimi>=res && mapl-mami<=res) x=mapl, y=res-x;
	if(mapl-mimi>=res && mipl-mimi<=res) y=mimi, x=res+y;
	if(mapl-mami>=res && mipl-mami<=res) y=mami, x=res+y;
	if(x==-1) return _P("Impossible\n");
	int pi=0,mi=0;
	_P("Possible\n");
	FOR(i,S[0].size()+S[1].size()) {
		if(i) _P(" %c ","+-"[P[i]]);
		if(P[i]==0) _P("%d",x/S[0].size()+(pi<x%S[0].size())), pi++;
		if(P[i]==1) _P("%d",y/S[1].size()+(mi<y%S[1].size())), mi++;
	}
	_P(" = %d\n",res);
}

まとめ

「ただし各？に同じ値を設定してはならない」とかすると難易度上がりそう。