PAST4I
from 第四回 アルゴリズム実技検定
PAST4I
I - ピザ
考えたこと
やっと巨大なNの問題
円周のRange Sumが最大になるところを探す
2倍にして累積和
それでも始点と終点が自由だと二乗のオーダー
しゃくとり法をする
イコールの時にどっちをすればいい？
縮める？
イコールの時は答えが0だから終わっていいのか
通ったのでいいや
code:python
def solve(N, AS):
import sys
INF = sys.maxsize
from itertools import accumulate
acc = list(accumulate(AS + AS)) + 0
def rangeSum(start, end):
return accend - 1 - accstart - 1
start = 0
end = 1
ret = INF
total = rangeSum(0, N)
while True:
x = rangeSum(start, end)
y = total - x
d = x - y
ret = min(abs(d), ret)
if d < 0:
if end == 2 * N - 1:
break
end += 1
else:
start += 1
return ret