SRM 513 YetAnotherIncredibleMachine

問題概要

動かせる床の長さと範囲が与えられる。
ボールが降ってくる座標が与えられる。
ボールにあたらないようにする配置の数を求めよ。

解法

全探索。
それぞれの床の置き方を全部ためして、掛け合わせる。
けど、へんな実装してしまった。本番で気づきたかった。

ソース

#include <set>
#include <iostream>
#include <vector>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;

typedef long long lli;

const lli MOD = 1000000009;

set<int> B;

lli solve(int pos, int len){
  lli last, ret;
  last = pos - len -1;
  ret = 0;
  REP(i, pos - len, pos + len+1){
    if(B.find(i) != B.end()){
      last = i;
      continue;
    }
    if(i - last >= len + 1){
      ret++;
      ret %= MOD;
    }
  }
  return ret;
}

class YetAnotherIncredibleMachine {
public:
  int countWays(vector <int> pos, vector <int> len, vector <int> balls) {
    B.clear();
    FOR(it, balls){
      B.insert(*it);
    }
    lli ret = 1;
    rep(i, pos.size()){
      ret *= solve(pos[i], len[i]);
      ret %= MOD;
    }
    return ret;
  }
};