Блог пользователя Gantz

ACM ICPC Northern Subregional Contest 2011
Автор Gantz, 13 лет назад, По-русски

Доброе утро!

29-го октября прошел четвертьфинал в Питере и еще в Казахстане, Узбекистане и Грузии.

Вот условия

Где можно прочитать разбор по этим задачам? И если можно, то напишите здесь разбор для E, G, H и К.

Заранее спасибо!)

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

По задаче H.
Переберем 2^5 масок. Определим сколько пар строк совпадают по каждой маске. Единичные биты маски определяют какие символы мы будем сравнивать. Для каждой маски кол-во совпадающих пар считается просто. Посчитаем хэши полученных строк из данной и сложим в map, т.е. посчитаем кол-во каждых хэшей (т.к. огранчения маленькие можно даже не считать хэши, а складывать сразу строки). Тогда, если кол-во какого-то хэша равно n, то к ответу по маске мы прибавляем n*(n-1)/2
Пусть ответы хранятся в count[mask]

Далее вступает в дело формула включения-исключения. Будем считать правильные ответы и хранить их в acount[mask]. Для каждой маски переберем надмаску (omask). Надмаска omask это такая маска, что (omask & mask) == mask.
Если разница кол-ва бит надмаски и подмаски нечетна , то от ответа отнимает count[omask] : acount[mask]-=count[omask], иначе прибавляем count[omask] : acount[mask]+=count[omask]. Если не понятно почему это так, лучше почитать сначала статью на e-maxx про принцип включения-исключения.

Теперь мы посчитали для каждой маски, какое кол-во пар имеет ровно 1 совпадающий символ, 2, 3 и т.д.

Финальный ответ высчитывается просто. Для каждой маски ans[5-bitCount(mask]]+=acount[mask]. Ответ для строк у которых не совпадает ничего - n*(n-1)/2 - сумма всех просчитанных ответов.

Код: http://pastebin.com/B5Y7kbjr

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Все верно. Для строк можно было не только хеши считать, но и сортировать - тоже проходило по времени. 
    Еще совет по коду - в Java есть замечательный метод Integer.bitCount(x);
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Задача G.
Покрасим начальный цикл во все k цветов: i-ую вершину в i-ый цвет. Дальше делаем обход графа (bfs, dfs) от этого цикла. Будем поддерживать такую раскраску, чтобы из каждой вершины существовал путь из цветов вида: p, p+1, ..., k, 1, ..., p-1. На начальном цикле, это, очевидно, выполняется. Чтобы поддерживать эту раскраску, каждую вершину надо красить в цвет = {цвет одного из соседей - 1} (если цвет получился равным 0, то меняем на k).
Допустим у текущей вершины есть сосед, покрашенный в цвет q. Значит можно покрасить в цвет q-1. Но у вершины может быть другой сосед, покрашенный в этот цвет. Тогда можно покрасить в цвет q-2. Если есть сосед цвета q-2, то можно покрасить в цвет q-3, и т.д. Так как у вершины строго меньше, чем k соседей, то в конце концов найдем свободный цвет.
Таким образом красим весь граф.
→ Ответить