SRM551 Div2 Medium

500

使う文字と範囲を全部試す。

view plainprint?

1. class ColorfulChocolates {  
2. public:  
3.   int maximumSpread(string C, int S)  
4.   {  
5.     const int N = C.size();  
6.   
7.     map< char, vector<int> > index;  
8.     for (int i = 0; i < N; ++i) {  
9.       index[C[i]].push_back(i);  
10.     }  
11.   
12.     int mx = 1;  
13.   
14.     for (int begin = 0; begin < N; ++begin) {  
15.       for (int len = 1; begin + len <= N; ++len) {  
16.         for (char c = 'A'; c <= 'Z'; ++c) {  
17.           vector<int> v = index[c];  
18.           if (len <= v.size()) ; else continue;  
19.           for (int i = 0; i + len <= v.size(); ++i) {  
20.             int cost = 0;  
21.             for (int j = 0; j < len; ++j) {  
22.               int src = v[i + j];  
23.               int dst = begin + j;  
24.               cost += abs(src - dst);  
25.             }  
26.             if (cost <= S) mx = max(mx, len);  
27.           }  
28.         }  
29.       }  
30.     }  
31.   
32.     return mx;  
33.   }  
34. };  

class ColorfulChocolates {
public:
  int maximumSpread(string C, int S)
  {
    const int N = C.size();

    map< char, vector<int> > index;
    for (int i = 0; i < N; ++i) {
      index[C[i]].push_back(i);
    }

    int mx = 1;

    for (int begin = 0; begin < N; ++begin) {
      for (int len = 1; begin + len <= N; ++len) {
        for (char c = 'A'; c <= 'Z'; ++c) {
          vector<int> v = index[c];
          if (len <= v.size()) ; else continue;
          for (int i = 0; i + len <= v.size(); ++i) {
            int cost = 0;
            for (int j = 0; j < len; ++j) {
              int src = v[i + j];
              int dst = begin + j;
              cost += abs(src - dst);
            }
            if (cost <= S) mx = max(mx, len);
          }
        }
      }
    }

    return mx;
  }
};