TopCoder SRM 434 Div1 Medium maximizeSum

問題

36進法の数がn個与えられる。
これらの数から、ちょうどk種類のアルファベットを全て'Z'に置換する。


置換後の全ての数の和の最大値を36進法で求めよ。

制約条件

n≦50
それぞれの数の桁数≦50

方針

36進法の多倍長加算を実装する。


あるアルファベットを'Z'に置き換えたときの差分は簡単に求まるので、
差分の大きいアルファベットから順にk種類選んで置換すればよい。

ソースコード

int num(char c){return isdigit(c)?c-'0':c-'A'+10;}
char ch(int n){return n<10?'0'+n:'A'+n-10;}

string add(string a,string b){
	int n=a.size(),m=b.size();
	rep(i,max(n,m)+1-n)a="0"+a;
	rep(i,max(n,m)+1-m)b="0"+b;
	string res=a;
	
	int carry=0;
	for(int i=res.size()-1;i>=0;i--){
		int t=num(a[i])+num(b[i])+carry;
		res[i]=ch(t%36);
		carry=t>=36;
	}
	while(res.size()>1&&res[0]=='0')res=res.substr(1);
	return res;
}

bool cmp(string a,string b){
	while(a.size()&&a[0]=='0')a=a.substr(1);
	while(b.size()&&b[0]=='0')b=b.substr(1);
	if(a.size()!=b.size())return a.size()>b.size();
	return a>b;
}
class HexatridecimalSum {
	public:
	string maximizeSum(vector <string> numbers, int k) 
	{
		int n=numbers.size();
		vs d(36,string(1,'0'));
		rep(i,36)rep(j,n){
			string tmp(numbers[j].size(),'0');
			rep(k,tmp.size())if(num(numbers[j][k])==i)tmp[k]=ch(num('Z')-i);
			d[i]=add(d[i],tmp);
		}
		sort(all(d),cmp);
		string ans(1,'0');
		rep(i,n)ans=add(ans,numbers[i]);
		rep(i,k)ans=add(ans,d[i]);
		return ans;
	}
};