Tenka1 Programmer Beginner Contest 2019 C問題

C - Stones

累積和で無事に解けたのでメモ

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

int main() {
  int N;
  string S;
  cin >> N >> S;
  
  vector<int> ha(N);
  
  // 配列内を 黒=1 白=0 に変換
  for (int i = 0; i < N; i++){
    if (S.at(i) == '.'){
      ha.at(i) = 0;
    } else {
      ha.at(i) = 1;
    }
  }
  
  // 累積和を求める
  vector<int> s(N + 1, 0);
  
  for (int i = 0; i < N; i++){
    s.at(i + 1) = s.at(i) + ha.at(i);
  }
  
  int min = N;
  for (int i = 0; i <= N; i++){
  // ans = 各境目に対してそれより左にある黒い石の個数とそれより右にある白い石の個数の和。境目を右端までもっていくため、 i <= N としている 
    int ans = s.at(i) + (N - i - s.at(N) + s.at(i));
    if (min > ans){
      min = ans;
    }
  }
     
  cout << min << endl;

}

他の人の解答見てたらかなりスマートなやつがあったので参考にして書いたやつ

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

int main() {
  int N;
  string S;
  cin >> N >> S;
  
  int count = 0;
  
  for (int i = 0; i < N; i++){
    if (S.at(i) == '.'){
     count++;
    }
  }
  
  int ans = count;
  
  for (int i = 0; i < N; i++){
    if (S.at(i) == '.'){
      count--;
    } else {
      count++;
    }
    ans = min(ans, count);
  }
     
  cout << ans << endl;

}

はえ～すっごい発想...