Задача A. Игра в автобусе (автор - rng_58)
В этой задаче прекрасно работает симуляция "в лоб" - нам прямым текстом сказано, как ходят игроки. Лиса Кейл играет по следующей стратегии: если есть хотя бы две монеты по 100 йен и две монеты по 10 йен, она берёт их. Иначе, если есть хотя бы одна монета по 100 йен и 12 монет по 10 - она забирает их. В противном случае она берет 22 монеты по 10 йен. Если ей это не удаётся - выигрывает Ханако. Кролик поступает точно также, но в обратном порядке. Сложность решения - O(x+y).Задача B. Разноцветное поле (автор - ir5)
Решение, использующее массив NxM получает TL/ML, и, разумеется, мы не можем решать задачу "в лоб". Так как и запросов, и безжизненных клеток не более 1000, нам достаточно научиться отвечать на каждый запрос за время O(K).Пусть (a, b) - клетка из очередного запроса. Является ли она безжизненной, или нет - решит один цикл for по входным данным.
Итак, мы знаем, что на этой клетке что-то растёт. Пусть I - суммарное число клеток перед (a, b), а J - количество безжизненных клеток перед (a, b). Тогда ответ определяется значением (I-J) mod 3 (где 0 => "Carrots", 1 => "Kiwis", 2 => "Grapes"). Путем несложной математики можно понять, что I=(a-1)M+(b-1) (первое слагаемое - это количество клеток в предыдущих строках, а второе - количество предыдущих клеток в текущей строке), а величину J можно опять же подсчитать циклом for за O(K).
Получаем решение за O(TK), где T - количество запросов.
Задача C. Скучные строки (автор - ir5)
Мы можем представить каждую подстроку в s, совпадающую с какой-либо скучной строкой, как "запрещённый отрезок". Таких кандидатов в плохие отрезки для каждой из bi порядка O(n), поэтому мы можем подсчитать их все за O(|s|· n· |bi|) (да, тут не требуется никаких специальных алгоритмов, например, КМП).Теперь мы можем переписать задачу по-другому: дано не более 106 запрещенных отрезков, найти отрезок, который не содержит полностью ни один из запрещённых.
Давайте подсчитаем величину right[i] - минимальная правая граница среди запрещенных интервалов с левой границей в i. Если таких интервалов нет, положим right[i]=|s|.
Теперь давайте переберём начало ответа, начиная с |s| и до 0. Вначале ответ - пустая строка. Пусть ответ для предыдщего начала - подстрока с i+1 до j. Тогда, если right[i]>j, то мы можем спокойно приписать один символ слева и ответ увеличивается на 1 - подстрока с i до j. Если же right[i]<=j, то ответ не может быть дальше, чем до right[i]-1, в противном случае мы полностью покроем "плохой отрезок". Таким образом, мы пробежимся по всем возможным началам ответов за O(|s|).
Итого время работы - O(|s|· n· |bi|).
Задача D. Кодовый замок (автор - rng_58)
Давайте слегка переформулируем состояние замка: определим массив bi следующим образом: bi = 0, если панели i и i + 1 находятся в одинаковом состоянии и bi = 1 в противном случае. Положим, что панели 0 и n + 1 выключены (OFF). Если Кейл изменяет состояние панелей на отрезке с x до x+a-1 (включительно), то в массиве b изменяются значения bx и bx + a:
Задача D'.
У Вас есть массив bi. Не более 20 (=2k) элементов - единички. За каждый ход Вы можете изменить значения в bx и bx + a, где a - элемент ai и 0 ≤ x ≤ n - a. Определите минимальное количество ходов, требуемое для обнуления массива (мы просто "перевернули" порядок действий).
Понятно, что порядок ходов не важен. Также понятно, что если массив еще не обнулён, то есть такой индекс x, что bx = 1, и нам придётся походить, задев этот индекс, хотя бы один раз. Давайте следаем этот ход первым. Далее применим аналогичное рассуждение и получим, что на каждом ходу хотя бы одно из двух чисел bx и bx + a - единица.
Задача D''.
Теперь давайте построим граф с вершинами от 0 до n+1. Ребро между двумя вершинами v1 и v2 будет в том, и только том случае, если |v1 - v2| - элемент массива ai (то есть, мы можем сделать ход bv1 и bv2. Также изначально есть не более 20 фишек (стоят в позициях изначальных единиц в массиве bi). За один ход мы можем подвинуть фишку по какому-либо ребру. Если две фишки оказываются в одной вершине, они исчезают. Определить минимальное количество ходов, необходимое для избавления от всех фишек.
Для начала предподсчитаем попарные расстояния между всеми фишками. Это можно сделать, 20 раз запустив BFS. А далее имеем динамику по подмножествам: d[S] (где S - подмножество фишек) - минимальное количество шагов, чтобы убрать все фишки из S. Если S пусто, d[S=0]=0. Если S = {s0, s1, ..., sm - 1} непусто, то мы выбирае фишки, которая исчезнет вместе с нулевой, и делаем переход: d[S] = min(d[S\{s0, si}] + dist(s0, si)), где 1 ≤ i ≤ m - 1.
Итоговая сложность решения - O(knl + k· 22k).
Задача D'.
У Вас есть массив bi. Не более 20 (=2k) элементов - единички. За каждый ход Вы можете изменить значения в bx и bx + a, где a - элемент ai и 0 ≤ x ≤ n - a. Определите минимальное количество ходов, требуемое для обнуления массива (мы просто "перевернули" порядок действий).
Понятно, что порядок ходов не важен. Также понятно, что если массив еще не обнулён, то есть такой индекс x, что bx = 1, и нам придётся походить, задев этот индекс, хотя бы один раз. Давайте следаем этот ход первым. Далее применим аналогичное рассуждение и получим, что на каждом ходу хотя бы одно из двух чисел bx и bx + a - единица.
Задача D''.
Теперь давайте построим граф с вершинами от 0 до n+1. Ребро между двумя вершинами v1 и v2 будет в том, и только том случае, если |v1 - v2| - элемент массива ai (то есть, мы можем сделать ход bv1 и bv2. Также изначально есть не более 20 фишек (стоят в позициях изначальных единиц в массиве bi). За один ход мы можем подвинуть фишку по какому-либо ребру. Если две фишки оказываются в одной вершине, они исчезают. Определить минимальное количество ходов, необходимое для избавления от всех фишек.
Для начала предподсчитаем попарные расстояния между всеми фишками. Это можно сделать, 20 раз запустив BFS. А далее имеем динамику по подмножествам: d[S] (где S - подмножество фишек) - минимальное количество шагов, чтобы убрать все фишки из S. Если S пусто, d[S=0]=0. Если S = {s0, s1, ..., sm - 1} непусто, то мы выбирае фишки, которая исчезнет вместе с нулевой, и делаем переход: d[S] = min(d[S\{s0, si}] + dist(s0, si)), где 1 ≤ i ≤ m - 1.
Итоговая сложность решения - O(knl + k· 22k).
Комментарии (0)
