nakashiiiの自由帳

自由に書きます

添字迷子にならないための練習

競プロ 累積和

以下の記事を見ながら練習したことのメモ。

rsk0315.hatenablog.com

現状、以下の記事内の

何も考えずに AC するまで [i] [i+1] [i-1] などを適当に書き換えるような癖はつけない方がいいと思います。

みたいなことが度々あるので、少しずつ書き改めていく。

※練習のため、上記の記事からの新規性はほぼゼロです。

累積和

実装

int main() {
  int n;
  cin >> n;

  // 元の配列
  vector<int> a(n);
  rep(i, 0, n) cin >> a[i];
  a.insert(a.begin(), 0);

  // 累積和
  vector<int> sum = a;
  rep(i, 1, n + 1) sum[i] += sum[i - 1];

  // 逆からの累積和
  vector<int> t(n + 1, sum[n]);
  rep(i, 1, n + 1) t[i] -= sum[i];

  // 階差
  vector<int> diff(n + 1);
  rep(i, 1, n + 1) diff[i] = a[i] - a[i - 1];

  // 階差から元の配列を復元
  vector<int> b(n + 1);
  b[0] = 0;
  rep(i, 1, n + 1) b[i] = b[i - 1] + diff[i];

  rep(i, 0, n + 1) cout << setw(2) << a[i] << " ";
  cout << ":元の配列" << endl;
  rep(i, 0, n + 1) cout << setw(2) << sum[i] << " ";
  cout << ":累積和" << endl;
  rep(i, 0, n + 1) cout << setw(2) << t[i] << " ";
  cout << ":逆からの累積和" << endl;
  rep(i, 0, n + 1) cout << setw(2) << sum[i] + t[i + 1] << " ";
  cout << ":a[i]を覗いた累積" << endl;
  rep(i, 0, n + 1) cout << setw(2) << diff[i] << " ";
  cout << ":階差" << endl;
  rep(i, 0, n + 1) cout << setw(2) << b[i] << " ";
  cout << ":階差から元の配列を復元" << endl;
}

ポイント

  • 元の配列の初項を 0 にする
  • 入力はいつもどおり, サイズ n で受け取れる. あとから最初の要素に 0 を insert
  • 累積和の配列は a をコピーするだけなので, 長さは考えなくていい
  • 累積和の計算は前から順番に走査しながら足していくだけ
  • 区間和は半開区間で求まる. s[i] は 区間[l,r)の和
  • つまり, 0-indexd の[l, r]の累積和は, [l, r+1)なので, sum[r+1] - sum[l] で求まる
  • 階差も初項 0 で考える

練習問題の提出

二分探索

（練習したら書く）

尺取法

（練習したら書く）