[yukicoder] No. 1219 Mancala Combo

2020年9月17日2020年12月13日

問題

方針

配列の末尾から実際にシミュレーションしていきます。操作を行った回数を \( t \) とすると、\( i \) 番目のマスでは、\( A_i + t \) 個の石があり、操作回数は

\[ t \leftarrow t + \left \lfloor \dfrac{A_i + t}{t} \right \rfloor \]

と更新されます。したがって、\( (A_i + t) \bmod i = 0 \) である必要があります。\( A_i + t > i \) だとしても、\( A_i = i \) のときに石を運ぶことができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    ll A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    ll t = 0;
    for (int i = N - 1; i >= 1; i--) {
        if ((A[i] + t) % (i + 1) != 0) {
            cout << "No\n";
            return 0;
        }
        t += (A[i] + t) / (i + 1);
    }
    cout << "Yes\n";
    return 0;
}