Análise dos Prbolemas do AtCoder Beginner Contest 371

Este artigo explora as soluções técnicas dos problemas do AtCoder Beginner Contest 371, com foco em algoritmos e estruturas de dados.

Problema A

O Problema A envolve determinar o segundo maior entre três indivíduos, A, B e C, com base em desigualdades fornecidas. A abordagem eficiente consiste em avaliar as condições de desigualdade para estabelecer a ordem de classificação.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    char relAB, relAC, relBC;
    cin >> relAB >> relAC >> relBC;
    
    char persons[] = {'A', 'B', 'C'};
    int ranks[] = {1, 2, 3};
    
    do {
        int rankA = ranks[0], rankB = ranks[1], rankC = ranks[2];
        bool isValid = true;
        
        if (relAB == '<' && rankA >= rankB) isValid = false;
        if (relAB == '>' && rankA <= rankB) isValid = false;
        if (relAC == '<' && rankA >= rankC) isValid = false;
        if (relAC == '>' && rankA <= rankC) isValid = false;
        if (relBC == '<' && rankB >= rankC) isValid = false;
        if (relBC == '>' && rankB <= rankC) isValid = false;
        
        if (isValid) {
            for (int i = 0; i < 3; i++) {
                if (ranks[i] == 2) {
                    cout << persons[i] << endl;
                    return 0;
                }
            }
        }
    } while (next_permutation(ranks, ranks+3));
    
    return 0;
}

Problema B

No Problema B, é necessário registrar o filho mais velho durante consultas e verificar correspondências. A solução armazena informações em arrays e realiza comparações diretas.

#include <iostream>
using namespace std;

const int MAX_ENTRIES = 105;
int numNodes, numQueries;
int queryIDs[MAX_ENTRIES];
int eldestChild[MAX_ENTRIES];

int main() {
    cin >> numNodes >> numQueries;
    for (int i = 1; i <= numQueries; i++) {
        int nodeID;
        char queryType;
        cin >> nodeID >> queryType;
        queryIDs[i] = nodeID;
        if (queryType == 'F') continue;
        if (eldestChild[nodeID] == 0) eldestChild[nodeID] = i;
    }
    for (int i = 1; i <= numQueries; i++) {
        if (eldestChild[queryIDs[i]] == i) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

Problema C

O Problema C possui um tamanho n pequeno, permitindo a enumeração de todas as permutações de p para calcular o custo mínimo. A consideração de arestas bidirecionais é crucial para a solução.

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_SIZE = 10;
int n, mFirst, mSecond;
int permutation[MAX_SIZE];
int graphFirst[MAX_SIZE][MAX_SIZE], graphSecond[MAX_SIZE][MAX_SIZE], edgeCost[MAX_SIZE][MAX_SIZE];
int minCost = 0x3f3f3f3f;

int main() {
    cin >> n;
    cin >> mFirst;
    for (int i = 0; i < mFirst; i++) {
        int u, v;
        cin >> u >> v;
        graphFirst[u][v] = graphFirst[v][u] = 1;
    }
    cin >> mSecond;
    for (int i = 0; i < mSecond; i++) {
        int u, v;
        cin >> u >> v;
        graphSecond[u][v] = graphSecond[v][u] = 1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++)
            cin >> edgeCost[i][j], edgeCost[j][i] = edgeCost[i][j];
    
    for (int i = 1; i <= n; i++) permutation[i] = i;
    do {
        int currentCost = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i+1; j <= n; j++) {
                int mappedI = permutation[i], mappedJ = permutation[j];
                if (graphFirst[i][j] != graphSecond[mappedI][mappedJ]) currentCost += edgeCost[mappedI][mappedJ];
            }
        minCost = min(minCost, currentCost);
    } while (next_permutation(permutation+1, permutation+n+1));
    
    cout << minCost << endl;
    return 0;
}

Problema D

O Problema D utiliza discretização e soma de prefixos para processar consultas de intervalo de maneira eficiente, transformando coordenadas em índices contínuos.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAX_QUERIES = 1e6 + 5;
int n, q;
vector<int> pointPositions;
vector<ll> pointValues;
vector<ll> prefixSums;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int pos;
        cin >> pos;
        pointPositions.push_back(pos);
    }
    for (int i = 0; i < n; i++) {
        ll val;
        cin >> val;
        pointValues.push_back(val);
    }
    
    vector<int> allPoints = pointPositions;
    cin >> q;
    vector<pair<int, int>> queryList(q);
    for (int i = 0; i < q; i++) {
        cin >> queryList[i].first >> queryList[i].second;
        allPoints.push_back(queryList[i].first);
        allPoints.push_back(queryList[i].second);
    }
    sort(allPoints.begin(), allPoints.end());
    allPoints.erase(unique(allPoints.begin(), allPoints.end()), allPoints.end());
    
    int totalPoints = allPoints.size();
    prefixSums.resize(totalPoints+1, 0);
    for (int i = 0; i < n; i++) {
        int idx = lower_bound(allPoints.begin(), allPoints.end(), pointPositions[i]) - allPoints.begin();
        prefixSums[idx+1] += pointValues[i];
    }
    for (int i = 1; i <= totalPoints; i++) prefixSums[i] += prefixSums[i-1];
    
    for (auto &query : queryList) {
        int leftIdx = lower_bound(allPoints.begin(), allPoints.end(), query.first) - allPoints.begin();
        int rightIdx = lower_bound(allPoints.begin(), allPoints.end(), query.second) - allPoints.begin();
        cout << prefixSums[rightIdx+1] - prefixSums[leftIdx] << endl;
    }
    return 0;
}

Problema E

O Problema E emprega soma de prefixos e rastreamento de ocorrências futuras para calcular a contribuição total de todas as subsequências de forma otimizada, evitando complexidade quadrática.

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
const int MAX_N = 2e5 + 5;
int n;
int sequence[MAX_N];
vector<int> occurrenceList[MAX_N];
int nextOccurIndex[MAX_N];
ll accumulatedSum, finalAnswer;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> sequence[i];
        occurrenceList[sequence[i]].push_back(i);
    }
    
    for (int i = 1; i <= n; i++) occurrenceList[i].push_back(n+1);
    
    ll currentSum = 0;
    int distinctCount = 0;
    for (int i = 1; i <= n; i++) {
        if (occurrenceList[sequence[i]][nextOccurIndex[sequence[i]]] == i) distinctCount++;
        currentSum += distinctCount;
    }
    
    finalAnswer = currentSum;
    for (int i = 1; i < n; i++) {
        int nextOccur = occurrenceList[sequence[i]][++nextOccurIndex[sequence[i]]];
        currentSum -= (nextOccur - i);
        finalAnswer += currentSum;
    }
    
    cout << finalAnswer << endl;
    return 0;
}