Принцип Дирихле в олимпиадных задачах: как его реально применять?
Постоянно в разборах пишут «по принципу Дирихле (pigeonhole) найдутся два...». Я понимаю формулировку «если n+1 голубей в n клетках, в одной клетке ≥2», но не понимаю, как это превращается в алгоритм. Можете показать на конкретной задаче, где именно Дирихле даёт решение?
2 ответа
Принцип Дирихле в усиленной форме: если разложить N предметов по k клеткам, то найдётся клетка с ≥ ⌈N/k⌉ предметами. В алгоритмах он чаще всего гарантирует существование коллизии или совпадения по модулю, и это совпадение сразу даёт ответ.
Классика: в массиве из n чисел всегда найдётся непустой подотрезок, сумма которого делится на n. Берём префиксные суммы P_0=0, P_1, ..., P_n — это n+1 значение остатков по модулю n. Остатков всего n, значений n+1 → по Дирихле два префикса P_i ≡ P_j (mod n), и тогда сумма на отрезке (i, j] делится на n.
// возвращает границы подотрезка [l+1..r] (1-индексация), сумма делится на n
pair<int,int> subarrayDivByN(vector<int>& a) {
int n = a.size();
vector<int> firstIdx(n, -1);
int pref = 0;
firstIdx[0] = 0; // P_0 = 0
for (int i = 1; i <= n; i++) {
pref = (pref + a[i-1]) % n;
if (firstIdx[pref] != -1) return {firstIdx[pref] + 1, i};
firstIdx[pref] = i;
}
return {-1, -1}; // по Дирихле сюда не дойдём
}
Сложность O(n) времени и памяти. Суть: «n+1 префиксов, n остатков → коллизия» — это и есть Дирихле, переведённый в код через массив firstIdx.
Другой типовой паттерн — Дирихле по координатам/значениям: если выбрать k+1 чисел из {1,...,2k}, обязательно найдутся два, где одно делит другое (клетки = нечётные «ядра» чисел). На контесте Дирихле редко даёт прямой код — чаще он обосновывает, что какой-то жадный/перебор гарантированно найдёт пару, и позволяет ограничить размер перебора (например, «достаточно проверить первые n+1 элементов»).