PAST4I
from 第四回 アルゴリズム実技検定
PAST4I
考えたこと
やっと巨大なNの問題
円周のRange Sumが最大になるところを探す
2倍にして累積和
それでも始点と終点が自由だと二乗のオーダー
しゃくとり法をする
イコールの時にどっちをすればいい？
縮める？
イコールの時は答えが0だから終わっていいのか
通ったのでいいや
pythondef solve(N, AS):
import sys
INF = sys.maxsize
from itertools import accumulate
acc = list(accumulate(AS + AS)) + [0]
def rangeSum(start, end):
return acc[end - 1] - acc[start - 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"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]