SRM434 Div1 Medium

500

ある文字を変更した場合の増加分の多い順に貪欲に変更する。
多倍長整数あれば楽?



自前のBigIntは長いので略

int conv(char c)
{
  if ('0' <= c && c <= '9') return c - '0';
  return c - 'A' + 10;
}

class HexatridecimalSum {
public:
  string maximizeSum(vector <string> numbers, int k)
  {
    const string D = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for (int i = 0; i + 1 < D.size(); ++i) {
      if (D[i] == '9' && D[i + 1] == 'A') continue;
      else assert(D[i] + 1 == D[i + 1]);
    }

    const int N = 50 + 1;
    BigInt w[N];
    w[0] = BigInt("1");
    for (int i = 1; i < N; ++i) {
      w[i] = w[i - 1] * 36;
    }

    for (int i = 0; i < numbers.size(); ++i) {
      reverse(numbers[i].begin(), numbers[i].end());
    }
    map<char, BigInt> m;
    for (int i = 0; i < D.size(); ++i) {
      m[D[i]] = BigInt("0");
    }
    for (int i = 0; i < numbers.size(); ++i) {
      for (int j = 0; j < numbers[i].size(); ++j) {
        BigInt a = w[j] * conv(numbers[i][j]);
        BigInt b = w[j] * conv('Z');
        m[numbers[i][j]] = m[numbers[i][j]] + (b - a);
      }
    }

    vector< pair<BigInt, char> > v;
    each (i, m) {
      v.push_back(make_pair(i->second, i->first));
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    for (int i = 0; i < k; ++i) {
      for (int j = 0; j < numbers.size(); ++j) {
        replace(numbers[j].begin(), numbers[j].end(), v[i].second, 'Z');
      }
    }

    BigInt sum("0");
    for (int i = 0; i < numbers.size(); ++i) {
      BigInt n("0");
      BigInt w("1");
      for (int j = 0; j < numbers[i].size(); ++j) {
        n = n + (w * conv(numbers[i][j]));
        w = w * 36;
      }
      sum = sum + n;
    }

    string ret;
    while (!(BigInt("0") == sum)) {
      BigInt n = sum % BigInt("36");
      int m = atoi((n.toString()).c_str());
      ret += D[m];
      sum = sum / BigInt("36");
    }
    reverse(ret.begin(), ret.end());
    return ret;
  }
};