Перебор подмножеств и битовые маски в ЕГЭ (Задание 23)

Делимся разбором самых сложных заданий в Телеграм канале

Как разобраться в теме без паники

** изображение создано или обработано с помощью ИИ.

«Перебор подмножеств и другие темы к ЕГЭ» звучит как фраза из подвала программистов. Я тоже так думал. Сейчас мне 27, я несколько лет разбираю задачи с учениками. Скажу честно: тема не страшная. Страшно прыгать в неё без плана.

Перебор нужен там, где мы выбираем часть объектов: несколько чисел, файлов, дорог, букв. ЕГЭ любит такие ситуации. Экзамен проверяет не магию, а аккуратность. Нужно понять, что именно можно брать, а что нельзя.

Ученик видит условие и думает: «Всё, приехали». Я отвечаю: «Не приехали, просто парковка большая». В задачах с подмножествами задайте себе простой вопрос: мы выбираем каждый элемент или пропускаем его? Если да — перед вами почти наверняка перебор.

Но один перебор не спасает. Рядом часто живут таблицы, графы, рекурсия, динамическое программирование, логика. Эти темы дружат. Иногда даже слишком — как соседи, которые постоянно заходят за солью.

Как увидеть подмножество в задаче

** изображение создано или обработано с помощью ИИ.

Подмножество — это выбранная часть исходного набора. В школьных задачах набор всегда конечный. Это важно, потому что компьютер не философствует — он перебирает варианты по чёткому правилу.

Первые маркеры в тексте. Слова «выбрать», «часть», «некоторые», «набор», «комбинация» часто указывают на подмножества. Не всегда — ЕГЭ любит маскировку, но эти слова точно стоит подчёркивать карандашом.

Дальше — размер набора. Если элементов мало (до 20), прямой перебор всех комбинаций обычно проходит в Python. Если их 25 и больше — $2^{25}$ это 33 миллиона вариантов, для Python это много. Тут уже нужны оптимизации: отсечения, динамика или «встреча посередине».

Мой порядок действий:

Выписать элементы набора.

Понять, можно ли брать каждый элемент только один раз.

Найти запреты и обязательные условия (если сказано «включает хотя бы один» или «не включает элемент X»).

Оценить число вариантов (хотя бы прикинуть: много или мало).

Выбрать способ решения: ручной перебор на бумаге или программа.

Мини-диалог из практики:

— А если вариантов миллион?

— Миллион для компьютера не проблема.

— А миллиард?

— Вот тут уже чай остынет.

Оценка нужна до кода. Она экономит время и нервы. Признак — независимый выбор. Для каждого элемента есть два состояния: берём или не берём. Значит, для n элементов получается 2ⁿ вариантов. Это не нужно заучивать как заклинание. Просто запомните: каждый новый объект удваивает число возможных сценариев.

Битовые маски: маленький фонарик в темном лесу

** изображение создано или обработано с помощью ИИ.

Битовая маска пугает только при первом знакомстве. На деле это обычное число, которое хранит набор ответов «да» и «нет». Единица (1) означает «взяли», ноль (0) — «пропустили». Компактно и без лишней драмы.

Пример. Есть три числа: 5, 8, 13. Маска 101 (двоичная) означает: взяли первое и третье число (5 и 13), второе пропустили. Маска 010 — взяли только второе число (8). Все возможные подмножества можно перебрать числами от 0 до 2ⁿ − 1, где n — количество элементов.

Как это работает в Python. Цикл по всем маскам (от 0 до 2ⁿ−1). Для каждой маски проверяем каждый бит. Если бит равен 1 — включаем соответствующий элемент. Идея проста: маска — это чек-лист, упакованный в число.

Частая ошибка. Путают номер бита и номер элемента. Ошибка встречается чаще, чем пустая кружка перед дедлайном. Первый элемент часто связывают с нулевым битом (младшим). В тетради лучше подписывать соответствие явно: «элемент 1 — бит 0, элемент 2 — бит 1».

Когда маски особенно удобны:

нужно перебрать все возможные группы элементов;

количество элементов небольшое (обычно не более 20-25);

требуется быстро проверять, входит ли элемент в текущую комбинацию;

задача просит найти максимум, минимум или количество подходящих вариантов.

Хотите решать Задание 23 за 5 минут, не запутавшись в вариантах? В «ЕГЭленд» мы разбираем комбинаторику и битовые маски на конкретных примерах ФИПИ. Вы научитесь видеть структуру задачи и применять маски там, где другие пишут 10 вложенных циклов. Заходите на курс подготовки к ЕГЭ и ОГЭ по информатике.

Динамика, графы и таблицы рядом с перебором

