[AtCoder] ABC 130 D – Enough Array

2019年6月17日

問題

方針

尺取り法

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

尺取り法の左側のインデックスを \( 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\) となります。

コード

提出したコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll b[100001]{};
ll f(int l, int r) {
  return b[r] - b[l - 1];
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N, K;
  cin >> N >> K;
  ll a[N];
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < N; i++) {
    b[i + 1] += b[i] + a[i];
  }
  int r = 1;
  ll cnt = 0;
  for (int l = 1; l <= N; l++) {
    while(f(l, r) < K && r <= N) r++;
    if (r > N) break;
    if(f(l, r) >= K) {
      cnt += N - r + 1;
    }
  }
  cout << cnt << "\n";
  return 0;
}