Macros para programación competitiva

Notar que en todos los casos, cuando queremos hablar de un rango de números, indicamos sus extremos como $[A, B)$, es decir, utilizamos como extremos dos valores A y B de modo tal que los números del rango son aquellos $x$ que cumplen $A \leq x < B$. Esta elección de “fronteras”, que es cerrada a la izquierda, pero abierta a la derecha, es para casi toda tarea de programación la más conveniente, y se utiliza mucho en los lenguajes de programación como C++. También es la que más recomendamos, porque evita muchos errores y es más clara que otras, una vez que uno la conoce.

Para iterar los números desde 0 hasta n-1 inclusive, con la variable i que es creada para el for:

#define forn(i,n) for(int i=0;i<int(n);i++)

Para iterar los números desde s hasta n-1 inclusive, con la variable i que es creada para el for:

#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)

Para iterar los números desde n-1 hasta 0 inclusive, bajando con la variable i que es creada para el for:

#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)

Para iterar los números desde n-1 hasta s inclusive, bajando con la variable i que es creada para el for:

#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)

Las siguientes macros son cómodas para iterar una colección hacia adelante o hacia atrás, si nos interesa tener acceso al iterador y no solamente a los elementos iterados. Eran necesarias (utilizando typeof en lugar de auto) antes de c++11 para iterar sets y maps, pues no existía el foreach.

#define forall(i,c) for(auto i = (c).begin(); i != (c).end(); i++)
#define dforall(i,c) for(auto i = (c).rbegin(); i != (c).rend(); i++)

La siguiente sirve para evitar montones de errores peligrosos y muy difíciles de detectar producto de comparar enteros con y sin signo, ya que .size() retorna un entero sin signo, por lo que al hacerle cuentas resultados como -1 automáticamente pasan a $2^{bits}-1$. El ejemplo más común sería escribir algo como if (v.size()-1 >= 0), que da siempre true, a diferencia de if (SIZE(v)-1 >= 0) que se comporta como uno espera. Pasar inmediatamente a entero con signo evita problemas.

#define SIZE(c) int((c).size())

La siguiente es muy útil para utilizar con funciones de STL, donde se suele pedir un rango mediante dos iteradores, para pasar directamente una colección completa.

#define ALL(c) begin(c), end(c)

El uso más común de esta macro, es para llamar a la función sort, con sort(ALL(v)) por ejemplo, siendo v un vector. Sin embargo es útil con muchísimas funciones de la STL, como podría ser por ejemplo una instrucción find(ALL(v), 27).

La siguiente sirve para consultar si un elemento está en un set (o map: en un map, se consulta si el elemento dado es una clave del diccionario).

#define ESTA(x,c) ((c).find(x) != (c).end())

Las siguientes son muy útiles para buscar y corregir errores en programas:

#define DBG(x) cerr << #x << " = " << (x) << endl
#define RAYA cerr << "===============================" << endl

DBG es una macro particularmente bonita y “mágica”. Si escribimos en una línea DBG(x); en el código, siendo x una variable (o podría ser una expresión), nos mostrará su valor y su nombre por pantalla. Alentamos a probarla para ver su utilidad a la hora de buscar bugs en programas.

Similarmente, RAYA; muestra una clara línea separadora: esto es especialmente útil cuando tenemos un for y queremos mostrar los valores de varias variables en cada iteración. Poniendo un RAYA;, podemos separar con facilidad los valores entre iteraciones.

Los siguientes typedef son razonables y cómodos en programación competitiva:

typedef long long tint;
typedef long double tdbl;

O su equivalente más moderno:

using tint = long long;
using tdbl = long double;

Utilizar tint para indicar el tipo del int permite cambiar entre int, unsigned, long long, unsigned long long, __int128, unsigned char, etc fácilmente si se usa siempre tint para los “valores” del programa (mientras que se usa por ejemplo int para los índices de arreglos y colecciones).

El porqué de la macro forn

#define forn(i, n) for(int i = 0; i < int(n); i++)

nos permite, además de parametrizar la cantidad de iteraciones, parametrizar la variable que indexa. Entonces uno puede escribir

forn(i, 10){
    forn (j, SIZE(v)) {
 
    }
}

Uno podría entusiarmarse con las macros y hacer la siguiente macro:

#define forn(n) for(int i = 0; i < int(n); i++)

Es una muy mala idea definir el forn sin pasarle la variable para indexar, porque eso nos podría introducir muy fácilmente “bugs ocultos” por no ser suficientemente declarativos y esconder cosas en la macro. En este caso, escondemos una declaración de variables visibles fuera de la macro.

Por ejemplo, este código tendría un error oculto usando esa macro

int i = 24;
forn(10){
	cout << i << endl;
}

Un lector cualquiera asumiría que este código escribe 10 veces el número 24, pero se encontraría con que imprime los números del 1 al 10.

En general el objetivo de las macros no es escribir menos caracteres, sino escribir código que evite bugs simples por repetición o copy-paste.

Otro ejemplo:

for(int i=0;i<n;i++){
    for(int j=0;j<m;i++){
 
   }
}

Ese código tiene un bug no evidente a simple vista: en el segundo for incrementa i en vez de j. En cambio, usando la macro forn como la definimos más arriba, sería

forn(i, n) {
   forn(j, m) {
 
   }
}

¡Donde ese bug es simplemente imposible de escribir! Usar i ambas veces sería el bug más parecido, pero si usamos las opciones de compilación recomendadas tendremos una advertencia por shadow al hacerlo, e incluso sin el warning es un bug mucho más fácil de detectar y corregir.