SRM572 Div1 Easy

250

前からの範囲と後ろからの範囲がオーバーラップすることに注意。
同じ文字にする必要のあるインデックスの中で、どれに合わせるべきかを調べていく。

view plainprint?

1. class NewArenaPassword {  
2. public:  
3.   int minChange(string old, int K)  
4.   {  
5.     const int N = old.size();  
6.     static int same[55];  
7.     fill(same, same + N, -1);  
8.     for (int i = 0; i < N; ++i) {  
9.       int a = i;  
10.       int b = N - K + i;  
11.       same[max(a, b)] = min(a, b);  
12.     }  
13.     int ret = 0;  
14.     for (int i = N - 1; 0 <= i; --i) {  
15.       vector<int> v;  
16.       for (int j = i; j != -1; j = same[j]) {  
17.         v.push_back(j);  
18.         if (j == same[j]) break;  
19.       }  
20.       char c = '@';  
21.       int mx = 0;  
22.       map<char, int> cnt;  
23.       for (int j = 0; j < v.size(); ++j) {  
24.         int m = ++cnt[old[v[j]]];  
25.         if (mx < m) {  
26.           mx = m;  
27.           c = old[v[j]];  
28.         }  
29.       }  
30.       if (c != '@') {  
31.         for (int j = 0; j < v.size(); ++j) {  
32.           if (old[v[j]] != c) {  
33.             ++ret;  
34.             old[v[j]] = c;  
35.           }  
36.         }  
37.       }  
38.     }  
39.     return ret;  
40.   }  
41. };  

class NewArenaPassword {
public:
  int minChange(string old, int K)
  {
    const int N = old.size();
    static int same[55];
    fill(same, same + N, -1);
    for (int i = 0; i < N; ++i) {
      int a = i;
      int b = N - K + i;
      same[max(a, b)] = min(a, b);
    }
    int ret = 0;
    for (int i = N - 1; 0 <= i; --i) {
      vector<int> v;
      for (int j = i; j != -1; j = same[j]) {
        v.push_back(j);
        if (j == same[j]) break;
      }
      char c = '@';
      int mx = 0;
      map<char, int> cnt;
      for (int j = 0; j < v.size(); ++j) {
        int m = ++cnt[old[v[j]]];
        if (mx < m) {
          mx = m;
          c = old[v[j]];
        }
      }
      if (c != '@') {
        for (int j = 0; j < v.size(); ++j) {
          if (old[v[j]] != c) {
            ++ret;
            old[v[j]] = c;
          }
        }
      }
    }
    return ret;
  }
};