Cet article présente une récapitulation technique des solutions pour les problèmes de l'AtCoder Beginner Contest 420, avec des explications et des exemples de code réécrits en C++.

Problème A

Un problème simple qui peut être résolu directement. La solution calcule la valeur modulo 12 après ajustement.

#include <iostream>
using namespace std;

int main() {
    int posX, posY;
    cin >> posX >> posY;
    int resultat = ((posX - 1 + posY) % 12) + 1;
    cout << resultat << endl;
    return 0;
}

Problème B

Un problème où l'on doit trouver les indices avec le maximum de points basés sur des séquences binaires. La solution analyse chaque colonne et met à jour les points en conséquence.

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

int main() {
    int nbLignes, nbColonnes;
    cin >> nbLignes >> nbColonnes;
    vector<string> tableau(nbLignes);
    for (int i = 0; i < nbLignes; i++) {
        cin >> tableau[i];
    }
    vector<int> score(nbLignes, 0);
    for (int col = 0; col < nbColonnes; col++) {
        int compteurZero = 0, compteurUn = 0;
        for (int lig = 0; lig < nbLignes; lig++) {
            if (tableau[lig][col] == '0') compteurZero++;
            else compteurUn++;
        }
        if (compteurZero != 0 && compteurUn != 0) {
            if (compteurZero < compteurUn) {
                for (int lig = 0; lig < nbLignes; lig++) {
                    if (tableau[lig][col] == '0') score[lig]++;
                }
            } else {
                for (int lig = 0; lig < nbLignes; lig++) {
                    if (tableau[lig][col] == '1') score[lig]++;
                }
            }
        }
    }
    int maxScore = 0;
    for (int i = 0; i < nbLignes; i++) {
        if (score[i] > maxScore) maxScore = score[i];
    }
    for (int i = 0; i < nbLignes; i++) {
        if (score[i] == maxScore) cout << i + 1 << " ";
    }
    cout << endl;
    return 0;
}

Problème C

Ce problème implique des mises à jour dynamiques où seule une position est affectée à la fois. La solution maintient une somme totale et met à jour uniquement la contribution de l'élément modifié pour optimiser le temps de calcul.

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

int main() {
    long long nbElements, nbRequetes;
    cin >> nbElements >> nbRequetes;
    vector<long long> tableauA(nbElements), tableauB(nbElements);
    for (int i = 0; i < nbElements; i++) cin >> tableauA[i];
    for (int i = 0; i < nbElements; i++) cin >> tableauB[i];
    long long sommeTotale = 0;
    for (int i = 0; i < nbElements; i++) {
        sommeTotale += min(tableauA[i], tableauB[i]);
    }
    for (int q = 0; q < nbRequetes; q++) {
        char typeMiseAJour;
        int position, nouvelleValeur;
        cin >> typeMiseAJour >> position >> nouvelleValeur;
        position--; // Ajustement pour indexation à base zéro
        sommeTotale -= min(tableauA[position], tableauB[position]);
        if (typeMiseAJour == 'A') {
            tableauA[position] = nouvelleValeur;
        } else {
            tableauB[position] = nouvelleValeur;
        }
        sommeTotale += min(tableauA[position], tableauB[position]);
        cout << sommeTotale << endl;
    }
    return 0;
}

Problème D

Ce problème utilise une recherche en largeur (BFS) avec un état supplémentaire pour gérer les portes qui peuvent être ouvertes ou fermées. La solution explore les chemins en maintenant une matrice de visite avec deux dimensions pour l'état des portes.

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

struct EtatBFS {
    int ligne, colonne, etatPorte, pas;
};

