naoya_t@topcoder

SRM434 Div1 Medium: HexatridecimalSum

過去問, 練習 | 04:12 |

時間切れから６分後に出来たやつでそのままSysTest通った件（無念）

• Bignumライブラリ作るべし

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define forr(var,from,to) for(int var=(from);var<=(to);var++) 
#define found(s,e)  ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())
#define lastc(str) (*((str).end()-1))

class HexatridecimalSum {
  int de(int c){
    if('0'<=c && c<='9') return c-'0';
    else return 10+(c-'A');
  }
  int en(int c){
    if (c<10) return '0'+c;
    else return 'A'+(c-10);
  }
 public:
  string maximizeSum(vector<string> numbers, int k) {
    vvi m(52);
    rep(i,52) m[i].resize(0);

    tr(numbers,it){
      string ns=*it;
      int l=sz(ns);
      rep(i,l) m[i].pb(de(ns[l-i-1]));
    }
    int maxk = 0;
    rep(i,52){
      if(sz(m[i])>0) maxk=i;
      sort(all(m[i]));
    }

    vvi di(36),id(36);
    rep(i,36) {
      di[i].resize(maxk+3);
      id[i].resize(maxk+3);
      rep(j,maxk+3) di[i][j] = id[i][j] = 0;
    }

    vi sum(maxk+3,0);
    for(int i=maxk;i>=0;i--){
      tr(m[i],it) {
        int c = *it;
        di[c][i] += (35-c);
        sum[maxk+2-i] += c;
      }
    }
    rep(c,36) {
      rep(i,maxk+2){
        if(di[c][i] >= 36) {
          di[c][i+1] += di[c][i]/36;
          di[c][i] %= 36;
        }
      }
    }
    rep(c,36){
      rep(i,maxk+3){
        id[c][maxk+2-i] = di[c][i];
      }
    }
    sort(all(id)); reverse(all(id));
    rep(i,k){
      rep(j,maxk+3){
        sum[j] += id[i][j];
      }
    }
    for(int i=maxk+2;i>0;i--){
      if(sum[i] >= 36) {
        sum[i-1] += sum[i]/36;
        sum[i] %= 36;
      }
    }
    bool left=true;
    stringstream ss;
    rep(i,maxk+3){
      if (left && sum[i]==0) continue;
      left=false;
      ss << (char)en(sum[i]);
    }
    return ss.str();
  }
};