[AtCoder] ABC 130 D – Enough Array

問題

方針

尺取り法

連続する部分列に関する問題は尺取り法の適用を考えます。尺取り法については、しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめを参照してください。

尺取り法の左側のインデックスを \( l \)、右側のインデックスを \( r \) とします。ここで、\( 1 \leq l \leq N\), \( l \leq r \leq N \) とします。\( f(l, r) \) を

\[f(l, r) = \sum_{i = l}^{r} a_i\]

とします。\( l \) を固定した時、\( f(l, r) < K \) を満たす最大の \( r \) を \( r_{l}^*\) とします。

\( f(l, r_{l}^* + 1) \geq K \) を満たすとき、条件を満たす部分列の数は、\( N – r_{l}^* \) となります。次に、\( l + 1 \) のとき、\( f(l+1, r) \) について、\( r_{l+1}^{*} \) の候補は、\( r_{l}^* + 1\leq r \leq N\) となります。

コード

提出したコード