「みんなのプロコン 2018」E: グラフの問題

https://yahoo-procon2018-qual.contest.atcoder.jp/tasks/yahoo_procon2018_qual_e

検索するとこんなのが出てきます。

ここにある式をそのまま使えばいいです。

1を足す時でも式で考えれば一番小さい次数を1上げれば良いことがわかります。

ただ式を勘違いして読んで無限にWAを出した…流石に不注意がすぎる。

int N;
ll A[MAX_N];
ll S[MAX_N], SD[MAX_N];

ll f(ll at) {
	ll lv = -1, rv = N;
	while(rv - lv > 1) {
		int m = (lv + rv) / 2;
		if(A[m] < at) rv = m;
		else lv = m;
	}
	ll v = max(rv, at);
	ll res = (S[N] - S[v]) + (v - at) * at;
	return res;
}

bool ok() {
	sort(A, A + N, greater<ll>());

	memset(S, 0, sizeof(S));
	memset(SD, 0, sizeof(SD));

	rep(i, 0, N) S[i + 1] = S[i] + A[i];

	rep(i, 0, N) {
		if((S[i + 1] - S[0]) - f(i + 1) > 1LL * i * (i + 1)) {
			return false;
		}
	}
	return true;
}

int sub_solve() {
	ll s = 0;
	rep(i, 0, N) s += A[i];
	if(s % 2 == 0) {
		if(ok()) return 0;
		else return 2;
	}
	else {
		A[0]++;
		if(ok()) return 1;
		else return 2;
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	int s = sub_solve();
	if(s == 0) cout << "YES\n";
	else if(s == 1) cout << "NO\n";
	else cout << "ABSOLUTELY NO\n";
}