A. Sous-tableau maximum à deux segments

Algorithme standard du sous-tableau maximum :

for (int idx = 1; idx <= n; idx++) 
    cumul[idx] = max(cumul[idx - 1] + valeurs[idx], valeurs[idx]);

cumul[i] représente la somme maximale se terminant à la position i, calculée à partir de la valeur précédente ou en recommençant une nouvelle séquence.

Solution pour deux segments non adjacents :

• prefixMax[i] : somme maximale de 1 à i
• suffixMax[i] : somme maximale de i à n
• Mise à jour des tablaeux pour obtenir les sommes se terminant/débutant à chaque position
• Résultat maximal de prefixMax[i] + suffixMax[i+1] pour chaque i

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int TAILLE = 100010;

int n, resultat;
int valeurs[TAILLE];
int prefixMax[TAILLE], suffixMax[TAILLE];

signed main() {
    cin >> n;
    for (int idx = 1; idx <= n; idx++) cin >> valeurs[idx];
    
    prefixMax[1] = valeurs[1];
    for (int idx = 2; idx <= n; idx++) 
        prefixMax[idx] = max(prefixMax[idx - 1] + valeurs[idx], valeurs[idx]);
    for (int idx = 2; idx <= n; idx++)
        prefixMax[idx] = max(prefixMax[idx - 1], prefixMax[idx]);
    
    suffixMax[n] = valeurs[n];
    for (int idx = n - 1; idx >= 1; idx--)
        suffixMax[idx] = max(suffixMax[idx + 1] + valeurs[idx], valeurs[idx]);
    for (int idx = n - 1; idx >= 1; idx--)
        suffixMax[idx] = max(suffixMax[idx + 1], suffixMax[idx]);
    
    resultat = prefixMax[1] + suffixMax[2];
    for (int sep = 2; sep <= n - 1; sep++)
        resultat = max(resultat, prefixMax[sep] + suffixMax[sep + 1]);
    
    cout << resultat << endl;
}

Problème original : P2642

B. Mise à jour d'intervalle avec séquence arithmétique

Ajout d'une progression arithmétique sur un entervalle [L,R] :

Opérations sur le tableau de différences secondes :

diff[L] += S;
diff[L+1] += D - S;
diff[R+1] -= (E + D);
diff[R+2] += E;

#include <iostream>
#define int long long
using namespace std;
const int MAX = 500010;

int n, m, res;
int diff[MAX];

signed main() {
    cin >> n >> m;
    while (m--) {
        int L, R, S, E;
        cin >> L >> R >> S >> E;
        int ecart = (E - S) / (R - L);
        diff[L] += S;
        diff[L+1] += ecart - S;
        diff[R+1] -= (E + ecart);
        diff[R+2] += E;
    }
    for (int idx = 1; idx <= n+1; idx++) diff[idx] += diff[idx-1];
    for (int idx = 1; idx <= n+1; idx++) diff[idx] += diff[idx-1];
    for (int idx = 1; idx <= n; idx++) res ^= diff[idx];
    cout << res << endl;
}

Problème original : P4231

C. Séquence adorable

État DP : dp[i][v][s][d]

• i : position actuelle
• v : valeur à la position i
• s : somme des valeurs jusqu'à i
• d : relasion avec élément précédent (0 : ≥, 1 : <)

for (int pos = 1; pos <= n; pos++) {
    int min_val = 0, max_val = 40;
    if (input[pos] != -1) min_val = max_val = input[pos];
    for (int val = min_val; val <= max_val; val++) {
        for (int somme = val*(pos-1); somme <= 40*(pos-1); somme++) {
            for (int prev = 0; prev <= val; prev++)
                dp[pos][val][val+somme][0] += dp[pos-1][prev][somme][0] + dp[pos-1][prev][somme][1];
            for (int prev = val+1; prev <= 40; prev++)
                dp[pos][val][val+somme][1] += dp[pos-1][prev][somme][0];
        }
    }
}

#include <iostream>
#define int long long
using namespace std;
const int MOD = 1e9+7;

int n, total;
int input[41];
int dp[41][41][1601][2];

signed main() {
    cin >> n;
    dp[0][0][0][0] = 1;
    for (int idx = 1; idx <= n; idx++) cin >> input[idx];
    
    for (int pos = 1; pos <= n; pos++) {
        int min_val = 0, max_val = 40;
        if (input[pos] != -1) min_val = max_val = input[pos];
        for (int val = min_val; val <= max_val; val++) {
            for (int somme = val*(pos-1); somme <= 40*(pos-1); somme++) {
                for (int prev_val = 0; prev_val <= val; prev_val++) {
                    dp[pos][val][val + somme][0] = 
                        (dp[pos][val][val + somme][0] + 
                         dp[pos-1][prev_val][somme][0] + 
                         dp[pos-1][prev_val][somme][1]) % MOD;
                }
                for (int prev_val = val+1; prev_val <= 40; prev_val++) {
                    dp[pos][val][val + somme][1] = 
                        (dp[pos][val][val + somme][1] + 
                         dp[pos-1][prev_val][somme][0]) % MOD;
                }
            }
        }
    }
    
    for (int val = 0; val <= 40; val++)
        for (int somme = 0; somme <= 40*n; somme++)
            total = (total + dp[n][val][somme][0] + dp[n][val][somme][1]) % MOD;
    
    cout << total << endl;
}

D. Jeu de pierres

Modélisation par coefficients binômiaux :

Solution :

#include <iostream>
#define int long long
using namespace std;
const int MAX = 1000010;
const int MOD = 1e9+7;

int n, res;
int fact[MAX], invFact[MAX];
int a[MAX];

int puissance(int base, int exp) {
    int result = 1;
    while (exp) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

int combinaison(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

signed main() {
    cin >> n;
    n++;
    for (int idx = 1; idx <= n; idx++) cin >> a[idx];
    
    fact[0] = invFact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = fact[i-1] * i % MOD;
        invFact[i] = puissance(fact[i], MOD-2);
    }
    
    for (int idx = 1; idx <= n; idx++) 
        res = (res + combinaison(a[idx] + idx - 1, a[idx] - 1)) % MOD;
    
    cout << res << endl;
}

Problème original : Placing Jinas