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

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

Завершился первый раунд SNWS 2013.

Давайте обсудим задачи. Интересно, как решалась B.

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

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

И F объясните, пожалуйста, как решалась)))

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

    В F важно понимать, что если мы зафиксировали набор типов граблей, наступанию на которые мы не будем обучаться, то дальше нет разницы, через какие из ных мы перепрыгнем. Значит, заведем динамику f(i, j) — минимальное количество ударов по голове, если мы уже прошли первые i типов граблей и перепрыгнули j раз. Тогда мы либо обучаемся граблям текущего типа, получив ai ударов, при этом ничего не перепрыгиваем, либо же ничему не обучаемся и перепрыгиваем по максимуму, т.е. min(K - j, bi) раз. Сложность O(NK).

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

      Долго хохотал над фразой "минимальное количество ударов по голове" (контест не писал, условия не читал).

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

    Динамика:

    d[i][j], где i -- количество обработанных типов граблей, j -- количество совершенных прыжков Петей.

    Для каждого состояния три перехода:

    1. Мы не тратим прыжки: d[i + 1][j] = min(d[i + 1][j], d[i][j] + a[i])
    2. Если хватает, мы тратим необходимое количество прыжков и не получаем: d[i + 1][j + b[i]] = min(d[i + 1][j + b[i]], d[i][j])
    3. Если не хватает, тратим все оставшиемся прыжки: d[i + 1][k] = min(d[i + 1][k], d[i][j] + b[i] - (k - j))

    Итого: O(NK), исходник: http://pastie.org/5669554

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

В B я перебирал сторону одну прямоугольника (<= N * max(W, H)), а дальше проверял, что если прямоугольник AxB можно замостить карточками WxH, то пробуем улучшить ответ.

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

    если прямоугольник AxB можно замостить карточками WxH,

    Еще раз для тех кто в танке. Как это делать?

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

      Мне подумалось что-то такое: сначала сократим w и h на их НОД, теперь либо w|a и h|b, либо w|b и h|a, либо одно из a и b делится на wh, тогда проверяем, что другое представимо в виде wx + hy, где x, y ≥ 0. Но я это даже не писал, если что.

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

    там можно было проще. пользуясь той фишкой с сазанки, что возможное разбиение можно поделить на две части, перебираем a и b — две части одной стороны. дальше нужно узнать c и d (a*c — прямоугольник со всеми вертикальными, b*d — горизонтальными карточками), а это просто два уравнения ac+bd=n, cw=dh. выражаем d и c отсюда целочисленно, проверяем равенства, обновляем ответ.

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

В B я поверил, что работает динамика по количеству плашек и ширине (т.е. в замощении ничего не цепляется) и написать её, "за куб": перебираем. На самом деле будет работать за какой-нибудь O(N2)/

Unable to parse markup [type=CF_TEX]

, потому что ширина должна быть делителем понятно чего.

Код.

P.S. Пример, когда "цепляется":

112
3.4
344
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

C тоже интересно как решать

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

    У меня была проблема с пониманием условия: я не понял, что нам необязательно проверять всех больных из палаты. Т.е. если k = n, то ответ может быть довольно большим.

    А дальше очевидная кубическая динамика по дереву: сколько максимум из поддерева можно позвать людей, если осталось сколько-то комнат. При пересчёте "обрезаем" это количество по мощности ребра.

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

      Ааааа, это написано в самом конце самого последнего примечания, ну я учту такие подлянки на будущее.

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

Я B решил так:

set < pair<int,int> > a[i] — всевозможные прямоугольники, выраженные парами (длина,ширина), составленные из i карточек.

Теперь просто пробежим по каждому i и для каждого прямоугольника попробуем достроить и получить другой прямоугольник, я делал добавление ряда горизонтальных и вертикальных карточек справа и снизу (это 4 варианта) и ещё можно фиксированный прямоугольник приписать к себе же, причём много раз. Я не доказывал что наборы будут не сильно большой длины, но думаю это можно сделать. Ответ будет лежать в a[n].