A continuación, presento un desglose técnico de los problemas abordados durante el AtCoder Beginner Contest 382, enfocándome en la lógica algorítmica y la optimización.

Problema C: Estrategia de Selección

Dado que los elemantos de mayor valor son consumidos por los primeros individuos de la secuencia, la capacidad efectiva de los participantes resulta en una sublista monótona decreciente. Para resolver esto de manera eficiente, filtramos los candidatos válidos y aplicamos una búsqueda binaria, logrando una complejidad de O(M log N).

// Estructura simplificada de la lógica de búsqueda
void resolver() {
   int n, m;
   std::cin >> n >> m;
   std::vector<int> a(n), b(m);
   // ... lectura de datos ...
   
   std::vector<std::pair<int, int>> min_indices;
   int actual_min = 2e9;
   for(int i = 0; i < n; ++i) {
       if(a[i] < actual_min) {
           actual_min = a[i];
           min_indices.push_back({actual_min, i + 1});
       }
   }
   
   for(int i = 0; i < m; ++i) {
       auto it = std::upper_bound(min_indices.begin(), min_indices.end(), 
                 std::make_pair(b[i], 2000000000));
       if(it == min_indices.begin()) std::cout << -1 << "\n";
       else std::cout << std::prev(it)->second << "\n";
   }
}
   

Problema D: Generación de Secuencias con Backtracking

Para construir las secuencias bajo la restrición ai ≥ ai-1 + 10, implementamos una búsqueda en profundidad (DFS). Aplicamos una poda esencial: si la suma actual más el incremento mínimo requerido excede el límite superior M, terminamos la rama prematuramente.

void buscar(int idx, int ultimo_valor, std::vector<int>& seq, int N, int M) {
   if (idx == N) {
       // Almacenar o imprimir secuencia completa
       return;
   }
   for (int v = ultimo_valor + 10; v + 10 * (N - 1 - idx) <= M; ++v) {
       seq.push_back(v);
       buscar(idx + 1, v, seq, N, M);
       seq.pop_back();
   }
}
   

Problema E: Esperanza Matemática y Programación Dinámica

Para calcular la esperanza del número de intentos necesarios para obtener X cartas raras, definimos P(i, j) como la probabilidad de obtener exactamente j cartas raras al abrir un paquete. El problema se reduce a resolver la recurrancia: E[i] = (Σ E[i-j] * P(n, j) + 1) / (1 - P(n, 0)). La implementación requiere un enfoque de DP con complejidad O(N * M).

void resolver_esperanza() {
   // DP para probabilidades de obtener 'j' cartas raras
   std::vector<double> dp_prob(n + 1, 0.0);
   dp_prob[0] = 1.0;
   for (double p : probs) {
       for (int j = n; j >= 1; --j)
           dp_prob[j] = dp_prob[j] * (1.0 - p) + dp_prob[j - 1] * p;
       dp_prob[0] *= (1.0 - p);
   }
   
   // Cálculo de esperanza
   std::vector<double> E(m + 1, 0.0);
   for (int i = 1; i <= m; ++i) {
       for (int j = 1; j <= std::min(i, n); ++j)
           E[i] += E[i - j] * dp_prob[j];
       E[i] = (E[i] + 1.0) / (1.0 - dp_prob[0]);
   }
}