AOJ 0307 Nisshinkan Marathon Club

問題概要, 制約

長いので省略。
ニッシン館マラソン部 | Aizu Online Judge

解法

シミュレーションをする。

シミュレーションする際には、それぞれの人のいる給水所、各給水所の空の容器の数、中身の入った容器の数を状態に持つと良い。

まず、時間を1ずつ進めていくことを考える。
それぞれの時間で、N人の人の位置を進めていく。
人iが現在いる位置をpos_iとすると、その人の次の位置は、(pos_i + p_i) % Rとなる。(p_iは人iのペースであり、Rは周回コースの長さを表す)

それぞれの人について、
時間が0でなければ、次の位置で空の容器の数を1増やす。
また、次の位置の中身の入った容器の数をチェックし、それが、1以上であれば1減らし、0であれば、新たに給水容器が必要になるので答えに1加算する。

上記が全て終了したら、その時間で溜まった空の容器の数を中身の入った容器の数に加算する。

以上を繰り返すと答えが出る。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int N, R, T;
    cin >> N >> R >> T;
    vector<int> p(N), cur(N);
    for (int i = 0; i < N; i++) {
        cin >> p[i];        
    }
     
    int res = 0;
    vector<int> e(R), f(R); 
    for (int i = 0; i < T; i++) {
        for (int j = 0; j < N; j++) {
            cur[j] = (cur[j] + p[j]) % R;
            if (i != 0) e[cur[j]]++;
            if (f[cur[j]] > 0) {
                f[cur[j]]--;
            } else {
                res++;
            }
        }
        for (int j = 0; j < R; j++) {
            f[j] += e[j];
            e[j] = 0;
        }
    }
    cout << res << endl;
    return 0;
}