Модуль: Скользящее окно и два указателя

Разбор

Анализ условия

• «ровно 160 раз» → используем метод через позиции
• «максимальное» → для каждого набора из 160 пар находим максимальное расширение
• Считаем пары CD, а не отдельные символы

Идея решения

Шаг 1: Собираем позиции всех пар CD

Строка: A C D X C D Y C D Z C D
        0 1 2 3 4 5 6 7 8 9 10 11

Пара CD на позиции p означает: s[p]='C' и s[p+1]='D'

Позиции CD: [1, 4, 7, 10]

Шаг 2: Перебираем «окна» из k=160 подряд идущих пар

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

Шаг 3: Формулы для границ

cd_pos = [позиции всех пар CD]

Берём пары с индексами i, i+1, ..., i+k-1
  - Первая пара: cd_pos[i]
  - Последняя пара: cd_pos[i+k-1]

Левая граница (min_left):
  - Должна исключить предыдущую пару cd_pos[i-1]
  - Пара на позиции p занимает s[p] и s[p+1]
  - Чтобы исключить пару, достаточно не включить s[p] (букву 'C')
  - Значит: min_left = cd_pos[i-1] + 1

Правая граница (max_right):
  - Должна исключить следующую пару cd_pos[i+k]
  - Чтобы исключить пару на позиции p, достаточно не включить s[p+1] (букву 'D')
  - Можно включить s[p] (букву 'C'), но не s[p+1]
  - Значит: max_right = cd_pos[i+k]

Визуализация на примере

Строка: A C D X C D Y C D Z C D
        0 1 2 3 4 5 6 7 8 9 10 11
          ↑     ↑     ↑     ↑
         p=1   p=4   p=7   p=10

cd_pos = [1, 4, 7, 10]

Пусть k = 2, берём пары с индексами i=1 и i+1=2
То есть пары на позициях cd_pos[1]=4 и cd_pos[2]=7

Левая граница

Предыдущая пара: cd_pos[i-1] = cd_pos[0] = 1

Строка: A C D X C D Y C D Z C D
        0 1 2 3 4 5 6 7 8 9 10 11
          ^─^
          пара, которую надо ИСКЛЮЧИТЬ

Чтобы исключить пару на позиции 1:
  - НЕ включаем s[1]='C'
  - min_left = 1 + 1 = 2

Строка: A C D X C D Y C D Z C D
            ↑
          min_left = 2

Подстрока начинается с 'D' — пара CD на позиции 1 НЕ захвачена ✓

Правая граница

Следующая пара: cd_pos[i+k] = cd_pos[3] = 10

Строка: A C D X C D Y C D Z C D
        0 1 2 3 4 5 6 7 8 9 10 11
                              ^──^
                              пара, которую надо ИСКЛЮЧИТЬ

Чтобы исключить пару на позиции 10:
  - НЕ включаем s[11]='D'
  - МОЖНО включить s[10]='C'
  - max_right = 10

Строка: A C D X C D Y C D Z C D
        0 1 2 3 4 5 6 7 8 9 10 11
                              ↑
                          max_right = 10

Итоговая подстрока

Строка: A C D X C D Y C D Z C  D
        0 1 2 3 4 5 6 7 8 9 10 11
            ↑               ↑
          left=2        right=10

Подстрока: s[2:11] = "D X C D Y C D Z C"
Длина: 10 - 2 + 1 = 9
Пар CD: 2 (на позициях 4 и 7) ✓

Почему +1 слева и без -1 справа?

Разбор пары CD на позиции p

Позиция:     p    p+1
Символ:      C     D
             ↑     ↑
           нужен  нужен
           чтобы  чтобы
           пара   пара
           была   была

Чтобы ИСКЛЮЧИТЬ пару слева (позиция p):

Варианты начала подстроки:

left = p:     [C D ...     — пара ЗАХВАЧЕНА ✗
left = p+1:   [D ...       — пара НЕ захвачена ✓ (нет 'C')

Вывод: min_left = p + 1

Чтобы ИСКЛЮЧИТЬ пару справа (позиция p):

Варианты конца подстроки:

right = p+1:  ...C D]      — пара ЗАХВАЧЕНА ✗
right = p:    ...C]        — пара НЕ захвачена ✓ (нет 'D')
right = p-1:  ...]         — пара НЕ захвачена ✓

Для максимальной длины берём right = p

Вывод: max_right = p

Код решения

def solve_296(filename):
    with open(filename) as f:
        s = f.read().strip()
    
    k = 160
    
    # Шаг 1: Собираем позиции всех пар CD
    cd_pos = []
    for i in range(len(s) - 1):
        if s[i] == 'C' and s[i + 1] == 'D':
            cd_pos.append(i)
    
    # Проверка: достаточно ли пар
    if len(cd_pos) < k:
        return 0
    
    max_len = 0
    
    # Шаг 2: Перебираем все "окна" из k пар
    for i in range(len(cd_pos) - k + 1):
        # Пары с индексами i, i+1, ..., i+k-1
        
        # Левая граница: после предыдущей пары
        if i > 0:
            min_left = cd_pos[i - 1] + 1  # исключаем 'C' предыдущей пары
        else:
            min_left = 0  # нет предыдущей пары
        
        # Правая граница: до следующей пары
        if i + k < len(cd_pos):
            max_right = cd_pos[i + k]  # включаем 'C', но не 'D' следующей пары
        else:
            max_right = len(s) - 1  # нет следующей пары
        
        # Шаг 3: Вычисляем длину
        length = max_right - min_left + 1
        max_len = max(max_len, length)
    
    return max_len


print(solve_296("24-296.txt"))  # Ответ: 1288

Сложность

• Время: O(n) — один проход для сбора позиций + один проход по позициям
• Память: O(m) — где m = количество пар CD

Итоговая шпаргалка

┌─────────────────────────────────────────────────────────────┐
│  ЗАДАЧА: Максимальная подстрока с РОВНО k парами XY        │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1. Собрать позиции всех пар XY                             │
│                                                             │
│  2. Для каждого окна из k пар [i, i+k-1]:                   │
│                                                             │
│     min_left  = positions[i-1] + 1    (исключить 'X')       │
│     max_right = positions[i+k]        (исключить 'Y')       │
│                                                             │
│  3. Длина = max_right - min_left + 1                        │
│                                                             │
└─────────────────────────────────────────────────────────────┘

Ответ: 1288

Обсуждения (0)

Решения (0)

Решения: