И снова привет, Codeforces! С ощутимым перерывом, но всё же выходит следующий разбор из серии "Как додуматься до..."
Этот пост посвящён задаче B2. Юкари Якумо и камни границы из Div 2 раунда, которую я встретил в параллельном Div 1 раунде на первой позиции и, немного удивившись сложности, решил подготовить небольшой рассказ о ней.
Задача имеет первую часть и формулируется следующим образом: у героя есть суммарно $$$n \leq 100$$$ камней, какие-то маленькие, какие-то большие, но мы не знаем сколько каких. В задаче есть две операции. За операцию, обозначаемую символом '+', герой может выбрать какой-то камень. Если он маленький, то становится большим, а иначе большой камень раздваивается в два больших. Для операции символа '-' большой камень становится маленьким, а маленький камень удаляется.
Но вот какие операции будут выполняться выбираем мы: мы готовим строку из '+' и '-' длины от 1 до 999 и передаём герою. Он выбирает в ней префикс и выполняет операции из него слева направо, максимизируя итоговое количество камней после всех операций.
Фактически, герой говорит в ответ на строку, префикс какой длины максимизирует итоговое количество камней при оптимальном выполнении операции. Если таких несколько, то сообщает длину наименьшего из них. Требуется по этому ответу понять, сколько у героя маленьких камней, а сколько больших.
Фууух, так много слов на условие пока что у меня не уходило. Ну что ж, давайте разбираться. Мы герою — строку. Он для каждого префикса понимает сколько камней может получить, исполнив префикс, и сообщает нам оптимальный префикс. А понимаем ли мы сами по префиксу, сколько можно обеспечить камней?
Вопрос 1: Если нам дана фиксированная строка, какое наибольшее число камней можно получить, выполнив команды в ней слева направо?
Подсказка 1.1Какой камень выгодно выбирать для операции '+'?
Ответ 1.1Если есть большой камень, нужно выбирать его, так как, в сравнении с альтернативой выбора маленького камня у нас в итоге получается на 1 маленький камень больше. Это уже строго доказывает, что такой выбор не хуже
Подсказка 1.2Какой камень выгодно выбирать для операции '-'? Внимательно посмотрите на случай, когда остался ровно 1 большой камень
Ответ 1.2На первый взгляд кажется, что ответ зависит от того, что будет в строке дальше. Ясно, что если больших камней больше одного, то нужно выбирать их, так как в этом случае мы не уменьшаем число камней и сохраняем оптимальный ход для команды '+'. Также не возникает вопросов, если остались только маленькие камни. А вот если остался 1 большой камень, то есть 2 варианта: 1. Если это последний символ строки, то нужно выбирать большой камень 2. Иначе нужно выбирать маленький камень, чтобы сохранить оптимальный ход для операции '+'. Лучше сейчас удалить маленький камень, чем потом лишиться возможности получить большой
Сразу бросается в глаза, что если бы не вариант 1, то мы бы просто выполняли жадным алгоритмом операции и количество камней на очередном шаге было бы ответом для префикса. Как бы нам избавиться от него?
Подсказка 1.3Какое условие задачи позволяет просто выкинуть из рассмотрения префиксы, оканчивающиеся на '-'?
Ответ 1.3Нас интересует самый короткий префикс, после которого получается как можно больше камней, но такой префикс не может оканчиваться на '-', поэтому мы можем просто не рассматривать такие префиксы. А значит наш жадный алгоритм имеет место для восстановления ответа на задачу
Итак, мы поняли как считается ответ, выдаваемый системой, в зависимости от стартового числа камней. Получилось довольно удобным то, что это правило довольно простое. Но нам всё ещё нужно научиться выдавать такую строку, по ответу на которую можно однозначно определить количество камней обоих типов у героя.
Так как суммарное число камней известно, я предлагаю пытаться установить, сколько больших камней было у героя. Но так как сходу не ясно как это сделать, давайте чуть упростим задачу
Вопрос 2: Если бы вам можно было сделать не 1 запрос, а несколько, как тогда восстановить количество больших камней?
Подсказка 2.1Интуитивно кажется, что количество больших камней определяет то, как много операций '-' можно применить без уменьшения числа камней.
Подсказка 2.2Если вывести строку из $$$k$$$ минусов и плюса в конце, что даст ответ на такой запрос?
Ответ 2.2Во-первых, ответ на этот запрос либо 0, либо $$$k+1$$$, так как все остальные префиксы заканчиваются на '-'. И $$$k+1$$$ он только в том случае, если изначально у героя больше чем $$$k$$$ больших камней. Иначе ему пришлось бы удалить один маленький камень, но тогда префикс длины $$$0$$$ давал бы результат не хуже, чем длины $$$k+1$$$
Как теперь такими запросами восстановить число больших камней?
Подсказка 2.3Это можно сделать всего за $$$log(n)$$$ запросов.
Ответ 2.3Теперь, умея проверять, правда ли больших камней больше, чем $$$k$$$, мы можем бинарным (да и линейным тоже, я же вас не ограничивал в количестве запросов) поиском найти точное число таких камней.
Вопрос 3: Как теперь справиться за 1 запрос?
Подсказка 3.1Бинарный поиск в этот раз подходит плохо, ведь строка одна, а значит все объединённые запросы придётся подготовить сразу. Попробуйте реализовать в этой строке линейный поиск ответа
Ответ 3.1Для линейного поиска предлагается построить строку так, чтобы для каждого следующего префикса, оканчивающегося на '+', разница минусов и плюсов в нём была на 1 больше, чем у предыдущего. Тогда, пока эта разность меньше, чем число больших камней, каждый следующий '+' позволяет получить на один камень больше, чем все предыдущие префиксы. А после этого максимальное число камней перестаёт расти: чтобы выполнить очередные минусы, приходится удалять маленькие камни. Значит оптимальный префикс будет содержать лишь те плюсы, которые увеличивают максимальное число камней, а позиция последнего такого плюса определяет число больших камней.
Попробуйте сами построить такую строку.
Ответ 3.2Из такого описания уже несложно придумать строку, а именно взять '+--' и повторить $$$n + 1$$$ раз. Если префикс из ответа оканчивается на $$$i$$$-том по счёту плюсе, то изначально у героя $$$i$$$ больших камней. Соответственно, при ответе $$$0$$$ больших камней нет вовсе.
Вот и всё, теперь мы научились решать такую забавную интерактивную задачу. Надеюсь, вам понравилось читать разбор и думать над задачей в процессе. Желаю всем читателям дальнейших успехов на раундах Codeforces!
Замечание: Если вам понравился этот пост, то, возможно, вам понравится контент из телеграм-канала, в который я выкладываю свою подготовку к финалу ICPC 2026. Переходите по ссылке
Автокомментарий: текст был обновлен пользователем machine_solution (предыдущая версия, новая версия, сравнить).