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