C++, rápido y veloz

Table of Contents

CSES paso a paso - This article is part of a series.

En la programación competitiva nos interesa escribir y ejecutar nuestros programas rápidamente, a cualquier precio. Es más, si pudiéramos conseguir que el programa terminara de ejecutarse incluso antes de haberlo ejecutado, mejor que mejor. Sin embargo, como vivimos encadenados a la cruel tecnología de nuestro tiempo, que nos impide aplicar principios cuánticos a nuestro Hello World, nos vemos obligados a hacer las cosas una detrás de otra, con paciencia y buena letra.

En este artículo ofreceremos algunas técnicas que nos permitan sustraernos por un corto tiempo de la vil realidad que nos oprime, y también para apretarle las tuercas a C++ para conseguir que nuestros programas corran un poquito más rápido. Como advertencia al lector, algunas de estas técnicas harían llorar a cualquier profesor de programación, por lo que no me responsabilizo de su uso inadecuado en prácticas de universidad, brazos robóticos, aplicaciones de finanzas, minería de criptomonedas, misiles balísticos intercontinentales, estaciones espaciales y similares.

Plantillas
#

Cada programador tiene su plantilla favorita: el código base del que parte para resolver los problemas. En general, el contenido de esta plantilla debería proporcionarte un entorno familiar para ayudarte a programar rápido, utilizando atajos en forma de macros o typedefs para las funciones o estructuras que utilices más frecuentemente. Además, piensa que nadie tiene por qué entender tu código sino tú y el compilador (y este último no se quejará a menos que hagas algo muy ilegal), así que encárgate de confeccionar la plantilla que más se ajuste a tus necesidades particulares, y no te preocupes mucho por el estilo. (Insisto: si estás programando algo que potencialmente pueda salvar o destruir el mundo, intenta hacer tu código legible y pon comentarios.)

No existe una solución única para crear una plantilla, y poco a poco irás adquiriendo conocimientos que te permitan mejorarla. Sin embargo, como punto de partida, puedes utilizar algunas de las siguientes ideas.

Algunos programadores utilizan plantillas que son, a veces, más largas incluso que el propio código de la solución, pero que incluyen muchos atajos útiles. Puedes buscar algunas de estas plantillas y seleccionar aquellos puntos que te sirvan a ti. Recuerda que, al igual que el cuerpo humano, el compilador es sabio y eliminará aquellas partes del código que no utilices, así que no te debes preocupar excesivamente por la longitud, pero recuerda que durante los concursos (al menos en aquellos presenciales, como las olimpiadas) no tendrás acceso a internet ni a apuntes de ningún tipo, por lo que te recomiendo que utilices algo sencillo que puedas recordar en esos casos.

Personalmente, yo suelo partir de una plantilla muy sencilla, a la que voy añadiendo cosas a medida que sean necesarias. A continuación explicaremos cada una de sus partes:

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // Tu código...

    return 0;
}

La línea #include <bits/stdc++.h> incluye todos los headers de la librería estándar (iostream, vector, algorithm, etc.), por lo que no tendrás que recordar el nombre de la librería que contenía una función concreta que puedas estar buscando. Este no es un header estándar de C++, y depende de la implementación del compilador. En compiladores como GCC (utilizado por la gran mayoría de plataformas) sí que está disponible, pero no en otros, como Visual C++.

La directiva #pragma GCC optimize("O3") fuerza al compilador a aplicar el máximo nivel de optimización (incrementa el tiempo de compilación, pero puede reducir significativamente el tiempo de ejecución).

Finalmente, las líneas ios_base::sync_with_stdio(false); y cin.tie(nullptr); básicamente hacen que la entrada y salida estándar vayan más rápido. Para más detalle, consulta el apartado “Entrada y salida rápida”.

Otros consejos
#

Si el problema requiere del uso de un módulo (veremos la aritmética modular más adelante), puedes utilizar una macro. Este ejemplo se utilizaría en el caso de que un problema pidiera dar la respuesta en módulo $10^{9} + 7$ :
```
#define MOD 1000000007
```
Si necesitas utilizar enteros grandes, puedes cambiar int por ll utilizando este typedef al principio de tu programa (utilízalo con cuidado, ya que las variables de tipo long long utilizan el doble de espacio que las de tipo int):
```
typedef long long ll;

ll n = 1e16; // en un int no cabría
```

