SRM 513 Div2 Medium YetAnotherIncredibleMachine

問題

N個の板を配置する,i番目の板はplatformLength[i]の長さを持ち,x座標が必ずplatformMount[i]に接するように設置する.M個のballを上から落とす.i番目のballはx座標balls[i]から落とす.
この時ballが板にぶつからないように設置する時の場合の数を答えよ.

解答

各板の設置は他の板の設置に影響しないのでそれぞれ独立に考えることが出来る.よって各板のぶつからないようにする場合の数を求め,それをかけあわせれば良い.

class YetAnotherIncredibleMachine
{
public:
  int countWays(vector <int> platformMount, vector <int> platformLength, vector <int> balls)
    {
      long long dp[50] = {};
      long long mod = 1000000009;
      int i, j, k;
      int n = platformMount.size();
      int m = balls.size();
      for(i = 0; i < n; i++){
        int count = 0;
        for(j = platformMount[i] - platformLength[i]; j <= platformMount[i]; j++){
          bool valid = true;
          for(k = 0; k < m; k++){
            if (j <= balls[k] && balls[k] <= j+platformLength[i]){
              valid = false;
              break;
            }
          }
          if (valid) count++;
        }
        if (i == 0) dp[i] = count;
        else dp[i] = (dp[i-1] * count) % mod;
      }
      return dp[n-1];
    }
};