ABC 124反省会

C++ AtCoder

初4完。でも今回正解者多かったし少し簡単だったかも…？

A. Buttons

A==Bの場合だけ気をつける。

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

int main(){
  int A, B;
  cin >> A >> B;
  int m = max(A, B);
  cout << (A == B ? m + m : m + m - 1) << endl;
}

B. Great Ocean View

最大の山の高さを保持しつつ、比較していけば良い。

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

int main(){
  int N;
  cin >> N;
  int h;
  cin >> h;
  int hmax = h;
  int cnt = 1;
  for (int i = 1; i < N; i++) {
    cin >> h;
    if (h >= hmax){
      hmax = h;
      cnt++;
    };
  }
  cout << cnt << endl;
}

C. Coloring Colorfully

一つ前と色が違えばカウントを増やす。

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

int main(){
  string S;
  cin >> S;
  int pre = S.at(0) - '0';
  int cnt = 0;
  int cur;
  for (int i = 1; i < S.size(); i++) {
    cur = S.at(i) - '0';
    if (pre == cur) {
      cnt++;
    };
    pre = !pre;
  }
  cout << cnt << endl;
}

D. Handstand

例えば入力例2は次のように見ることができる。

  • 1が3個
  • 0が1個
  • 1が1個
  • 0が1個
  • 1が1個
  • 0が1個
  • 1が2個
  • 0が2個
  • 1が2個

このような集計をした上で、各1からk*2+1個分先までの区間の「個数」が最大になる場合を探せば良い。もし文字列Sが0から始まったら、最初に「1が0個」があるとみなせば良い。これなら計算量はO(S.size())程度なので余裕で間に合う。

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

int main(){
  int N, K;
  cin >> N >> K;
  string S;
  cin >> S;
  vector<int> arr(N, 0);
  int idx = 0;
  char pre = '1';
  if (S.at(0) == '0') { // 0スタートだった
    idx++;
    arr.at(0) = 0; // 1が0個あることにする
    pre = '0';
  }
  for (int i = 0; i < N; i++) {
    if (pre == S.at(i)) {
      arr.at(idx)++;
    } else {
      idx++;
      arr.at(idx)++;
    }
    pre = S.at(i);    
  }
  
  int max_lensum = 0;
  for (int i = 0; i < idx+1; i = i+2) {
    int lensum = accumulate(arr.begin()+i, arr.begin() + min(i+2*K+1, idx+1), 0);
    if (lensum > max_lensum) max_lensum = lensum;
    if (i+2*K+1 > idx) break;
  }
  cout << max_lensum << endl;
}