SRM434 Div1 Medium

500

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



自前のBigIntは長いので略

view plainprint?

1. int conv(char c)  
2. {  
3.   if ('0' <= c && c <= '9') return c - '0';  
4.   return c - 'A' + 10;  
5. }  
6.   
7. class HexatridecimalSum {  
8. public:  
9.   string maximizeSum(vector <string> numbers, int k)  
10.   {  
11.     const string D = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";  
12.     for (int i = 0; i + 1 < D.size(); ++i) {  
13.       if (D[i] == '9' && D[i + 1] == 'A') continue;  
14.       else assert(D[i] + 1 == D[i + 1]);  
15.     }  
16.   
17.     const int N = 50 + 1;  
18.     BigInt w[N];  
19.     w[0] = BigInt("1");  
20.     for (int i = 1; i < N; ++i) {  
21.       w[i] = w[i - 1] * 36;  
22.     }  
23.   
24.     for (int i = 0; i < numbers.size(); ++i) {  
25.       reverse(numbers[i].begin(), numbers[i].end());  
26.     }  
27.     map<char, BigInt> m;  
28.     for (int i = 0; i < D.size(); ++i) {  
29.       m[D[i]] = BigInt("0");  
30.     }  
31.     for (int i = 0; i < numbers.size(); ++i) {  
32.       for (int j = 0; j < numbers[i].size(); ++j) {  
33.         BigInt a = w[j] * conv(numbers[i][j]);  
34.         BigInt b = w[j] * conv('Z');  
35.         m[numbers[i][j]] = m[numbers[i][j]] + (b - a);  
36.       }  
37.     }  
38.   
39.     vector< pair<BigInt, char> > v;  
40.     each (i, m) {  
41.       v.push_back(make_pair(i->second, i->first));  
42.     }  
43.     sort(v.begin(), v.end());  
44.     reverse(v.begin(), v.end());  
45.   
46.     for (int i = 0; i < k; ++i) {  
47.       for (int j = 0; j < numbers.size(); ++j) {  
48.         replace(numbers[j].begin(), numbers[j].end(), v[i].second, 'Z');  
49.       }  
50.     }  
51.   
52.     BigInt sum("0");  
53.     for (int i = 0; i < numbers.size(); ++i) {  
54.       BigInt n("0");  
55.       BigInt w("1");  
56.       for (int j = 0; j < numbers[i].size(); ++j) {  
57.         n = n + (w * conv(numbers[i][j]));  
58.         w = w * 36;  
59.       }  
60.       sum = sum + n;  
61.     }  
62.   
63.     string ret;  
64.     while (!(BigInt("0") == sum)) {  
65.       BigInt n = sum % BigInt("36");  
66.       int m = atoi((n.toString()).c_str());  
67.       ret += D[m];  
68.       sum = sum / BigInt("36");  
69.     }  
70.     reverse(ret.begin(), ret.end());  
71.     return ret;  
72.   }  
73. };  

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