Atcoder 典型90問 076 Cake Cut

問題

atcoder.jp

公式解説を見ても右側の例が何を言ってるのか理解できない...

解き方

まずは、問題が円形の要素であること。
これは単純に要素を*2するだけなのでわかる。
次に隣り合う要素の和が全体和の÷10と一致するか？というところ。

累積和

累積和が登場します。

mankozooyork.hatenablog.com

まずはそれぞれの要素を足し合わせる累積和を作成する。

そうすると、1, 2がTargetである3となることがわかりますが、
累積和を求めておけば、（そもそも累積和はある範囲(x - y)の和を簡単に求めるもの）
どことどこを引けばTargetになっているのかわかります。
実装としては、現状の累積和 + Target - 現在の累積和 としてTargetにマッチすればよいです.
しかし、これを実際に全探索しようとすると、O(N²)になってしまうので、
早くするために二分探索を使って累積和 + Targetに近いindexを取得して早くするってわけのようです。
これでO(logN)Nにできるってわけですね、、
あと、二分探索はsort済arrayに行うのが常ですが、累積和に対しては元々ソートされているものになるので応用可能なようです。
累積和 + 二分探索は覚えておいて良さげ。

累積和の問題がでてきても自力で解ける気がまだまだしませんw

サンプル

n = int(input())
a = list(map(int, input().split()))
import bisect

#円系を2周分の配列として作成
a.extend(a)

#累積和を作成
c_sum = [0] * len(a)
c_sum[0] = a[0]
for i in range(len(a)-1):
    c_sum[i+1] = c_sum[i] + a[i+1]

# コーナーケース; そもそもinputのsumが10で割れない場合（整数でない場合）は"No"でよい
# ちなみにこのロジックがないとACになりません、、
if c_sum[n-1] % 10 != 0:
    exit(print("No"))

#Target
target = c_sum[n-1] // 10

for i in range(n):
    #二分探索、これもbisect_leftじゃないとACなりません
    idx = bisect.bisect_left(c_sum, target + c_sum[i])
    if c_sum[idx] - c_sum[i] == target:
        exit(print("Yes"))
   
print("No")