AtCoder Beginner Contest 124

結果

　29分56秒で全完。137位だった。簡単なセットだったのでなかなか順位は伸びず。

A問題

　std::maxにinitializer_listを渡す(ということをしているのだという理解で良いはず)。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll A, B;
    cin >> A >> B;
    cout << max({ 2 * A - 1, A + B, 2 * B - 1 }) << endl;
}

B問題

　最大値を保存しておけば良いのだなと。こういうの入力取る時にそのまま計算できそうだなと思うんだけど手癖で分けでしまう。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<ll> H(N);
    for (ll i = 0; i < N; i++) {
        cin >> H[i];
    }

    ll ans = 0, h = 0;
    for (ll i = 0; i < N; i++) {
        if (H[i] >= h) {
            ans++;
            h = H[i];
        }
    }

    cout << ans << endl;
}

C問題

　黒始まりか白始まりかを2通り試すだけでメモを取るまでもなく。しかしelseを使わず無駄な書き方しているなぁ。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string S;
    cin >> S;

    ll ans1 = 0, ans2 = 0;
    for (ll i = 0; i < S.size(); i++) {
        if (S[i] == ('0' + i % 2)) {
            ans1++;
        }
        if (S[i] == ('0' + (i + 1) % 2)) {
            ans2++;
        }
    }

    cout << min(ans1, ans2) << endl;
}

D問題

1. 問題の性質を少し考える
2. DPを疑う
3. 二分探索を疑う
4. 問題の性質から答えに気づく

　という感じの流れだった。二分探索を考えようと思ってメモに「二分探索を考える」って書いた瞬間に「(選ぶ) (個)はかためた方が良い」っていうところに気づいて単純なだということがわかった。しかし累積和で脳が混乱してしまうタイプの人間なのでわりと実装に苦労した。フリップする個の区間について、もともとである区間はその両脇まで取らないといけないというところをもう少し道筋よく考えられたら良かったが。

　0,1をまたぐような区間のフリップはダメだと勝手に思い込んでいたけど別に操作としては可能だということに実装途中で気づいて焦ったが、そういう取り方は無駄なので考えなくて良さそうと思った。証明はしていないのでただの勘。WAが出たらちゃんと考えなおそうと思って出して通ったのでそれで良しの精神。

　尺取り法はだいぶ馴染みがないので全然思い浮かばない。実装したことも1,2回しかない気がする。二分探索でもいけるのか。まぁそうかな。やり方はいろいろありそう。解法が手広く見えたら良さそうだが、高望みでもある。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    vector<ll> a[2];

    char target = '0';
    ll num = 0;
    for (char c : S) {
        if (c == target) {
            num++;
        } else {
            a[target - '0'].push_back(num);
            num = 1;
            target = (target == '0' ? '1' : '0');
        }
    }
    a[target - '0'].push_back(num);

    if (a[0].size() <= K) {
        cout << N << endl;
        return 0;
    }

    if (a[0].size() != a[1].size()) {
        a[1].push_back(0);
    }

    //累積和
    vector<vector<ll>> sum(2, vector<ll>(a[0].size() + 1, 0));
    for (ll i = 0; i < a[0].size(); i++) {
        sum[0][i + 1] = sum[0][i] + a[0][i];
        sum[1][i + 1] = sum[1][i] + a[1][i];
    }

    ll ans = 0;
    for (ll i = 0; i <= a[0].size() - K; i++) {
        ans = max(ans, sum[0][i + K] - sum[0][i] + sum[1][i + K] - (i == 0 ? 0 : sum[1][i - 1]));
    }
    cout << ans << endl;
}