CodeForces 216C Hiring Staff

http://codeforces.com/problemset/problem/216/C

問題

従業員はn(2<=n<=1000)日働いた後m(1<=n<=m<=1000)日休むことを繰り返す。
つまり働いている日は、x日目に雇われたとして、

{d | ((x-1) + (d-1)) % (n+m) < n}

である。
この時、常に店に従業員がk(1<=k<=1000)人以上働いている状態にしたい。
ただし、店には鍵がかかっており、鍵は一つしか無く、従業員の誰かが持たないといけないが、働いている日のうちにしか他の従業員に鍵を渡すことはできない。
この時、それぞれの従業員の雇う日を調整して雇う従業員の数を少なくしたい。
最小の従業員数と、それぞれを雇う日を答えろ

回答

greedyに、雇わなければいけない日だったら雇えばいい。
雇わなければいけない日とは、その日働いている人の数がk未満、もしくは、今日から明日にかけて鍵が渡せない日である。
鍵が渡せるかどうかは、働いている前の日が渡せてればその日も大丈夫。これをn+m日目までやる

コード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cassert>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(__typeof(o.begin()) it = o.begin; it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;

const int N = 5000;
int d[N],f[N];
int main() {
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    mset(d,0);
    vi r;
    f[0]=1;
    rep(i,n+m) {
        while(d[i]<k||!f[i+1]){
            r.pb(i+1);
            reu(j, i, i+n+m) if((j - i)%(n+m) < n) {
                d[j] ++;
                f[j] |= f[j-1];
            }
        }
    }
    printf("%d\n", r.size());
    rep(i,r.size()) {
        printf("%d ", r[i]);
    }
    puts("");
}