Jeux de pierres premières

Le théorème de Zermelo établit que chaque position est soit gagnante soit perdante avec une stratégie optimale. On définit 0 comme position perdante. Une position est gagnante si elle permet de laisser une position perdante à l'adversaire. Une position est perdante si toutes les actions conduisent à une position gagnante pour l'adversaire. L'analyse montre que les multiples de 4 sont predants, les autres sont gagnants.

#include <iostream>
using namespace std;
using ll = long long;

void process() {
    ll size;
    cin >> size;
    cout << (size % 4 != 0 ? "Alice\n" : "Bob\n");
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tests;
    cin >> tests;
    while (tests--) {
        process();
    }
}

Gestion des intervalles de caractères

L'approche utilise un tri glouton sur les intervalles de 'z' et 'Z'. On identifie d'abord les zones contiguës, les trie par taille croissante, puis utilise un tableau de différences pour marquer les suppressions optimales.

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    while (!s.empty() && s.back() == 'z') {
        s.pop_back();
    }
    vector<pii> intervals;
    int start = -1, end = 0;
    while (end < s.size() && s[end] == 'z') {
        end++;
    }
    while (end < s.size() && s[end] == 'Z') {
        end++;
    }
    start = end;
    while (end < s.size()) {
        if (end > 0 && s[end] == 'Z') {
            intervals.emplace_back(start, end - 1);
            while (end < s.size() && s[end] == 'Z') {
                end++;
            }
            start = end;
        } else {
            end++;
        }
    }
    if (start < s.size()) {
        intervals.emplace_back(start, s.size() - 1);
    }
    sort(intervals.begin(), intervals.end(), [](const pii &a, const pii &b) {
        return (a.second - a.first) < (b.second - b.first);
    });
    vector<int> diff(s.size() + 2, 0);
    for (int i = 0; i < intervals.size() && k > 0; i++) {
        int len = intervals[i].second - intervals[i].first + 1;
        if (k >= len) {
            diff[intervals[i].first]++;
            diff[intervals[i].second + 1]--;
            k -= len;
        }
    }
    for (int i = 1; i < s.size(); i++) {
        diff[i] += diff[i - 1];
    }
    string result;
    bool skip = true;
    for (int i = 0; i < s.size(); i++) {
        if (skip && s[i] == 'z') continue;
        skip = false;
        if (diff[i]) continue;
        result += s[i];
    }
    int total = 0;
    for (int i = 1; i < result.size(); i++) {
        int a = (result[i] == 'z' ? 0 : 2);
        int b = (result[i - 1] == 'z' ? 0 : 2);
        total += a * b;
    }
    cout << total << '\n';
}

Planification d'affiches

Problème de programmation dynamique 0-1. On définit dp[i] comme le coût minimal pour couvrir la première i positions. La transition vérifie que l'affiche couvre la position j et ne chevauche pas.

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

const ll INF = 1e18;

void process() {
    int n;
    cin >> n;
    vector<ll> lengths(n + 1, 0);
    vector<ll> dp(n + 1, INF);
    for (int i = 1; i <= n; i++) {
        cin >> lengths[i];
    }
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (i - lengths[j] < j && i - lengths[j] >= 0) {
                dp[i] = min(dp[i], dp[i - lengths[j]] + 1);
            }
        }
    }
    cout << (dp[n] == INF ? -1 : dp[n]) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tests;
    cin >> tests;
    while (tests--) {
        process();
    }
}

Problème de chaîne de Reimu

La définition de l'ordre lexicographique est inversée. On regroupe les caractères idetniques en sous-chaînes. Si S_i < S_{i+1}, on peut copier S_i pour diminuer l'ordre.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, max_ops;
    cin >> n >> max_ops;
    string s;
    cin >> s;
    vector<int> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    vector<pii> groups;
    int current_char = -1;
    int count = 0;
    for (char c : s) {
        int idx = c - 'a';
        if (idx != current_char) {
            if (count > 0) {
                groups.push_back({current_char, count});
            }
            current_char = idx;
            count = 1;
        } else {
            count++;
        }
    }
    if (count > 0) {
        groups.push_back({current_char, count});
    }
    string result;
    int index = 0;
    for (int i = 0; i < groups.size(); i++) {
        if (max_ops > 0 && i + 1 < groups.size() && groups[i].first < groups[i + 1].first) {
            priority_queue<int, vector<int>, greater<int>> pq;
            for (int j = index; j < index + groups[i].second; j++) {
                pq.push(cost[j]);
            }
            int copies = 0;
            while (!pq.empty() && max_ops >= pq.top()) {
                max_ops -= pq.top();
                pq.pop();
                copies++;
            }
            for (int j = 0; j < copies; j++) {
                result += char('a' + groups[i].first);
            }
        }
        for (int j = 0; j < groups[i].second; j++) {
            result += char('a' + groups[i].first);
        }
        index += groups[i].second;
    }
    cout << result << '\n';
}

Opérations sur intervalles

L'utilisation d'un tableau de différences permet d'appliquer efficacement les opérations sur les intervalles avant de calculer la somme finale.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, operations;
    cin >> n >> operations;
    vector<ll> arr(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    vector<ll> diff(n + 2, 0);
    for (int i = 0; i < operations; i++) {
        ll type, l, r, value;
        cin >> type >> l >> r >> value;
        if (type == 1) {
            diff[l] -= value;
            diff[r + 1] += value;
        } else {
            diff[l] += value;
            diff[r + 1] -= value;
        }
    }
    for (int i = 1; i <= n; i++) {
        diff[i] += diff[i - 1];
        arr[i] += diff[i];
    }
    ll left, right;
    cin >> left >> right;
    ll total = 0;
    for (int i = left; i <= right; i++) {
        total += arr[i];
    }
    cout << total << '\n';
}