Тип 4
Мы завершаем работу с 24 заданиями ЕГЭ по информатике. В прошлых статьях уже разобрали алгоритмы решения первых трёх типов как с использованием регулярных выражений, так и без них.
Как раз в предыдущей статье мы пришли к выводу, что порой гораздо оптимальнее решать 24 задания с помощью метода замены и разделения. Сейчас же мы продолжим развивать эту мысль и используем этот метод для решения заданий 4 типа.
Алгоритм решения
В 24 заданиях четвёртого типа часто встречаются условия, в которых указано определённое содержание каких-то комбинаций букв или одиночных букв в требуемой подстроке. Мы всё так же должны найти максимально длинную подстроку, но теперь в этой подстроке должно быть, например, ровно 2 буквы «А».
Для примера рассмотрим такую строку: «BCADBECAFBDACEB». Нам нужно найти самую длинную подстроку, содержащую ровно 2 буквы А. Как подойти к решению?
Представим, что мы «разрезаем» строку по каждой букве «А»:
После разреза получаем фрагменты: «BC», «DBEC», «FBD» и «CEB».
Теперь ключевое наблюдение: между любыми двумя соседними фрагментами в исходной строке стояла буква А. Значит, если мы возьмём 3 соседних фрагмента и склеим их обратно (добавив между ними буквы «А»), то получим подстроку ровно с 2 буквами А — ведь между тремя фрагментами ровно два «разреза».
Переберём все возможные тройки соседних фрагментов. Первая тройка состоит из символов от начала строки до третьего символа «A»: «BC», «DBEC», «FBD».
Склеиваем все три фрагмента через символ «A» и получаем подстроку длиной 11 символов.
Теперь вторая тройка. Она начинается после первого символа «А» (с фрагмента «DBEC») и длится до конца строки. Еще можно представить, что там после символа B стоит еще одна «А» — суть одна и та же.
Здесь все еще 2 символа «А» и мы постарались поместить в эту подстроку максимум букв. Максимум как раз и означает, что мы пропускаем букву «А», которая была первой в предыдущей строке, и захватываем все сразу после неё и вплоть до третьей по счёту буквы «А» или до конца всё строки.
Теперь собираем фрагменты «DBEC», «FBD» и «CEB» через символ «А» и получаем подстроку длиной 12 символов. Она и будет самой длинной в нашем примере.
В коде же это реализуется так: мы заменяем каждую букву А на « A » (с пробелами по краям), затем разбиваем строку по пробелам методом split(). После этого перебираем все группы из 3 соседних элементов, склеиваем их и ищем максимальную длину.
Но более наглядно это можно будет видно на задании с такой формулировкой:
«Текстовый файл состоит из символов A, B, C, D, E.
Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых комбинация символов AB встречается ровно 21 раз.»
Да, здесь целых две буквы, вместо одной «А», но сути это не меняет. Считываем файл и проводим замены — нужно разбить эту парочку «AB» пробельным символом и разделить всю строку по нему.
Визуализируем это примером из прошлой статьи. Рассмотрим строку «ABCAA BACACAB». Если разбить её по символам «AB», то получим такие 4 фрагмента: «A», «BCAA», «BACACA» и «B».
Крайние буквы нас пока не особо интересуют. Отметим следующее, склеив фрагменты «BCAA» и «BACACA», мы получим подстроку, в которой ровно 1 раз встречается комбинация символов «AB».
Осталось только масштабировать эту логику. Чтобы «AB» встречалась 21 раз нужно склеить 22 таких фрагмента. Скоро до этого дойдём. Но пока заведём переменную, в которой будем хранить максимальную длину подстроки:
Далее нужен цикл. Сейчас у нас в data хранится список из фрагментов строк. Будем перебирать эти фрагменты с шагом в 22 подстроки. Следовательно, индексы берём на 21 меньше:
Почему «len(data) – 21»? Потому что нам нужно взять 22 элемента подряд (между ними будет 21 «разрез»). Если в списке, например, 100 элементов, то последняя допустимая начальная позиция — 78 (с неё мы возьмём элементы с 78 по 99, всего 22 штуки).
Берём срез из 22 последовательных элементов списка начиная с позиции i. Срез «data[i:i + 22]» вернёт список из 22 фрагментов.
Метод «"".join()» склеивает все эти фрагменты обратно в одну строку (пустая строка «» означает, что между фрагментами ничего не вставляется). В примере с буквой «А» мы вставляли саму букву из-за того, что разделяли строку по ней. Здесь же разделяем по пробельному символу, следовательно, никаких букв добавлять не надо.
Получившаяся строка substring содержит ровно 21 комбинацию «AB» — по одной между каждыми двумя соседними фрагментами.
Осталось сравнить длину текущей подстроки с максимальной, найденной ранее (или с нулём, если это первая найденная подстрока). Если текущая подстрока длиннее — обновляем максимум.
В конце выводим значение max_len:
Решение готово, запускаем программу и получаем число 10007. Его и запишем в ответ.
Пример 1
Теперь рассмотрим такое задание:
«Текстовый файл состоит из символов A, B, C, D, E.
Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых символ A встречается не более 3 раз.»
Это задание максимально похоже на то, что было в нашем первом примере. Ввести в заблуждение может фраза «не более 3 раз». Чем она отличается от нашей формулировки «ровно 2 раза»?
Давайте подумаем логически.
Если мы ищем подстроку, где буква «A» встречается не более 3 раз, то максимальная длина будет достигаться именно при 3 буквах «A». Почему? Потому что подстрока с 3 буквами «A» всегда включает в себя подстроки с 2, 1 или 0 буквами A»». Добавляя ещё одну букву «A» (и фрагменты вокруг неё), мы только увеличиваем длину.
Другими словами: если взять 4 фрагмента, мы получим подстроку, которая содержит внутри себя все варианты с 3, 2 и 1 фрагментами из той же позиции. Значит, она точно будет не короче.
Единственное исключение — если в строке вообще меньше 3 букв «A». Тогда мы просто не сможем взять 4 фрагмента, и код с фиксированным числом фрагментов упадёт с ошибкой или даст неверный результат.
Но в реальных заданиях ЕГЭ файлы содержат сотни тысяч символов, так что букв A там заведомо больше трёх. Поэтому для экзамена можно смело использовать вариант решения, выведенный ранее:
Запускаем программу и получаем верный ответ — число 501.
Приведём еще решение с помощью регулярных выражений. Вспомним наш пример с первой подходящей подстрокой:
Какой шаблон можно здесь увидеть?
- Строка начинается с 0 и более символов «не А»;
- Далее идёт символ «А», после которого 0 и более «не А»;
- Группа из пункта 2 повторяется ровно 3 раза.
Давайте запишем такой шаблон. Сразу важное замечание — работаем мы с перекрывающимися подстроками, для этого обязательно писать выражения с опережающей проверкой «(?=…)»!
Все символы, кроме «А», будем искать по такому шаблону:
Группу из одного символа «А» и 0 и более любых других ищем так:
Теперь соберём все вместе.
Обратите внимание, что внутри f-строк значения в фигурных скобках считаются переменными. Чтобы использовать запись «{3}» как квантификатор, нужно её дополнительно обернуть в еще одни фигурные скобки.
Добавим чтение файла и поиск совпадений через finditer():
И еще один момент: поскольку мы здесь используем опережающие проверки, то искомая подстрока будет не во всем match-объекте, а в его первой группе: match.group(1).
В конце выводим значение answer:
Пример 2
По прошлому примеру могло показаться, что для четвёртого типа 24 заданий лучше всего использовать метод замены и разделения. Но это так. В некоторых заданиях регулярные выражения показывают себя куда лучше.
Примером будет такое задание:
«Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита.
Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых буква F встречается ровно 76 раз, чётная цифра встречается ровно один раз, искомая последовательность начинается с этой единственной чётной цифры.»
Если решать это задание методом замены и разделения, то придётся сделать замены для каждой чётной цифры, затем разделить всю строку по четной цифре на фрагменты. Далее в цикле перебирать каждый фрагмент и подсчитывать максимальное количество символов, среди которых будет ровно 76 «F». Всё это долго и не эффективно.
Регулярные выражения здесь отрабатывают куда быстрее.
Начнём с определения шаблона для чётных цифр:
Теперь напишем шаблон поиска всех остальных символов кроме «F» и чётных цифр:
Итак, после четной цифры должны идти любые символы, кроме четных цифр и «F» (это наша группа not_F_evens) в количестве 0 и более, а после них уже буква «F»:
И таких групп должно быть ровно 76. А после них уже могут идти все те же not_F_evens в количестве 0 и более штук. Итоговый шаблон выглядит так:
Подставляем его в наше базовое решение:
Запустим программу и получим ответ — число 163.
Пример 3
И последний пример 24 заданий:
«Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита.
Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых подстрока 2025 встречается не менее 90 раз и при этом содержится ровно 80 букв Y.»
Это одна из самых сложных формулировок 24 заданий. Просто так разделить строку здесь не получится, так что первый способ отметаем.
Чаще всего для решения таких заданий применяется метод двух указателей. Но мы всё же покажем, как здесь можно применить регулярные выражения, правда, не совсем в привычном стиле.
Подход у нас будет такой:
- Сначала находим позиции всех букв «Y» в строке;
- Перебираем все возможные «окна» из 80 подряд идущих букв «Y»;
- Для каждого окна расширяем границы влево и вправо, захватывая все символы между соседними «Y»;
- Проверяем условие про «2025» и ищем максимальную длину.
Открываем файл:
Теперь отдельно вынесем основные константы:
- Количество букв Y — переменная K;
- Искомая буква — переменная letter;
- Количество подстрок — переменная need;
- Сама подстрока —переменная sub.
Находим позиции всех букв «Y» в строке:
Например, для строки «AYBYYC» получим список «[1, 3, 4]» — это индексы, на которых стоят буквы Y.
Теперь создадим переменную для хранения максимальной длины и запустим цикл. В нём будем перебирать все возможные «окна» из K подряд идущих букв «Y». Если всего найдено, например, 100 букв «Y», а нам нужно ровно 80, то возможных окон будет 100 — 80 + 1 = 21.
Переменная i — это индекс первой буквы «Y» в текущем окне (индекс в списке pos, не в строке). Определяем границы текущего окна:
- left — позиция первой буквы «Y» в окне (это i-я буква «Y» в строке)
- right — позиция последней буквы «Y» в окне (это i + K — 1-я буква «Y»)
Например, если i = 0 и K = 80, то мы берём буквы «Y» с индексами от 0 до 79 в списке pos.
Теперь у нас будут два блока кода для расширения границ. Сначала расширяем влево. Начинаем с позиции первой «Y» и двигаемся влево, пока не встретим другую букву «Y» или не дойдём до начала строки.
Зачем это нужно? Между нашей первой «Y» и предыдущей «Y» могут быть другие символы (цифры, другие буквы). Мы хотим захватить их все, чтобы получить максимально длинную подстроку. Но останавливаемся перед предыдущей «Y», иначе в подстроке станет 81 буква «Y».
Аналогично расширяемся вправо:
Далее вырезаем подстроку от позиции l до позиции r включительно. То есть от двух наших границ.
Полученная подстрока содержит ровно K букв «Y» (мы расширяли границы только до соседних «Y», не включая их). Осталось лишь проверить, что в подстроке не менее 90 вхождений «2025». Если это условие выполняется, сравниваем длину с текущим максимумом и обновляем его при необходимости. В конце выводим значение max_len:
Запускаем программу и довольствуемся ответом — 2981.
Давайте резюмируем, что происходит в этом коде. Это стандартный алгоритм скользящего окна, который мы оптимизируем за счёт предварительной индексации искомого символа.
Вместо того чтобы перебирать весь текст целиком, мы выписываем индексы, где встречается буква «Y». Теперь мы можем мгновенно перемещаться от одной «Y» к другой.
Далее берём фрагменты по 80 букв «Y», как мы это делали с заменой и разделением строки. Но дальше нужно «растягивать» границу вправо и влево. Мы захватываем все цифры и другие буквы, пока не упремся в соседнюю букву «Y». Это «раздувает» нашу подстроку до максимума, но количество «Y» в ней остается ровно 80.
Условно, если мы нашли подстроку «Y111Y», то растягиваем в обе стороны, пока не упрёмся в «Y»: «Y00Y111Y00Y» — здесь мы захватили еще по 2 нуля с каждой стороны, не увеличив количество букв «Y».
Теперь, когда у нас в руках максимально длинный кусок с нужным количеством «Y», мы просто считаем, сколько в нем раз встретилось число 2025. Если 2025 встретилось не менее 90 раз — бинго, такая строка нам подходит. Считаем её длину и по необходимости обновляем значение в max_len.
Больше заданий данного типа с подробным решением вы можете найти в нашем тренажёре.