Участки G и C
Геном читают как строку из букв A, C, G и T, и состав букв в нём меняется кусками: где-то больше G и C, где-то — A и T. Модель с двумя скрытыми состояниями размечает каждую букву: состояние 0 — «здесь богато G и C», состояние 1 — «здесь богато A и T». Каждая буква в каждом состоянии приносит свои очки — логарифм того, насколько вероятна эта буква в таком участке, — а смена состояния между соседними буквами стоит штраф P.
Найдите разметку с наибольшим счётом: сумма очков всех букв в их состояниях минус P за каждую смену. Начинать можно с любого состояния.
В большинстве тестов — геномы фагов λ, HK97, HK022 и φX174 и митохондрии человека, а очки — как в статье: участок с 58 % букв G и C против участка с 40 %.
Вход
В первой строке — P (0 ≤ P ≤ 106). Во второй — очки букв A, C, G, T в состоянии 0, в третьей — в состоянии 1 (целые, по модулю не больше 1000). В четвёртой — строка из букв A, C, G, T длиной от 1 до 2·105.
Выход
В первой строке — наибольший счёт. Во второй — разметка: строка из нулей и единиц, по символу на букву. Если лучших разметок несколько, выведите любую.
Примеры
Пример 1
100 -25 21 21 -25 26 -32 -32 26 ATATTATAAGCGCGGCGCCGGATATAATTA
520 111111111000000000000111111111
Пример 2
1000 -25 21 21 -25 26 -32 -32 26 ATATTATAAGCGCGGCGCCGGATATAATTA
84 111111111111111111111111111111
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если бы смена состояния ничего не стоила, каждой букве можно было бы выбрать лучшее состояние отдельно. Что меняет штраф? Попробуйте второй пример: та же строка, но смена стоит 1000.
2Подсказка 2
Пусть известен лучший счёт разметки первых i букв, которая кончается состоянием 0, и такой же для состояния 1. Как из этих двух чисел получить два числа для i + 1 буквы?
3Идея
Обозначим Vi(s) лучший счёт разметки первых i букв, где буква i в состоянии s. Последний шаг такой разметки — либо остаться в s, либо перейти в него из другого состояния, заплатив P:
Vi(s) = очки(s, буква i) + max(Vi−1(s), Vi−1(другое) − P), V0 = 0.
Остаток лучшей разметки обязан быть лучшим среди разметок того же начала, кончающихся тем же состоянием: иначе его можно заменить и улучшить всё. Это и есть алгоритм Витерби для двух состояний. Чтобы восстановить саму разметку, для каждой буквы и каждого состояния запоминаем, откуда пришли, и идём назад от лучшего из двух чисел в конце.
4Разбор
Два числа на букву и два бита «откуда пришли». В первом примере в середине строки стоят двенадцать букв G и C подряд: каждая в состоянии 0 приносит 21 очко вместо −32, итого 636 очков разницы на кусок, а две смены стоят 200 — выгодно переключиться. Во втором примере две смены стоят 2000, и выгоднее всю строку оставить в состоянии 1. На геноме фага λ лучший счёт — 38 498 и шесть участков, как в листинге статьи.
4+Решение
5Сложность
O(n) времени: два сравнения на букву. Память — O(n) битов на обратный ход: по два бита на букву хватает, это 50 КБ на 200 тысяч букв. Если нужен только счёт, хватит двух чисел.
6Типичные ошибки
- Лучшее состояние для каждой буквы отдельно. Так поступают, когда штраф не учтён: получится разметка с бесчисленными сменами и плохим счётом. Второй пример ловит это сразу.
- Сумма очков вместо логарифмов. Очки уже логарифмы: их складывают. Перемножать нечего.
- Рекурсия по буквам. 2·105 вложенных вызовов Python не выдержит; цикл — выдержит.
- Штраф на старте. Первая буква может быть в любом состоянии бесплатно. Если обязательно начинать с состояния 0 или брать штраф за «вход» в состояние 1, во втором примере выйдет −198 вместо 84: вся строка в состоянии 0.