Разбор Codeforces Round #350 (Div. 2)

Правка ru14, от fcspartakm, 2016-05-05 21:35:00

670A - Holidays

Данная задача может быть решена несколькими способами. Рассмотрим один из них. Реализуем функцию, которая по стартовому дню года определяет количество выходных в нём. Для этого просто переберем все дни в году начиная с первого и будем проверять текущий день — выходной это день или нет. Несложно понять, что если первый день недели совпадает с началом года, то в этом году будет минимальное количество выходных. Если же начало года совпадает с первым выходным в неделе (в нашем понимании это суббота), то в этом году будет максимальное количество выходных дней.

670B - Game of Robots

Для решения данной задачи будем перебирать сколько идентификаторов назовут роботы в порядке слева направо. Договоримся, что будем решать эту задачу в 1-индексации. Пусть текущий робот назовёт i идентификаторов, тогда если k - i > 0 выполним k = k - i и перейдем к следующему роботу, в противном случае, выведем a[k], где a — это массив с идентификаторами роботов, и закончим алгоритм.

670C - Cinema

Воспользуемся map-ом (назовём его cnt) и насчитаем, сколько учёных говорит на каждом языке (то есть cnt[i] должно быть равно количеству учёных, которые говорят на языке номер i). Заведём пару res, в которой будем хранить количество \textit{очень довольных} учёных и количество \textit{почти довольных} учёных. Изначально выполним присвоение res = make_pair(0, 0). Переберем все фильмы, начиная с первого. Пусть текущий фильм имеет номер i. Тогда, если res < make_pair(cnt[b[i]], cnt[a[i]]), выполним присвоение res = make_pair(cnt[b[i]], cnt[c[i]]) и обновим ответ номером текущего фильма.

670D1 - Magic Powder - 1

Данную задачу с уменьшенными ограничениями можно решить следующим образом. Будем печь по одной печеньке до тех пор пока это возможно. Для каждой новой печеньки насчитаем val — сколько нужно волшебного порошка для её приготовления. Для этого переберём все ингредиенты, и для ингредиента номер i, если a[i] ≤ b[i] выполним присвоение b[i] = b[i] - a[i], в противном случае, выполним присвоение b[i] = 0 и val = val + a[i] - b[i]. После того, как мы перебрали все ингредиенты, если val > k, то больше печенек испечь мы не сможем. В противном случае, выполним присвоение k = k - val и перейдем к приготовлению следующей печеньки.

670D2 - Magic Powder - 2

