266A - Камни на столе

В этой задаче нужно было посчитать количество пар подряд идущих одинаковых букв. Это можно сделать в один цикл за время O(N).

266B - Очередь в школе

В этой задаче нужно было аккуратно реализовать процесс, описанный в условии. Нужно было t раз обменять два элемента i и i + 1 местами, если на i-ом месте стоял мальчик, а на i + 1-ом стояла девочка. Главное, не нужно было одну девочку двигать влево несколько раз за одну итерацию. Решение можно реализовать за O(N·T).

266C - Ниже диагонали

Эту задачу будем конструктивно, даже скорее используя индуктивный подход. В начальный момент у нас есть квадратная матрица размера n и n - 1 единица в ней. Следовательно, существует столбец, в котором нет ни одной единицы. Поставим этот столбец на n-ое место. Таким образом, правый нижний элемент будет равен 0. Теперь найдем любую строку, в которой есть хотя бы одна единица, и поставим ее на n-ое место.

Мы добились того, что в клетке (n, n) стоит 0, а также в последней строке стоит хотя бы одна единица. После этого можно уменьшить размерность задачи, то есть n:  = n - 1. Заметим, что в этой задаче у нас будет не более n - 2 единиц, следовательно эту задачу решить аналогичным образом. Когда n окажется равным 1, алгоритм нужно завершить, поскольку в первой строке будет 0 единиц. Всего у нас получается O(N) операций swap, не более двух для каждого n.

266D - БерДональдс

Расскажу несколько идей решения этой задачи. Сначала предложим решение за O(N⁴). Переберем ребро (u, v) длины len, на котором окажется точка из ответа. Пусть эта точка находится на этом ребре на расстоянии x от вершины u. Тогда расстояние до любой другой вершины i равно min(x + d[u][i], len–x + d[v][i]), где d[x][y] — расстояние между вершинами x и y. Приравняем эти величины, посчитаем критическое значение величины x для вершины i, получим x = (len + d[v][i]–d[u][i]) / 2. Отсюда видно, что ответ на задачу полуцелый. Таким образом, для каждого ребра и для каждой вершины получим набор таких критических точек. Проверим каждую из них помимо самих вершин графа (границы отрезка). Возможно такое решение вполне реально сдать, добавив какие-нибудь оптимизации или идеи.

Также можно было решать задачу за O(N³·log²). Умножим веса всех ребер на 2. Теперь переберем ребро, на котором находится ответ и сделаем бинарный поиск по ответу (уже в целых числах). Чтобы проверить текущий ответ, нужно перебрать вершину i, считая что ответ достигается в этой вершине. Тогда получим, что точка на этом ребра должна лежать либо <= какого-то l[i], либо >= какого-либо r[i]. Эта подзадача решается в оффлайне с помощью сортировки событий и поддержания баланса.

Также можно было попытаться сдать тернарный поиск на каждом из ребер графа. Однако, поскольку в чистом виде он работает неправильно, нужно было разбить ребро на некоторое количество отрезков и искать на каждом из них.

Последние два решения проходили, если их аккуратно реализовать. Еще отмечу, что также есть решение за время O(N³) автора задачи RAD.

266E - Опять запросы к массиву...

Эта задача решается с помощью структуры данных. Будем использовать дерево отрезков, причем будем поддерживать k деревьев отрезков для каждой из степеней. В вершине будем поддерживать взвешенную сумму с соответствующей степенью, а также число, которое означает цвет всего отрезка, если такой есть.

Пользователь Egor в комментариях к посту, а также пользователь mexmans в комментариях к разбору, описывали свои формулы для получения ответа. Постараюсь объяснить как их можно получить. Во-первых нужно выписать, что умеет в качестве запроса считать ваше дерево отрезков. Оно умеет получать сумму . Вам же нужно посчитать , можно записать как . Теперь нужно расписать на листочке последнюю сумму для первых степеней, хотя бы до трех, и отнять из первой суммы (ответ на запрос дерева) вторую (то что нужно получить). Получится выражение, которое нужно вычесть из числа запроса для получения ответа на задачу. Это просто бином Ньютона без старшей степени.

Таким образом, ответ для степени j выражается как разность числа запроса и бинома Ньютона со всеми степенями, которые меньше j (эти значения также можно запрашивать вашим деревом отрезков). Частичные суммы степеней и сочетания нужно заранее предпосчитать. Решение имеет сложность O(N·K·log(N)).