Si utilizas std::pair, te puede ayudar añadir un atajo para first y second:

#define f first
#define s second

[...]

pair<int, int> myPair;
myPair.f = 1; // en vez de myPair.first

En las soluciones oficiales de la Olimpiada Informática Española se hace uso frecuente de atajos como estos:

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<vpi> vvpi;

vvpi v; // en vez de vector<vector<pair<int, int>>>

Entrada y salida rápida
#

Para entender este apartado, te recomiendo la lectura de este artículo de USACO Guide. En resumidas cuentas, la entrada/salida estándar es demasiado lenta para nuestras necesidades, por lo que tenemos que echarle una mano para que vaya más rápido. Aquí tienes algunos consejos al respecto:

Como norma general, no utilices endl para realizar un salto de línea: en cambio, utiliza '\n'. Al utilizar endl estamos realizando un flush en la salida, incrementando el tiempo de ejecución.
Las funciones de entradad y salida de C, scanf y printf, pueden resultar ligeramente más rápidas que cin y cout. Puedes utilizar la opción que quieras, pero no las mezcles si no quieres que tu programa haga cosas raras.

Si la entrada y salida del problema se debe hacer mediante ficheros, utiliza freopen para apuntar la entrada y la salida estándar a los ficheros, y utiliza cin y cout con normalidad:

freopen("entrada.txt", "r", stdin);
freopen("salida.txt", "w", stdout);

int n;
cin >> n; // lee del archivo entrada.txt
cout << n << '\n'; // escribe al archivo salida.txt

Si tienes tiempo y ganas, también puedes estudiar la implementación de la entrada y salida con fread y fwrite para ahorrar unos pocos milisegundos.

Desincronización de I/O
#

Significado de ios_base::sync_with_stdio(false) y cin.tie(nullptr).

Por defecto, los streams de entrada y salida estándar de C y C++ están sincronizados. Con ios_base::sync_with_stdio(false) estamos inhabilitando esta función, incrementando ligeramente la eficiencia. Es por ello que no debemos mezclar el uso de cin/cout y scanf/printf.

Con cin.tie(nullptr), la entrada y la salida no están unidas y es posible que las operaciones de lectura y escritura no sigan un flujo lineal. Sin embargo, esto no nos afecta debido a que los jueces realizan la entrada y la salida por canales separados, a diferencia de un usuario que utiliza la consola.

Problemas interactivos
#

En el caso de los problemas interactivos (aquellos en los que nuestro programa se comunica con el programa del juez), si utilizamos estas recomendaciones pueden surgir complicaciones, por lo que es mejor utilizar cin y cout como de costumbre y realizar un flush después de cada operación de salida (bien con endl o flush, o con la función fflush(stdout)). Aquí tienes un ejemplo de problema interactivo, y este documento de la OIE que explica cómo funcionan.

Recomendaciones
#

No tengas miedo de utilizar break y continue, pero hazlo con moderación. Añadir una variable booleana para controlar el flujo de un bucle añade redundancia y puede hacer el código mucho menos legible. A veces es más sencillo utilizar un break y olvidarse del asunto. Eso sí, no lo hagas demasiado o cometerás el riesgo de romper el flujo del programa en un punto donde no se debería.

Utiliza varios return dentro de una función si es necesario, en vez de guardar una variable innecesaria y esperar a llegar al final. Es más sencillo este código:

int func() {
    if (condicion1) return 1;
    if (condicion2) return 2;
    if (condicion3) return 3;
    if (condicion4) return 4;
    return 0;
}

Que este:

int func() {
    int valor = 0;

    if (condicion1) valor = 1;
    else if (condicion2) valor = 2;
    else if (condicion3) valor = 3;
    else if (condicion4) valor = 4;

    return valor;
}

O que este (este es horrible, por favor no hagas esto):