Будем делать бинарный поиск по ответу. Пусть мы проверяем текущий ответ cur. Тогда целевая функция должна выглядеть следующим образом. Насчитаем в переменную cnt сколько грамм волшебного порошка нам нужно для приготовления cur печенек. Переберём все ингредиенты по очереди. Пусть текущий ингредиент имеет номер i. Тогда если a[icur > b[i] выполним присвоение cnt = cnt + a[icur - b[i]. Если после рассмотрения какого-то ингредиента cnt стало больше чем k, целевая функция должна вернуть false. Если такого не произошло ни после какого ингредиента, целевая функция должна вернуть true.

Понятно, что если целевая функция вернула true нужно сдвинуть левую границу бинпоиска в cur, иначе нужно сдвинуть правую границу.

670E - Correct Bracket Sequence Editor

Будем решать данную задачу следующим образом. Сначала с помощью stack насчитаем массив pos, где pos[i] будет означать позицию скобки, парной для скобки в позиции i. Затем заведём два массива left и right. Тогда left[i] будет равно позиции ближайшей слева относительно позиции i неудалённой скобки, а right[i] будет равно позиции ближайшей справа относительно позиции i неудалённой скобки. Если таковых скобок нет, будет хранить в соответствующей позиции в массиве число \texttt{-1}.

Пусть текущая позиция курсора равна p. Тогда при операции \texttt{L} выполним присвоение p = left[p], а при операции \texttt{R} выполним присвоение p = right[p]. Осталось научиться обрабатывать операцию \texttt{D}.

Пусть lf равно p, а rg равно pos[p]. Если lf > rg сделаем swap(lf, rg). То есть теперь мы знаем границы подстроки, которую нужно удалить. Пересчитаем сначала позицию p. Если right[rg] =  =  - 1 (то есть после удаления текущей подстроки не останется скобок справа), нужно сдвинуть p влево, то есть выполнить присвоение p = left[lf], иначе нужно выполнить присвоение p = right[rg]. Осталось только пересчитать ссылки для концов удаляемой подстроки. Здесь нужно быть аккуратным, и проверять есть ли скобки слева и справа относительно концов удаляемой подстроки.

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

670F - Restore a Number

Сначала нужно найти длину изначального числа. Для этого просто переберем её. Пусть текущая длина равна len. Тогда если len равно длине заданной строки минус количество цифр в числе len, то len это и есть длина изначального числа (то есть она определяется однозначно). Затем нужно убрать из заданной строки все цифры, которые есть в числе len, сгенерировать три строки из оставшихся цифр и выбрать из них лексикографически минимальную — это и будет ответом. Пусть t — это подстрока, которую запомнил Вася. Какие же три строки нужно сгенерировать?

  1. Записать сначала строку t, а затем все оставшиеся цифры из заданной строки в возрастающем порядке. Эта строка может быть составлена, только если t не начинается с нуля.

  2. Записать сначала наименьшую цифру из оставшихся в заданной строке отличную от нуля в начало. Если таковой нет, то такую строку составить мы не сможем. В противном случае, нужно записать все оставшиеся цифры, меньшие первой цифры в строке t в возрастающем порядке, затем дописать строку t и затем все оставшиеся цифры в возрастающем порядке.

  3. Записать сначала наименьшую цифру из оставшихся в заданной строке отличную от нуля в начало. Если таковой нет, то такую строку составить мы не сможем. В противном случае, нужно записать все оставшиеся цифры, меньшие или равные первой цифре в строке t в возрастающем порядке, затем дописать строку t и затем все оставшиеся цифры в возрастающем порядке.

Также нужно отдельно рассмотреть случай, когда число, которое передавал Вася, равно нулю.

Теги div2, editorial, 350, разбор

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru14 Русский fcspartakm 2016-05-05 21:35:00 0 (опубликовано)
ru13 Русский fcspartakm 2016-05-05 21:31:11 2
en9 Английский fcspartakm 2016-05-05 18:51:14 2620
en8 Английский fcspartakm 2016-05-05 18:27:42 2234
en7 Английский fcspartakm 2016-05-05 18:07:04 334
ru12 Русский fcspartakm 2016-05-05 18:02:23 7 Мелкая правка: 'ть правую правую гр' -> 'ть правую гр'
en6 Английский fcspartakm 2016-05-05 18:02:09 1123
en5 Английский fcspartakm 2016-05-05 17:56:59 813
en4 Английский fcspartakm 2016-05-05 17:50:53 783
en3 Английский fcspartakm 2016-05-05 17:44:46 584
en2 Английский fcspartakm 2016-05-05 17:38:10 1000
en1 Английский fcspartakm 2016-05-05 17:32:35 6507 Initial revision for English translation
ru11 Русский fcspartakm 2016-05-05 17:13:38 1749
ru10 Русский fcspartakm 2016-05-05 15:46:58 1564
ru9 Русский fcspartakm 2016-05-05 15:09:44 2 Мелкая правка: ']$, где $a[]$ &mdash; ' -> ']$, где $a$ &mdash; '
ru8 Русский fcspartakm 2016-05-05 15:04:18 1 Мелкая правка: 'ше чем $k$ целевая ф' -> 'ше чем $k$, целевая ф'
ru7 Русский fcspartakm 2016-05-05 15:03:54 3
ru6 Русский fcspartakm 2016-05-05 15:03:36 766
ru5 Русский fcspartakm 2016-05-05 14:44:25 651
ru4 Русский fcspartakm 2016-05-05 14:23:34 631
ru3 Русский fcspartakm 2016-05-05 14:10:53 382
ru2 Русский fcspartakm 2016-05-05 14:04:26 569
ru1 Русский fcspartakm 2016-05-05 13:53:08 191 Первая редакция (сохранено в черновиках)