ABC 124

競技プログラミングは申請書からの逃避に役立つ。

A

A - Buttons

  • 1回目はABの大きい方の枚数のコインが手に入る
  • 2回目は縮小したボタンと押さなかった方のボタンの大きい方の枚数のコインが手に入る
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  int ans = max(A, B) + ((A > B) ? max(A-1, B) : max(A, B-1));
  cout << ans << endl;
}

Submission #5114332 - AtCoder Beginner Contest 124

B

B - Great Ocean View

  • i 番目までの旅館で最も高い旅館の高さを持っておき、それ以上の高さだったら眺められる旅館の数を1増やす
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
 
using namespace std;
 
int main() {
  int N, H;
  cin >> N;
  int ans = 0;
  int highest = numeric_limits<int>::min();
  REP(i, N) {
    cin >> H;
    if(H >= highest) {
      highest = H;
      ans++;
    }
  }
  cout << ans << endl;
}

Submission #5114368 - AtCoder Beginner Contest 124

C

C - Coloring Colorfully

  • 0101010.... または 1010101... のどちらかにしかならないので、両方とのハミング距離を計算して小さい方
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
 
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int ans01 = 0;
  char c = '0';
  REP(i, S.size()) {
    if(S[i] != c) ans01++;
    c = (c == '0' ? '1' : '0');
  }
  c = '1';
  int ans10 = 0;
  REP(i, S.size()) {
    if(S[i] != c) ans10++;
    c = (c == '0' ? '1' : '0');
  }
  cout << min(ans01, ans10) << endl;
}

Submission #5114399 - AtCoder Beginner Contest 124

D

D - Handstand

  • 自力でやったらTLEだったので解説を見た
  • 01 が切り替わるところの位置を持っておいて、そこだけ調べる
  • その位置の文字が0なら2K個先の切り替わり位置、1なら2K+1個先の切り替わり位置との差を取ればその位置からスタートした最も長い連続逆立ち人数がO(1)で求まるからO(N)
  • これに気が付かなくていちいち数えていたのでO(N^2)になった
  • N <= 10^5 のときはO(N^2)だと間に合わないという認識をちゃんと持つ必要がある
  • 解説が1-indexedなので0-indexedにするために1を足したり引いたりしている
#include <bits/stdc++.h>

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;

using namespace std;

int main() {
  int N, K;
  string S;
  cin >> N >> K >> S;
  vector<int> I({1});
  FOR(i, 1, N) {
    if (S[i] != S[i - 1]) I.push_back(i + 1);
  }

  int ans = 0;
  int r = I.size();
  REP(k, r) {
    int cnt;
    if (S[I[k] - 1] == '0') {
      cnt = (k + 2 * K >= r ? N + 1 : I[k + 2 * K]) - I[k];
    } else {
      cnt = (k + 2 * K + 1 >= r ? N + 1 : I[k + 2 * K + 1]) - I[k];
    }
    ans = max(ans, cnt);
  }
  cout << ans << endl;
}

Submission #5115219 - AtCoder Beginner Contest 124

計算量オーダーの求め方を総整理! 〜 どこから log が出て来るか 〜 - Qiita によればループの回数を10^810^9回に抑えるようにする必要があるとのこと。以後意識する。