Chef And The Patents [February Challenge 2018 B]

https://www.codechef.com/FEB18/problems/CHEFPTNT

N個の特許とK人の従業員がいる。
以下のルールで、1月からM月までの間でN個の特許を処理できるか判定せよ。

• K人の従業員は奇数月、偶数月のどちらかでだけ働ける
• 一度に最大X人までしか1月に働けない
• １人1月に1特許処理できる
• K人はある月でしか働けない（1月しか割り当てられない）

解法

https://www.codechef.com/viewsolution/17299404

各月でシミュレートする。
シミュレート前に従業員の働ける月の偶奇で数えておく。
cnt[0] := 偶数月働ける人数
cnt[1] := 奇数月働ける人数
なるべく、働かせるように貪欲に人員を割り当てていく。
これでN特許を超えれば"yes"、超えないなら"no"

int N, M, X, K; string S;
//---------------------------------------------------------------------------------------------------
#define yes "yes"
#define no "no"
string solve() {
    cin >> N >> M >> X >> K >> S;
 
    int cnt[2] = { 0, 0 };
    fore(c, S) {
        if (c == 'E') cnt[0]++;
        else cnt[1]++;
    }
 
    ll sm = 0;
    rep(i, 1, M + 1) {
        sm += min(cnt[i % 2], X);
        cnt[i % 2] = max(0, cnt[i % 2] - X);
    }
 
    if (N <= sm) return yes;
    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T;  cin >> T;
    rep(t, 0, T) printf("%s\n", solve().c_str());
}