[AGC037] C - Numbers on a Circle
[Q] https://atcoder.jp/contests/agc037/tasks/agc037_c
1. BからAを作ることを考える。B[i]からB[i-1]とB[i+1]を引けばいい。
2. Bの大きい値から処理すれば最速になりそう
3. 愚直(TLE)
4. B[] = 1,10000001,1 の時がやばい。
5. 減算回数をまとめて実施すればよかった。
Q. -1になる判定は？
A. maxBの両隣を引いたときに、Aを下回ってしまうなら永遠にできない。
減算回数<=0のときに-1と判定する場合、入力時点でA==Bのpushをしてはいけない(WA)
実装
ll N;
ll A[200020];
ll B[200020];
int main() {
cincout();
cin >> N;
rep(i, N) cin >> A[i];
priority_queue<pll> Q; // B, id
rep(i, N) {
cin >> B[i];
if (B[i] != A[i]){ // もうAと一致しているならいれない
Q.push({B[i], i});
}
}
// Bが大きい値から処理を繰り返す
ll ans = 0;
while (!Q.empty()) {
auto [b, id] = Q.top();
Q.pop();
ll pid = (id - 1 + N) % N;
ll nid = (id + 1) % N;
ll dis = B[pid] + B[nid];
ll cnts = (b - A[id]) / dis;
if (cnts <= 0) { // 変更できないパターンのため詰み
cout << -1 << endl;
return 0;
}
ans += cnts;
b -= dis * cnts;
B[id] = b;
if (b == A[id]) continue;
Q.push({b, id});
}
cout << ans << endl;
}