競プロチャレンジ供養会場: AtCoder Regular Contest 119 C - ARC Wrecker 2

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1354 (記事作成時点)

供養

解法

• $\lbrack l, r \rbrack$ が解体可能なとき、$\lbrack l, r \rbrack$ の奇数番目のビルの高さの和と偶数番目のビルの高さの和が等しい
• よって、奇数番目のビルの高さの和と偶数番目のビルの高さの和が等しくなるような区間を探す
• $B_{0} = 0, B_{i} = \sum_{j = 1}^{i} (-1)^{j}A_{j}$ としたとき、$B_{l - 1} = B_{r}$ ならば $\lbrack l, r \rbrack$ は解体可能
• $B_{i}$ の値と個数をカウントして、同値の組み合わせの和をとればよい

実装

計算量は $O(N)$

公式解説

躓いた点

• 成立条件に気が付かなかった