AtCoder ABC409 振り返り #C++

はじめに

ABC409に参加したので振り返ります。
結果は2完でした。
今回は本番で解けた2問＋C問題についてまとめます。

A - Conflict

解法

文字列の比較ですね。
本番では両方x（欲しがっていない）の場合でも出力がYesとなるようにしていたので1度WAが出ました（もったない…）。

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

int main() {
    int N;
    string T, A;
    cin >> N >> T >> A;

    for (int i = 0; i < N; i++) {
        if (T[i] == A[i] && T[i] != 'x') {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

B - Citation

解法

まず、配列をソートして降順に直します。降順の理由は大きな数から探していくことで効率化を図るためです。
その後、配列のX番目の要素がX回以上現れるかを判別します。

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

int main() {
    int N;
    cin >> N;

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

    // 配列をソート（降順）
    sort(A.begin(), A.end(), greater<int>());

    for (int x = N; x >= 1; --x) {
        if (A[x - 1] >= x) {
            cout << x << endl;
            return 0;
        }
    }
    cout << 0 << endl;
}

C - Equilateral Triangle

解法

円周上にある点がつくる正三角形の個数を求める問題でした。円周の長さLなので、各点の距離がL/3の場合をカウントしていきます

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

int main() {
    long long N, L;
    cin >> N >> L;

    if (L % 3 != 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<long long> d(N - 1);
    for (int i = 0; i < N - 1; ++i) {
        cin >> d[i];
    }

    vector<long long> P(N);
    P[0] = 0;
    for (int i = 0; i < N - 1; ++i) {
        P[i + 1] = (P[i] + d[i]) % L;
    }

    std::map<long long, int> counts;
    for (long long pos : P) {
        counts[pos]++;
    }

    std::vector<long long> unique_positions;
    for (auto const& [pos, count] : counts) {
        unique_positions.push_back(pos);
    }

    long long third_L = L / 3;
    long long two_thirds_L = 2 * L / 3;
    long long ans = 0;

    for (long long p_a : unique_positions) {
        long long p_b = (p_a + third_L) % L;
        long long p_c = (p_a + two_thirds_L) % L;

        if (counts.count(p_b) && counts.count(p_c)) {
            ans += (long long)counts[p_a] * counts[p_b] * counts[p_c];
        }
    }
    cout << ans / 3 << endl;
}

おわりに

ソートの類似問題をたくさん解きたいです。