色々問題文に不備があった気がするけど、なんとか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; }
まとめ
- が無い場合について問題文で言及がないのまずくないかな…。