F - Divide the Cake Editorial
by 
MtSaka
この解説では以下の \(2\) つの部分に分けて解説します。
- 高橋君の勝利条件を求める
- 実際に高橋君が勝利するために選ぶ切込みを求める
1. 高橋君の勝利条件を求める
高橋君が切り込み \(i\) を選んだ時の勝敗の判定について考えましょう。以降、数列 \(A\) の平均\((\frac{\sum_{k=1}^{N}A_k}{N})\) を \(\mu\) とします。
実は、切り込み \(i\) から時計回りに各切り込みまで見たときに、すべての切込みについて \(1\) ピースあたりのイチゴの平均値が \(\mu\) 以上である時のみ高橋君は勝てます。
高橋君と青木君で分け合うイチゴの個数の合計は常に一定であり、またそれらを常に \(N\) ピースで分け合うため \(2\) 人の間の \(1\) ピースあたりのイチゴの個数の平均は一定です。よって、高橋君の \(1\) ピースあたりのイチゴの個数の平均値が \(\mu\) 以上であるとき、青木君の \(1\) ピースあたりの平均値は \(\mu\) 以下になります。逆もまた然りです。
2. 高橋君が勝利するために選ぶ切込みを求める
先ほど求めた条件より、
\(\sum_{k=i}^{i}(A_k-\mu) \geq 0\)
\( \sum_{k=i}^{i+1}(A_k-\mu) \geq 0\)
\(\vdots\)
\( \sum_{k=i}^{N}(A_k-\mu)\geq 0\)
\(\sum_{k=i}^{N}(A_k-\mu) +\sum_{k=1}^{1}(A_k-\mu) \geq 0\)
\(\vdots\)
\(\sum_{k=i}^{N}(A_k-\mu)+\sum_{k=1}^{i-1}(A_k-\mu) \geq0\)
をすべて満たす必要があります。(厳密には \(i=1\) の時は少し異なります)
これは、累積和などのテクニックを用いて判定することができます。
具体的には、\(S_i=\sum_{k=1}^{i-1}(A_k-\mu)\) となる長さ \(N+1\) の数列 \(S\) を考えます。
このとき、高橋君が切込み\(i\) を選んだ時、\(S_i\) が\(S\) の最小値と等しいとき、またこの時に限り勝利条件を満たすことができます。逆に、常に高橋君が勝利することができる切込みが存在します。
詳細
先ほどの 式を整理すると、\(i<j \leq N\) を満たすすべての \(j\) について、\(S_j-S_i \geq 0\) を、\(1 \leq j < i\) を満たすすべての \(j\) について、\(S_{N+1}-S_i+S_j \geq 0\) を満たすとき、高橋君は勝利します。
\(S_{N+1}=0\) であることを考えると、つまりはすべての \(1 \leq j \leq N,i \neq j\) を満たす \(j\) について、\(S_i\leq S_j\) を満たすとき高橋君は勝利します。またこの時にのみ勝利します。
よって、数列 \(S\) を求めて最小値およびその位置を求めることでこの問題が解けます。全体の時間計算量および空間計算量は \(O(N)\) となります。
別解
実は今回のような平均値の特徴を利用しなくても円環を考え、長さ \(2N+1\) の累積和を構築して条件を整理することで区間最小値クエリなどを求める問題に帰着できます。
区間最小値クエリは、セグメント木などを用いて \(O(N\log N)\) で求めることが可能です。今回の場合、区間の長さが固定なのでスライド最小値を用いて本解と同様の時間計算量 \(O(N)\) を達成する解になります。
実装例(C++):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> a(n);
for (auto& e : a) cin >> e;
vector<ll> sum(2 * n + 1);
for (int i = 0; i < n; ++i) {
sum[i + 1] = sum[i] + a[i];
}
for (int i = n; i < 2 * n; ++i) {
sum[i + 1] = sum[i] + a[i - n];
}
const ll s = sum[n];
for (int i = 0; i < 2 * n; ++i) {
sum[i] = sum[i] * n - s * i;
}
deque<int> idx;
for (int i = 1; i < n; ++i) {
while (idx.size() && sum[i] <= sum[idx.back()]) {
idx.pop_back();
}
idx.push_back(i);
}
for (int i = 0; i < n; ++i) {
const ll mi = sum[idx.front()];
if (mi >= sum[i]) {
cout << i + 1 << endl;
return 0;
}
while (idx.size() && sum[i + n] <= sum[idx.back()]) {
idx.pop_back();
}
idx.push_back(i + n);
if (idx.front() == i + 1) {
idx.pop_front();
}
}
}
実装例 (C++):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> a(n);
for (auto& e : a) cin >> e;
vector<ll> sum(n + 1);
for (int i = 0; i < n; ++i) {
sum[i + 1] = sum[i] + a[i];
}
const ll s = sum[n];
for (int i = 0; i <= n; ++i) {
sum[i] = sum[i] * n - s * i;
}
cout << (min_element(sum.begin(), sum.end()) - sum.begin()) + 1 << endl;
}
posted:
last update: