SRM549 Div2 Easy

250

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

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