Блог пользователя coder.ua

HSIN COCI Contest#6
Автор coder.ua, 12 лет назад, По-русски

Предлагаю здесь обсуждать задачи и результаты.

Как выводить сами отрезки в четвертой и как делать последнюю на 70 или 100%? Ну и, собственно — кто как написал?

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

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

В четвертой можно было выводить отрезки (5000, i) — (i, -5000) для i начиная от 4999. Я, правда, вместо этого написал извращенную жадность, которая соединяла верхнюю и нижнюю стороны отрезками, а затем забил массив констант.

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Правду говорят, утро вечера мудренее. Вчера за полтора часа на контесте не придумал нормальное решение последней, а с утра за 10 минут пришло в голову.

Идея следующая. В начале для каждой маски запишем величину g(mask) — сколько есть ящиков, в которых лежит такая маска игрушек. После этого, для всех масок посчитаем величину f(mask), которая равна сумме g(s) по всем s — подмаскам mask. Теперь ответ будем искать по формуле включений-исключений: всего есть 2^n наборов. Вычтем из этого количества те наборы, которые не покрывают каждый отдельный бит. Затем прибавим те, которые не покрывают все пары и т.д.. При нормальной реализации это все работает за O(nm + 2^m * m).

Вот код.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "после этого, для всех масок посчитаем величину f(mask), которая равна сумме g(s) по всем s — подмаскам mask" а как считать такое не за 3^m?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Рассмотрим следующую динамику: f(mask, pos) — сумма по всем g(s), для которых первые pos бит маски s являются подмаской первых pos бит маски mask, а оставшиеся биты совпадают с соответствующими битами маски mask. Тогда пересчитывать ее можно так:

      f(mask, pos) = f(mask, pos - 1), если pos-й бит равен 0,

      f(mask, pos) = f(mask, pos - 1) + f(mask \ {pos}, pos), если pos-й бит равен 1.

      Легко заметить, что второй параметр нам не нужен. Можно это все хранить в одном одномерном массиве:

      for (int i = 0; i < m; ++i)
   for (int mask = 0; mask < (1 << m); ++mask)
       if (mask & 1 << i) g[mask] += g[mask ^ 1 << i];

      После выполнения этого куска кода в массиве g как раз и будут искомые суммы по всем подмаскам.

      → Ответить