int func() {
    int valor = 0;

    if (!condicion1) {
        if (!condicion2) {
            if (!condicion3) {
                if (condicion4) {
                    valor = 4;
                }
            } else {
                valor = 3;
            }
        } else {
            valor = 2;
        }
    } else {
        valor = 1;
    }

    return valor;
}

Dale un buen nombre a tus variables, pero tampoco te pases:
```
int c; // ???
int countElements; // OK
int variableQueLlevaLaCuentaDeLosElementosDelVector; // too much
```
Utiliza, siempre que sea posible, el mismo nombre que se utilice en el enunciado para describir las variables. En este caso, sí que es buena idea nombrar a tus variables con n, m, k, x, etc., si dichos valores se llaman así en el enunciado.
Dentro de lo posible, utiliza i y j solo para nombrar las variables en los bucles for (si necesitas utilizar más de dos bucles anidados, busca una implementación mejor).
¡Utiliza la librería estándar! No hace falta volver a inventar la rueda: no realices tu propia implementación de la búsqueda binaria o el merge sort teniendo funciones como std::binary_search o std::sort a tu disposición.
Ante todo, sencillez y sentido común. Utiliza aquellos principios con que te sientas más cómodo. No es momento de experimentar en medio de un concurso.

Lecturas
#

Problemas
#

Aquí tienes algunos problemas para practicar antes de la próxima sección.

Football (Codeforces 96A, solución).

Explicación (spoiler!)
En este problema, simplemente hemos de encontrar el subconjunto más largo de caracteres consecutivos iguales y comprobar si su tamaño es mayor o igual a 7.
Twins (Codeforces 160A, solución).

Explicación (spoiler!)
Una solución sencilla consiste en ordenar el vector con los valores de las monedas, e ir cogiendo una a una las de mayor valor hasta que la suma de las monedas que hemos cogido sea mayor que la suma de las monedas restantes. Entonces mostramos por pantalla la cantidad de monedas que hemos cogido hasta ese momento.
Number Spiral (CSES 1071; solución).

Pista
No intentes obtener la solución iterativamente (mediante bucles o recursión), ya que los valores de $x$ e $y$ son demasiado grandes como para hacerlo viable. En cambio, busca un patrón que se repita en la espiral.
Explicación (spoiler!)

Si nos fijamos en la primera fila, observamos que en las columnas impares, el valor de la casilla es igual al cuadrado del número de columna, es decir, $x^{2}$ . A partir de ahí, si vamos bajando, el valor de la casilla se reducirá en uno por cada fila que bajemos hasta la fila $x$ .

Del mismo modo, si observamos la primera columna, en las filas pares, el valor de la casilla es igual al cuadrado del número de fila, $y^{2}$ , y el mismo patrón se repite, pero en horizontal.

En los otros casos (en las columnas pares y en las filas impares), el patrón es al revés: el valor se incrementa a medida que nos adentramos en la espiral.

Así, obtenemos los siguientes cuatro casos (llamaremos $n$ al número que buscamos en la columna $x$ y fila $y$ ):
- Si $y \geq x$ e $y$ es par: $n = y^{2} - (x - 1)$ . Ejemplo: $x = 3, y = 4 \to n = 14$ .
- Si $y \geq x$ e $y$ es impar: $n = y^{2} - (y - 1) - (y - x)$ . Ejemplo: $x = 2, y = 3 \to n = 6$ .
- Si $x > y$ y $x$ es impar: $n = x^{2} - (y - 1)$ . Ejemplo: $x = 3, y = 2 \to n = 8$ .
- Si $x > y$ y $x$ es par: $n = x^{2} - (x - 1) - (x - y)$ . Ejemplo: $x = 4, y = 4 \to n = 12$ .

Author

Alberto Navalón

Computer Science student at the University of Alicante. Google Code-In Grand Prize Winner 2018, competitive programmer and language learner, now playing with NLP.

CSES paso a paso - This article is part of a series.

Plantillas #

Otros consejos #

Entrada y salida rápida #

Desincronización de I/O #

Problemas interactivos #

Recomendaciones #

Lecturas #

Problemas #