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

Автор SkyHawk, 12 лет назад, По-русски

Сабж. Сегодня, 8 декабря, в 21:00 по Москве.

Удачи вам, дамы и господа!

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

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

Как решать 500? Написал тупую динамику без всяких отсечений, её, разумеется, сломали (правда, с третьей попытки).

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

    Я перебирал циклический сдвиг. Дальше решал задачу для отрезка динамикой z[i][j] — где стоим и сколько должны начиная с нашей позиции выкинуть.

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

      Сколько выкинуть же всегда определено уровнем карты?

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

        У нас могут быть открыты несколько карт.

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

    Посмотрим на итоговый ответ. Понятно, что в нём будет такое i, что среди i + 1, ..., i + li - 1 нет взятых в ответ элементов (в начальной конфигурации; просто возьмём какой-то элемент и пойдём от него направо, пока не упрёмся в требуемый, круг мы сделать не можем). А значит, перебираем элемент-"разрез" и проходимся тупой динамикой с конца разрезанного круга.

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

      не очень понятно, что за тупая динамика?

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

        Ну d[i][j] — мы находимся на i'ом с конца элементе и у нас "в запасе" есть j элементов для удаления; переходы — либо i + 1, j + 1, либо i + 1, j + 1 - li с увеличением урона на d[i]. Но если немного подумать, эта динамика упрощается до выбора элементов с суммой li не больше n, как пишут ниже; т.к. любое такое подмножество можно набрать, пройдя справа налево.

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

    Можно просто выбирать набор карточек с сумой уровней не больше n, c максимальным уроном.

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

    Рюкзак, где вес вещи — li, а стоимость — di. Нужно набрать вещей с суммарным весом не более N.

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

У меня в комнате один из участников посабмитил по easy перебор. Я долго думал как его почеленджить так и не понял. Passed system tests.

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

Это странное чувство, когда на вторую задачу уходит меньше времени, чем на первую...

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

    У меня другое чувство, когда на третью уходит меньше времени, чем на вторую :(

    UPD: А потом еще другое чувство, когда видишь решение в две строчки по 500

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

А как решать 950?

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

    Расскажу свое решение, не претендую на оптимальность асимптотики и времени написание кода. :) Придумал на раунде, но написать не успел и досдал только что в практисе.

    Рассмотрим нашу решетку как детерминированный конечный автомат над алфавитом {L, R, U, D}. Состояниями будут вершины сетки, в которых нет препятствия, а также будет сток, который будет допускающим состоянием. Переходы из состояния по каждой букве ведут в ту вершину, куда сместилась бы монетка на этой позиции при заданном действии. Если она падает со стола, направим ребро в сток.

    Когда положение монет хорошее? Когда есть 2 монеты, которые лежат на неэквивалентных состояниях (ибо есть различающая их строка, а значит, одна упадет, а другая -- нет). Посчитаем, сколько таких расстановок (точнее, посчитаем все и вычтем плохие). Плохие — это когда монетки лежат на позициях, соответствующих эквивалентным состояниям. Вычтем в таком случае из ответа 2cnt - 1, где cnt -- количество вершин в каком-то классе эквивалентности. Итого, , где cnti — количество вершин в i классе эквивалентности вершин в автомате, и .