** изображение создано или обработано с помощью ИИ.

Перебор подмножеств часто используют вместе с динамическим программированием. Динамика выручает, когда полный перебор занимает слишком много времени. Вместо многократных повторных вычислений вы сохраняете уже найденные ответы и используете их дальше.

Основная идея. Состояние описывает уже обработанную часть данных. Переход показывает, как добавить один новый элемент. В заданиях ЕГЭ это может быть накопленная сумма, текущая позиция, построенная строка или набор выполненных команд. Формулировки разные, но логика повторяется.

Графы тоже связаны с этой темой. Есть вершины, рёбра, маршруты, ограничения. Иногда нужно выбрать только некоторые вершины, иногда — пройти по разрешённым дорогам. Рисуйте схемы. Даже если ваш чертёж похож на карту метро после землетрясения.

Таблицы помогают не запутаться в вариантах. По строкам удобно записывать шаги, по столбцам — состояния. Таблица показывает структуру, а структура уменьшает панику. На экзамене это очень полезно.

Простой ориентир. Если в задаче спрашивают «сколько способов» — ищите повторяющиеся состояния и суммируйте варианты перехода. Если спрашивают «лучшее значение» — ищите максимум или минимум среди переходов. Если спрашивают «существует ли» — проверяйте, достижимо ли нужное состояние из начального.

Не нужно воспринимать динамическое программирование как сложную магию. Разбирайте небольшие примеры. Сначала вручную на бумаге, затем пишите код. После трёх-четырёх разобранных примеров вы начнёте замечать знакомые схемы. Это приятный момент.

Практика перед экзаменом: режим без героизма

** изображение создано или обработано с помощью ИИ.

Самая вредная стратегия — героически решать всё подряд ночью. Я пробовал. Результат был так себе. Утром мозг работает как картошка. Практика должна быть регулярной и честной.

Берите одну тему на короткий отрезок. Например, сегодня только подмножества. Завтра — только таблицы истинности. Послезавтра — задачи на файлы. Так вы видите прогресс и не смешиваете в голове шесть разных приёмов.

Хороший цикл занятий:

Разобрать одну идею на простом примере.

Решить две похожие задачи без подсказок.

Записать ошибку простыми словами (не «не понял», а «забыл про правую границу»).

Вернуться к этой же ошибке через два дня.

Собрать мини-шпаргалку с приёмами по теме.

Зачем шпаргалка? Не для экзамена, а для памяти. Когда вы формулируете приём своими словами, мозг перестаёт быть пассажиром — он садится за руль. Иногда криво, но уже сам.

Разбор чужого решения. Не копируйте слепо. Задавайте вопросы: почему цикл идёт именно до этого числа? Где хранится промежуточный ответ? Что именно проверяет условие? Если ответы не ясны, перепишите решение на бумаге.

Тренируйте чтение условия. Звучит скучно, но многие ошибки рождаются не в коде. Они появляются на первой минуте, когда человек пропустил слова «не более», «различные», «в порядке возрастания». Экзамен такие мелочи не прощает.

Типичные ошибки и мой короткий план

** изображение создано или обработано с помощью ИИ.

Первая ошибка — начинать с кода. Руки уже печатают, а голова ещё не поняла задачу. Получается цифровой винегрет. Лучше потратить две минуты на схему на бумаге. Это быстрее, чем потом искать ошибку в уже написанной программе.

Вторая ошибка — забывать пустое подмножество. Иногда оно подходит под условие, иногда нет. Решает только текст задачи, не ваше настроение и не интуиция.

Третья ошибка — считать одинаковые варианты несколько раз. Например, набор {2, 5} — это то же самое, что {5, 2}, если порядок не важен. Нельзя превращать комбинации в перестановки. Помогает сортировка элементов или перебор с выбором по возрастающим индексам.

Четвёртая ошибка — игнорировать ограничения. Если элементов слишком много, полный перебор всех подмножеств может не уложиться в отведённое время. Тогда ищите способы сократить перебор: отсечение заведомо неподходящих вариантов, динамическое программирование, жадный алгоритм или математическая формула.

Мой базовый план:

Прочитать условие два раза.

Выписать, из каких элементов выбираем.

Отметить все ограничения (можно ли повторять, важен ли порядок).

Оценить число возможных вариантов (хотя бы прикинуть).

Выбрать способ: прямой перебор, битовые маски, рекурсия или динамика.

Проверить решение на маленьком примере (руками или простым кодом).

Не пытайтесь выглядеть гением. Будьте аккуратным человеком с рабочим планом. ЕГЭ по информатике это ценит. А перебор подмножеств после регулярной практики становится почти дружелюбным. По крайней мере, по меркам экзамена.