kmjp's blog

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

TopCoderOpen 2016 Round1B Medium ReplacingDigit

今回は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よりは少し難しい?