🧩 AtCoder Beginner Contest 371

TayLockSeptember 14, 2024About 3 min

🧩 AtCoder Beginner Contest 371

# Info & Summary

Date: 2024-09-14
Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Prefix Sum	Binary Search & Prefix Sum	⭐🔥
E	number of subarrays	Math	🧠
F	lazy segment tree	lazy segment tree	🌀
G	Math	Math	🌀

Details

`Emoji`	`Label`	`Meaning`
⭐	Important	Problem is strategically useful or has reusable patterns
🔥	Must master	Classic problem or technique that appears often and is worth mastering
⚠️	Reattempt	You attempted but failed; worth reviewing and solving again
🧠	New to me	Introduced a new idea, technique, or pattern you hadn’t seen before
🛠️	Template	You built or improved a code template from solving this problem
🌀	Too hard now	Beyond current ability to understand/solve; revisit after more practice

📌 A - Jiro

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b, c;
    cin >> a >> b >> c;

    if (a == "<")
    {
        if (b == "<")
        {
            if (c == "<")
            {
                cout << 'B' << endl;
            }
            else
            {
                cout << 'C' << endl;
            }
        }
        else
        {
            cout << 'A' << endl;
        }
    }
    else
    {
        if (b == "<")
        {
            cout << 'A' << endl;
        }
        else
        {
            if (c == "<")
            {
                cout << 'C' << endl;
            }
            else
            {
                cout << 'B' << endl;
            }
        }
    }

    return 0;
}

📌 B - Taro

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<bool> ans(M);
    set<int> s;

    for (int i = 0; i < M; i++)
    {
        int a;
        char b;
        cin >> a >> b;

        if (b == 'M')
        {
            if (!s.count(a))
            {
                ans[i] = true;
            }
            s.insert(a);
        }
    }

    for (int i = 0; i < M; i++)
    {
        cout << (ans[i] ? "Yes" : " No") << endl;
    }

    return 0;
}

📌 C - Make Isomorphic

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    int Mg;
    cin >> Mg;

    vector<vector<int>> adjg(N, vector<int>(N, 0)), adjh(N, vector<int>(N, 0));
    for (int i = 0; i < Mg; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        adjg[u][v] = adjg[v][u] = 1;
    }

    int Mh;
    cin >> Mh;
    for (int i = 0; i < Mh; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        adjh[u][v] = adjh[v][u] = 1;
    }

    vector<vector<int>> c(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            cin >> c[i][j];
            c[j][i] = c[i][j];
        }
    }

    vector<int> perm(N);
    iota(perm.begin(), perm.end(), 0);

    int ans = 1e9;

    do
    {
        int cost = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                cost += c[perm[i]][perm[j]] * (adjg[i][j] != adjh[perm[i]][perm[j]]);
            }
        }

        ans = min(ans, cost);
        // cout << ans << endl;
    } while (next_permutation(perm.begin(), perm.end()));

    cout << ans << endl;

    return 0;
}

📌 D - 1D Country

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

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

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

    int Q;
    cin >> Q;

    for (int i = 0; i < Q; i++)
    {
        int l, r;
        cin >> l >> r;
        r++;

        auto il = lower_bound(X.begin(), X.end(), l) - X.begin();
        auto ir = lower_bound(X.begin(), X.end(), r) - X.begin();

        cout << pre[ir] - pre[il] << endl;
    }

    return 0;
}

📌 E - I Hate Sigma Problems

Tips

The answer is the number of subarrays containing 1 + the number of subarrays containing 1 + ... + the number of subarrays containing N

Tips

A common technique of combinatorics is to consider complementary events. Let's follow the custom and count the number of subarrays not containing $i$ , subtracting the sum from the all

For simplicity, let us insert $i$ to the both end of $A$

Then, the indices $x$ with $A_x = i$ arranged in ascending order are represented as $x = (x_0 = 0, x_1, ..., x_{C_i + 1} = N + 1)$

Then, the number of subarrays not containing $i$ equals:

the number of subarrays whose left end is $x_0 + 1$ or greater, and right end is $x_1 - 1$ or less
the number of subarrays whose left end is $x_0 + 1$ or greater, and right end is $x_1 - 1$ or less
...
the number of subarrays whose left end is $x_{C_i} + 1$ or greater, and right end is $x_{C_i + 1} - 1$ or less

This can be evaluated in $O(C_i)$ time

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> A(N);
    vector<int> lst(N, -1);

    long long ans = 0;

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

        ans += 1ll * (i - lst[A[i]]) * (lst[A[i]] + 1);

        lst[A[i]] = i;
    }

    for (int i = 0; i < N; i++)
    {
        ans += 1ll * (N - lst[i]) * (lst[i] + 1);
    }

    cout << ans << endl;

    return 0;
}

📌 F - Takahashi in Narrow Road

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Lexicographically Smallest Permutation

Warning

Hard Problems to Tackle Later

// TODO