SRM537 Div1 Medium

500
DP[K日][部屋N][Bビット] = K日が経過した部屋NのBビット目が１になっている確率。

view plainprint?

1. class KingXMagicSpells {  
2. public:  
3.   double expectedNumber(vector <int> D, vector <int> S1, vector <int> S2, int K)  
4.   {  
5.     const int N = D.size();  
6.     const int B = 30 + 1;  
7.     ++K;  
8.   
9.     double dp[K][N][B];  
10.     fill(&dp[0][0][0], &dp[K - 1][N - 1][B], 0);  
11.      
12.     for (int i = 0; i < N; ++i) {  
13.       for (int j = 0; j < B; ++j) {  
14.         dp[0][i][j] = (bool)(D[i] & (1 << j));  
15.       }  
16.     }  
17.      
18.     // spell1 : xor  
19.     // spell2 : move  
20.     for (int day = 0; day + 1 < K; ++day) {  
21.       for (int room = 0; room < N; ++room) {  
22.         for (int bit = 0; bit < B; ++bit) {  
23.           if (S1[room] & (1 << bit)) {  
24.             dp[day + 1][room][bit] += (1.0 - dp[day][room][bit]) * 0.5;  
25.           } else {  
26.             dp[day + 1][room][bit] += dp[day][room][bit] * 0.5;  
27.           }  
28.           dp[day + 1][S2[room]][bit] += dp[day][room][bit] * 0.5;  
29.         }  
30.       }  
31.     }  
32.   
33.     double ret = 0;  
34.     for (int i = 0; i < B; ++i) {  
35.       ret += dp[K - 1][0][i] * (1 << i);  
36.     }  
37.     return ret;  
38.   }  
39. };  

class KingXMagicSpells {
public:
  double expectedNumber(vector <int> D, vector <int> S1, vector <int> S2, int K)
  {
    const int N = D.size();
    const int B = 30 + 1;
    ++K;

    double dp[K][N][B];
    fill(&dp[0][0][0], &dp[K - 1][N - 1][B], 0);
   
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < B; ++j) {
        dp[0][i][j] = (bool)(D[i] & (1 << j));
      }
    }
   
    // spell1 : xor
    // spell2 : move
    for (int day = 0; day + 1 < K; ++day) {
      for (int room = 0; room < N; ++room) {
        for (int bit = 0; bit < B; ++bit) {
          if (S1[room] & (1 << bit)) {
            dp[day + 1][room][bit] += (1.0 - dp[day][room][bit]) * 0.5;
          } else {
            dp[day + 1][room][bit] += dp[day][room][bit] * 0.5;
          }
          dp[day + 1][S2[room]][bit] += dp[day][room][bit] * 0.5;
        }
      }
    }

    double ret = 0;
    for (int i = 0; i < B; ++i) {
      ret += dp[K - 1][0][i] * (1 << i);
    }
    return ret;
  }
};