問題
0～9、A～Zの36種類のアルファベットで表わされる36進数の数字を考える。最初に、複数の36進数の数字が与えられる。
このうち、任意のk個のアルファベットをZに変換する。
このとき、与えられた数字の和が最大となるように変換し、その最大の数字を36進数で求める。
解き方
問題としては貪欲法で解けそう。
ただし与えられる数字は50個、文字列長も50個であることから単純な変換ではオーバーフローしてしまう。
そこで、36進数のままで足し算と大小比較を行うことにする。
今回は元の数字を最初に足してしまってもよい。
それから各アルファベットについての差分を計算し、その計算した差分を降順にソートして順にｋ個足して解いた。
最初にオーバーフローまで踏まえてコーディングしないと後戻りは難しいので、
最初にあらかじめオーバーフローと計算量を忘れずに見積もる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class HexatridecimalSum {
public:
int getint(char ch){
if('0'<=ch&&ch<='9')return ch-'0';
return ch-'A'+10;
}
char getch(int x){
if(0<=x&&x<=9)return (char)('0'+x);
return (char)(x-10)+'A';
}
void getconnect(string &a,string b){
for(;b.size()<100;b='0'+b);
int cnt=0;
for(int i=99;i>=0;i--){
cnt+=getint(a[i])+getint(b[i]);
a[i]=getch(cnt%36);
cnt/=36;
}
}
string maximizeSum(vector<string> numbers, int k) {
string ret(100,'0');
int n=numbers.size();
FORE(i,0,n)getconnect(ret,numbers[i]);
string str[36];
FORE(i,0,36){
string org(100,'0');
FORE(j,0,n){
string tmp(100,'0');
FORE(k,0,numbers[j].size()){
if(getint(numbers[j][k])==i){
tmp[100-numbers[j].size()+k]=getch(35-i);
}
}
getconnect(org,tmp);
}
str[i]=org;
}
sort(str,str+36);
reverse(str,str+36);
FORE(i,0,k)getconnect(ret,str[i]);
for(;ret[0]=='0';ret=ret.substr(1));
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class HexatridecimalSum {
public:
int getint(char ch){
if('0'<=ch&&ch<='9')return ch-'0';
return ch-'A'+10;
}
char getch(int x){
if(0<=x&&x<=9)return (char)('0'+x);
return (char)(x-10)+'A';
}
void getconnect(string &a,string b){
for(;b.size()<100;b='0'+b);
int cnt=0;
for(int i=99;i>=0;i--){
cnt+=getint(a[i])+getint(b[i]);
a[i]=getch(cnt%36);
cnt/=36;
}
}
string maximizeSum(vector<string> numbers, int k) {
string ret(100,'0');
int n=numbers.size();
FORE(i,0,n)getconnect(ret,numbers[i]);
string str[36];
FORE(i,0,36){
string org(100,'0');
FORE(j,0,n){
string tmp(100,'0');
FORE(k,0,numbers[j].size()){
if(getint(numbers[j][k])==i){
tmp[100-numbers[j].size()+k]=getch(35-i);
}
}
getconnect(org,tmp);
}
str[i]=org;
}
sort(str,str+36);
reverse(str,str+36);
FORE(i,0,k)getconnect(ret,str[i]);
for(;ret[0]=='0';ret=ret.substr(1));
return ret;
}
};