Problème G: Théorie des jeux avec Rikka

Énoncé du problème: Étant donné un graphe non oreinté à n sommets (n ≤ 17), attribuer une valeur à chaque sommet telle que la valeur de chaque sommet soit le mex des valeurs des sommets adjacents. Calculer le nombre total d'attribution valide.

Solution: La contrainte sur n suggère une approche par programmation dynamique avec compression de bit. Définissons les ensembles V0, V1, ... comme les ensembles de sommets attribués aux valeurs 0, 1, ... respectivement. Chaque ensemble V_k doit satisfaire deux conditions: 1) Les sommets dans V_k ne doivent pas être connectés entre eux (indépendance); 2) Tout sommet ayant une valeur supérieure à k doit être adjacent à au moins un sommet dans V_k. Cela revient à recouvrir le graphe par des ensembles indépendants successifs. Soit dp[state] le nombre de façons d'attribuer des valeurs lorsque l'état du graphe est représenté par le masque binaire state. Pour chaque état state, nous énumérons ses sous-ensembles indépendants son, et mettons à jour dp[state] += dp[state ^ son].

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 17;
ll dp[1 << MAXN];
int adjacency[MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adjacency[u] |= (1 << v);
        adjacency[v] |= (1 << u);
    }
    int fullMask = (1 << n) - 1;
    vector<int> neighborMask(fullMask + 1, 0);
    for (int mask = 1; mask <= fullMask; ++mask) {
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                neighborMask[mask] |= adjacency[i];
            }
        }
    }
    dp[0] = 1;
    for (int mask = 1; mask <= fullMask; ++mask) {
        for (int sub = mask; sub; sub = (sub - 1) & mask) {
            if ((neighborMask[sub] & sub) == 0 && (neighborMask[sub] & (mask ^ sub)) == (mask ^ sub)) {
                dp[mask] += dp[mask ^ sub];
            }
        }
    }
    cout << dp[fullMask] << endl;
    return 0;
}

Problème I: RCPC avec Rikka

Énoncé du problème: Minimiser le coût total pour gérer une séquence d'événements tout en évitant que la valeur "angry" n'atteigne un seuil T. Des règles spécifiques permettent de réduire les coûts sous certaines conditions.

Solution: Transformer le problème en une minimisation de coût par programmation dynamique. Soit dp[i] le coût minimal jusqu'à la position i. Si aucun sous-chaîne valide ne se termine à i, alors dp[i] = dp[i-1] + a[i]. Sinon, dp[i] = min(dp[x]) pour tous x satisfaisant certaines contraintes sur les sommes partielles. L'optimisation avec une file monotone ou un arbre de segments est nécessaire pour une efficacité optimale. Attention aux éléments finaux: la solution optimale peut impliquer de ne pas appliquer certaines réductions.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
typedef long long ll;

int main() {
    int n, k, T;
    cin >> n >> k >> T;
    ++k;
    vector<int> weights(n);
    vector<ll> prefixSum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        cin >> weights[i];
        prefixSum[i + 1] = prefixSum[i] + weights[i];
    }
    vector<ll> dp(n + 1, 0);
    deque<int> dq;
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1];
        if (i >= k) {
            int idx = i - k;
            while (!dq.empty() && dp[dq.back()] - prefixSum[dq.back()] < dp[idx] - prefixSum[idx]) {
                dq.pop_back();
            }
            dq.push_back(idx);
        }
        while (!dq.empty() && prefixSum[dq.front()] + T < prefixSum[i]) {
            dq.pop_front();
        }
        if (!dq.empty()) {
            dp[i] = max(dp[i], dp[dq.front()] - prefixSum[dq.front()] + prefixSum[i]);
        }
    }
    ll totalSum = prefixSum[n];
    ll answer = totalSum;
    for (int i = 0; i <= n; ++i) {
        if (totalSum - prefixSum[i] <= T) {
            answer = min(answer, prefixSum[i] - dp[i]);
        }
    }
    cout << answer << endl;
    return 0;
}

Problème J: Livres avec Rikka

Énoncé du problème: Étant donné n livres avec des poids w[i] et des longueurs l[i], les empiler en forme de rectangles 1×l[i] sur un plan 2D. Trouver la distance horizontale maximale entre le bord de la pile et le centre de gravité, sans déséquilibre.

Solution: Utiliser une programmation dynamique avec compression de bit. Définir dp[state][i] comme la distance maximale du centre de gravité lorsque l'ensemble des livres empilés est représenté par le masque state et que le livre i est à la base. Pour chaque transition, calculer le nouveau centre de gravité en utilisant la formule de conservation de la masse. Attention, la distance maximale peut provenir de l'un des deux côtés de la pile.

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

int main() {
    int n;
    cin >> n;
    vector<double> length(n), weight(n);
    for (int i = 0; i < n; ++i) cin >> length[i];
    for (int i = 0; i < n; ++i) cin >> weight[i];
    int fullMask = (1 << n) - 1;
    vector<double> totalWeight(fullMask + 1, 0.0);
    vector<int> countBooks(fullMask + 1, 0);
    for (int mask = 1; mask <= fullMask; ++mask) {
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                totalWeight[mask] += weight[i];
                countBooks[mask]++;
            }
        }
    }
    vector<vector<double>> dp(fullMask + 1, vector<double>(n, 0.0));
    vector<double> maxDist(fullMask + 1, 0.0);
    for (int mask = 1; mask <= fullMask; ++mask) {
        if (countBooks[mask] == 1) {
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    dp[mask][i] = length[i] / 2.0;
                    maxDist[mask] = dp[mask][i];
                    break;
                }
            }
            continue;
        }
        for (int base = 0; base < n; ++base) {
            if (!(mask & (1 << base))) continue;
            int prevMask = mask ^ (1 << base);
            if (prevMask == 0) continue;
            double prevWeight = totalWeight[prevMask];
            double currentWeight = totalWeight[mask];
            double shift = (length[base] / 2.0) * (prevWeight / currentWeight);
            double candidate1 = maxDist[prevMask] + length[base] / 2.0 - shift;
            double candidate2 = length[base] / 2.0 + shift;
            dp[mask][base] = max(candidate1, candidate2);
            maxDist[mask] = max(maxDist[mask], dp[mask][base]);
        }
    }
    cout << fixed << setprecision(10) << maxDist[fullMask] << endl;
    return 0;
}