この手の嘘解法は好きなのだが、yukicoderだったら実質WAだし、そうでなくてもペナルティが厳しい。

ところで、最初に常にYESを投げてYES NOの偏り$p$を計測してそれに応じて投げれば最初の計測と合わせてもちょっと有利になるというのを思い付いたので使っていきたい。 例えば、今回私の実装を投げたら$3$TLEだったので、YES NOを$\frac{1}{2}$ずつで返すと期待値$8$回だが、このテクを使えば最初の計測で外した場合(なお今回は常にYESが正解だった)でも$1 + \frac{3^3}{2^2\cdot 1} = 7.75$と有利。

solution

嘘解法。貪欲 + 定数倍高速化 + 時間計測乱択。貪欲部分は$\frac{N\sum A_i}{{}_NC_2}$で$O(\max A_i)$。

貪欲は$i \in \{ i \mid A_i = \min A_j \}$を始点として愚直に$N$回引くことを繰り返すもの。 未証明だが、十分数の乱択ケースで検証したのでたぶん大丈夫。

定数倍高速化について。 (i+j)%nをi+j<n?i+j:i+j-nにして剰余を除去すること、clangを使ってSIMDによる最適化をしてもらうことが重要。 ${}_NC_2 \nmod \sum A_i$なら即座にNOを返すのも重要。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
#include <chrono>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
bool solve(vector<int> & a) {
    auto start = chrono::system_clock::now();
    int n = a.size();
    const ll nc2 = n*(n+1ll)/2;
    const ll sum_a = whole(accumulate, a, 0ll);
    if (sum_a % nc2 != 0) return false;
    repeat (q, sum_a / nc2) {
        int i = whole(min_element, a) - a.begin();
        if (a[i] <= 0) break;
        repeat      (k,i)   a[k] -= (n+k)-i+1;
        repeat_from (k,i,n) a[k] -=    k -i+1;
        if (q % 10 == 0) {
            auto end = chrono::system_clock::now();
            double t = chrono::duration<double>(end - start).count();
            if (t > 1.9) {
                random_device device;
                uniform_int_distribution<int> dist(0, 1);
                return dist(device);
            }
        }
    }
    return whole(count, a, 0) == n;
}
int main() {
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    cout << (solve(a) ? "YES" : "NO") << endl;
    return 0;
}