int main() {
    int hauteur, largeur;
    cin >> hauteur >> largeur;
    vector<vector<char>> grille(hauteur, vector<char>(largeur));
    int departLig = -1, departCol = -1;
    for (int i = 0; i < hauteur; i++) {
        for (int j = 0; j < largeur; j++) {
            cin >> grille[i][j];
            if (grille[i][j] == 'S') {
                departLig = i;
                departCol = j;
            }
        }
    }
    vector<vector<vector<bool>>> visite(hauteur, vector<vector<bool>>(largeur, vector<bool>(2, false)));
    queue<EtatBFS> fileBFS;
    fileBFS.push({departLig, departCol, 0, 0});
    visite[departLig][departCol][0] = true;
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    while (!fileBFS.empty()) {
        EtatBFS courant = fileBFS.front();
        fileBFS.pop();
        if (grille[courant.ligne][courant.colonne] == 'G') {
            cout << courant.pas << endl;
            return 0;
        }
        for (auto dir : directions) {
            int nouvLig = courant.ligne + dir[0];
            int nouvCol = courant.colonne + dir[1];
            if (nouvLig < 0 || nouvLig >= hauteur || nouvCol < 0 || nouvCol >= largeur) continue;
            char cellule = grille[nouvLig][nouvCol];
            if (cellule == '#') continue;
            int nouvEtat = courant.etatPorte;
            if (cellule == '?') nouvEtat = 1 - nouvEtat;
            if (visite[nouvLig][nouvCol][nouvEtat]) continue;
            bool accessible = true;
            if (cellule == 'o' && courant.etatPorte == 1) accessible = false;
            if (cellule == 'x' && courant.etatPorte == 0) accessible = false;
            if (accessible) {
                visite[nouvLig][nouvCol][nouvEtat] = true;
                fileBFS.push({nouvLig, nouvCol, nouvEtat, courant.pas + 1});
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

Problème E

Ce problème utilise une structure de données Union-Find (union par rang) pour maintenir les composantes connexes et compter les points noirs dans chaque ensemble. La solution répond aux requêtes en vérifiant si l'ensemble contient des points noirs.

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

vector<int> parent, taille, noir;
int trouver(int x) {
    if (parent[x] == x) return x;
    return parent[x] = trouver(parent[x]);
}

int main() {
    int nbSommets, nbRequetes;
    cin >> nbSommets >> nbRequetes;
    parent.resize(nbSommets + 1);
    taille.resize(nbSommets + 1, 0);
    noir.resize(nbSommets + 1, 0);
    for (int i = 1; i <= nbSommets; i++) parent[i] = i;
    for (int q = 0; q < nbRequetes; q++) {
        int typeRequete, paramX, paramY;
        cin >> typeRequete >> paramX;
        if (typeRequete == 1) {
            cin >> paramY;
            int racineX = trouver(paramX);
            int racineY = trouver(paramY);
            if (racineX != racineY) {
                parent[racineY] = racineX;
                taille[racineX] += taille[racineY];
            }
        } else if (typeRequete == 2) {
            int racine = trouver(paramX);
            if (noir[paramX] == 0) {
                taille[racine]++;
                noir[paramX] = 1;
            } else {
                taille[racine]--;
                noir[paramX] = 0;
            }
        } else {
            int racine = trouver(paramX);
            cout << (taille[racine] > 0 ? "Yes" : "No") << endl;
        }
    }
    return 0;
}

Problème G

Ce problème mathématique résout une équation quadratique en supposant une forme particulière. La solution énumère les valeurs possibles pour un paramètre et collecte les solutions uniques.

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

int main() {
    long long valeurX;
    cin >> valeurX;
    vector<long long> solutions;
    solutions.push_back(valeurX - 1);
    solutions.push_back(-valeurX);
    long long borneInf = max(min(valeurX - 1, -valeurX), -10000000LL);
    long long borneSup = min(max(valeurX - 1, -valeurX), 10000000LL);
    for (long long k = borneInf; k <= borneSup; k++) {
        if (k == 0) continue;
        long long denominateur = 2 * k - 1;
        if (denominateur == 0) continue;
        long long numerateur = valeurX - k * k;
        if (numerateur % denominateur == 0) {
            long long n = numerateur / denominateur;
            solutions.push_back(n);
        }
    }
    sort(solutions.begin(), solutions.end());
    auto finUnique = unique(solutions.begin(), solutions.end());
    int nombreSolutions = finUnique - solutions.begin();
    cout << nombreSolutions << endl;
    for (int i = 0; i < nombreSolutions; i++) {
        cout << solutions[i] << " ";
    }
    cout << endl;
    return 0;
}