【競プロ精進日記】その他編＜１０＞Beginaid

本記事は管理人が競技プログラミングを始めたため，その精進日記としてログを取ったものです。アウトプットして積極的にモチベーションを上げていく作戦です。記事目次は以下をご覧ください。

内容は管理人の推測や恣意的な感想を大いに含みます。もし間違い等ありましたらご指摘ください。あくまでも参考程度にお願い致します。

【競プロ精進日記】目次まとめ ABC Atcoder Beginner Contestの過去問を解いています。最低限のコメントと一言が添えられています。 ...

その他の問題

過去問精選10問でその他の問題に分類されているものに取り組んでいきます。今回は累積和に関する問題（ABC 098 C）です。使用言語はc++です。

c++

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
using namespace std;

int main() {
  int N = 0;
  cin >> N;
  int cnt_w = 0, cnt_e = 0;
  int ans = pow(10, 6);
  vector<char> A(N);
  vector<int> S_W(N, 0);
  vector<int> S_E(N, 0);
  rep(i, N){
    cin >> A[i];
  }

  // それぞれの方角についての累積和をとる
  rep(i, N){
    if (A[i]=='W'){
      cnt_w++;
      S_W[i] = cnt_w;
      S_E[i] = cnt_e;
    }
    if (A[i]=='E'){
      cnt_e++;
      S_W[i] = cnt_w;
      S_E[i] = cnt_e;
    }
  }

  // 累積和を使って左側にいるWの人と右側にいるEの人を各リーダについて調べる
  rep(i, N){
    if (i==0) ans = min(ans, S_E[N-1] - S_E[i]);
    if (i==N-1) ans = min(ans, S_W[N-1]);
    else ans = min(ans, (S_W[i] + (S_E[N-1] - S_E[i])));
  }
  cout << ans << endl;
}

累積和感動しました！全てのリーダーについて毎回左側にいるWの人と右側にいるEの人の数を数えてしまっては，N^2オーダかかってしまい，今回のケースでは間に合いません。そこで，前もって各方角についての人数の累積和を計算しておけば，インデックスにアクセスするだけで各方角を向いている人数を取得することができます。非常に便利なテクニックですね。