kmjp's blog

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

HackerRank HourRank 30 : B. Jerry's Expression

色々問題文に不備があった気がするけど、なんとかTシャツ圏内でした。
https://www.hackerrank.com/contests/hourrank-30/challenges/jerrys-expression

問題

ポーランド記法で書かれた数式が与えられる。
この式は演算子は+-のみであり、かつ数字は全て伏せられている。

伏せられた箇所に正整数を埋め、式の値を0にしたい。
埋める値の最大値を最小化する埋め方を答えよ。

解法

演算子は+-のみなので、各値は最終的な値に足されるか引かれるかのいずれかである。
よって、各値どちらになるかを分類しよう。

足し引きのうち、値の登場回数が多い方は1を埋め、少ない方は総和が前者に等しくなるよう均等に値を振ろう。

vector<int> P[2];
string S;
int cur;
int num[1010101];
void dfs(int p) {
	if(S[cur]=='?') {
		P[p].push_back(cur);
		cur++;
		return;
	}
	if(S[cur]=='+') {
		cur++;
		dfs(p);
		dfs(p);
	}
	else {
		cur++;
		dfs(p);
		dfs(1-p);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	dfs(0);
	
	assert(P[0].size());
	assert(P[1].size());
	if(P[0].size()==P[1].size()) {
		FORR(p,P[0]) num[p]=1;
		FORR(p,P[1]) num[p]=1;
	}
	else if(P[0].size()<P[1].size()) {
		FOR(i,P[0].size()) num[P[0][i]]=P[1].size()/P[0].size()+(i<P[1].size()%P[0].size());
		FORR(p,P[1]) num[p]=1;
	}
	else {
		FOR(i,P[1].size()) num[P[1][i]]=P[0].size()/P[1].size()+(i<P[0].size()%P[1].size());
		FORR(p,P[0]) num[p]=1;
	}
	FOR(i,S.size()) if(num[i]) cout<<num[i]<<endl;
	
}

まとめ

  • が無い場合について問題文で言及がないのまずくないかな…。