SRM549 Div2 Easy

250

よく分からないからDPする。
memo[ n回スワップした ][ 今の状態 ]

view plainprint?

1. const int N = 1000 + 1;  
2. map<string, double> memo[N];  
3.   
4. class BallAndHats {  
5. public:  
6.   int getHat(string hats, int numSwaps)  
7.   {  
8.     fill(memo, memo + N, map<string, double>());  
9.     memo[0][hats] = 1.0;  
10.   
11.     for (int i = 0; i < numSwaps; ++i) {  
12.       FOR (s, memo[i]) {  
13.         string t = s->first;  
14.         double cnt = 0;  
15.         for (int a = 0; a + 1 < t.size(); ++a) {  
16.           if (t[a] == 'o' || t[a + 1] == 'o') ++cnt;  
17.         }  
18.         for (int a = 0; a  + 1 < t.size(); ++a) {  
19.           if (t[a] == 'o' || t[a + 1] == 'o') {  
20.             swap(t[a], t[a + 1]);  
21.             memo[i + 1][t] += s->second / cnt;  
22.             swap(t[a], t[a + 1]);  
23.           }  
24.         }  
25.       }  
26.     }  
27.   
28.     double mx = 0;  
29.     FOR (i, memo[numSwaps]) {  
30.       mx = max(mx, i->second);  
31.     }  
32.   
33.     int mn = 4;  
34.     FOR (i, memo[numSwaps]) {  
35.       if (i->second == mx) {  
36.         mn = min(mn, (int)i->first.find("o"));  
37.       }  
38.     }  
39.   
40.     return mn;  
41.   }  
42. };  

const int N = 1000 + 1;
map<string, double> memo[N];

class BallAndHats {
public:
  int getHat(string hats, int numSwaps)
  {
    fill(memo, memo + N, map<string, double>());
    memo[0][hats] = 1.0;

    for (int i = 0; i < numSwaps; ++i) {
      FOR (s, memo[i]) {
        string t = s->first;
        double cnt = 0;
        for (int a = 0; a + 1 < t.size(); ++a) {
          if (t[a] == 'o' || t[a + 1] == 'o') ++cnt;
        }
        for (int a = 0; a  + 1 < t.size(); ++a) {
          if (t[a] == 'o' || t[a + 1] == 'o') {
            swap(t[a], t[a + 1]);
            memo[i + 1][t] += s->second / cnt;
            swap(t[a], t[a + 1]);
          }
        }
      }
    }

    double mx = 0;
    FOR (i, memo[numSwaps]) {
      mx = max(mx, i->second);
    }

    int mn = 4;
    FOR (i, memo[numSwaps]) {
      if (i->second == mx) {
        mn = min(mn, (int)i->first.find("o"));
      }
    }

    return mn;
  }
};