今回はParallelないのね。
https://community.topcoder.com/stat?c=problem_statement&pm=14203
問題
整数列Aが与えられる。
(leading zeroを除き)A中の各桁の整数を一部書き換えられる。
書き換えて1~9に出来る回数をそれぞれ最大D[i]とする。
書き換え後のAの総和を答えよ。
解法
上位の桁ほど大きな値に書き換えるのが良いのは自明である。
そこで上位の桁から順書き換えを考えていこう。
Aの各要素を、今見ている桁の順でソートする。
小さい値を大きい値にするほど総和を大きくできるので、小さい順に桁の数値を書き換えられる最大値に変えていけば良い。
vector<int> C[10]; class ReplacingDigit { public: int getMaximumStockWorth(vector <int> A, vector <int> D) { int N=A.size(); int i,j,x,y; FOR(i,7) C[i].clear(); FOR(i,N) { FOR(j,7) { if(A[i]==0) break; C[j].push_back(A[i]%10); A[i]/=10; } } int ret=0; int p10=1000000; for(j=6;j>=0;j--) { sort(C[j].begin(),C[j].end()); FORR(r,C[j]) { for(i=9;i>=1;i--) if(D[i-1]&&i>r) r=i,D[i-1]--; ret += r*p10; } p10/=10; } return ret; } }
まとめ
普段のDiv2 Mediumよりは少し難しい?