AtCoder Beginer Contest 384 備忘録

• 今後競技プログラミングを精進していくための個人的な備忘録
• コンテスト中は3完、D問題解けなかったので解説みて理解したことをまとめた

A - aaaadaa

• 問題文の通りやるだけ

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

int main() {
    int N;
    char c1, c2;
    string S;
    cin >> N >> c1 >> c2 >> S;
    for (int i = 0; i < N; i++) {
        if(S[i] != c1) {
            cout << c2;
        } else {
            cout << S[i];
        }
    }
    cout << endl;
}

B - ARC Division

• 基本的にfor文でN回順にシミュレーションしていくだけ
• 条件分岐は問題文にある通りにすればいい。レートを加算する処理を共通化するために下記ではすこし条件を調整

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

int main() {
    int N, R;
    cin >> N >> R;
    int D, A;
    int rate = R;
    for (int i = 0; i < N; i++) {
        cin >> D >> A;
        if (D == 1) {
            if (rate < 1600 || rate >= 2800) continue;
        } else {
            if (rate < 1200 || rate >= 2400) continue;
        }
        rate += A;
    }
    cout << rate << endl;
}

C - Perfect Standings

• 文字列の全通りを列挙したかったのでbit全探索をつかった
• スコアの大きいもの順に並べる時にはよくやるスコアをマイナスにして昇順ソートした

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

int main() {
    vector<int> scores(5);
    for (int i = 0; i < 5; i++) {
        cin >> scores[i];
    }
    vector<char> chars = {'A', 'B', 'C', 'D', 'E'};
    vector<pair<int, string>> result;

    for (int bit = 1; bit < (1 << 5); bit++) {
        string key = "";
        int sum = 0;
        for (int i = 1; i < 5; i++) {
            if (!(bit & (1 << i))) {
                key += chars[i];
                sum += scores[i];
            }
        }

        result.push_back(make_pair(-sum, key));
    }
    sort(result.begin(), result.end());

    for (auto v : result) {
        cout << v.second << endl;
    }
}

D - Repeated Sequence

• なんとなく尺取りっぽいなとは思いつつ解けずにコンテスト終わった
• 解説を見てChatGPTにも色々噛み砕いて教えてもらってようやく理解できた
• 先頭N項のA1~ANの配列の合計がS以下の場合は、Aの配列からSと一致する部分和が存在するかを探索すれば良さそうなことがわかる
• 一方Sより大きい場合は、無限数列Aの中に部分和としてSが存在するなら、SをAの配列の合計で割ったあまりの値がAの1~2Nの中に部分和として存在することになる
• Aの範囲が1~2Nなのは連続する部分和を網羅するため
• 配列の中から素直に部分和を探そうとするとO(N^2)かかってしまい今回の制約では間に合わない。なので今回は尺取り法を使ってO(N)で条件に合う部分和を探索させる方法にした

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

int main() {
    long long N, S;
    cin >> N >> S;
    vector<long long> A(N);
    long long sum = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sum += A[i];
    }

    S %= sum;

    vector<long long> B(2 * N);
    for (int i = 0; i < 2 * N; i++) B[i] = A[i % N];

    long long sum = 0;
    int right = 0;
    for (int left = 0; left < N; ++left) {
        while (right < 2 * N && sum + B[right] <= S) {
            sum += B[right];
            ++right;
        }

        if (sum == S) {
            cout << "Yes" << endl;
            return 0;
        }

        sum -= B[left];
    }
    cout << "No" << endl;
    return 0;
}