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; } };