Wednesday, 16 September 2009

skiminok: (Compas)
Судя по всему, из трёх возможных подраундов первого раунда Google Code Jam я выбрал самый жёсткий. Или оно просто так исторически сложилось: раунд был как раз по временной зоне на европейскую и постсоветскую аудиторию =) По крайней мере, часть моих знакомых его успешно завалили, после чего на следующий день в 1С показали просто высший класс. Ладно, идём по порядку.

Задача А. Тупая, вся проблема задачи опять заключалась в текстовом парсинге. И опять у человека тяжёлый выбор: осуществлять ударный посимвольный разбор дерева решений, или попытаться найти способ поэлегантнее. Я, как всегда, предпочел регекспы =) Кстати говоря, я их структуру знаю не настолько хорошо, чтобы выяснить, возможно ли с их помощью описать в общем виде правильное скобочное выражение. Следуя чистой теории формальных языков — можно, наверное. В общем, как-нибудь надо будет особые возможности синтаксиса подучить поподробнее. Пока что я прекрасно обхожусь ^, $, +, *, ?, [] (с отрицанием), (), |, ., символьными классами и нумерованными группами. И хватает с головой. Тем не менее, разделение двух деревьев решений в рекурсивной функции анализа строки я писал вручную, подсчитывая баланс скобок до нуля.

Задача B. Минус в карму C# =) Идея в том, чтобы капельку заставить человека подумать головой, а потом разделить аудиторию на три естественные категории: те, кто умеет писать next_permutation(), те, кто этого делать не умеет, и те, кто его тупо вызывают из STL)) В самом деле, на С++ основная логика решения задачи выглядит следующим образом:
deque<char> f;
/* Считывание входного числа в f */
f.push_front('0');
next_permutation(f.begin(), f.end());
if (f.front() == '0') f.pop_front();

Ваш покорный слуга плюсами не пользовался в силу нелюбви и плохо набитых рук, писал получение следующей перестановки собственными силами, за что и поплатился одной неправильной попыткой сдачи смолл-теста (перепутал < и <= ). *Впрочем, особо на результат это не повлияло, и так в следующий тур спокойно прорвался.* Кстати сказать, самые быстрые цппшники сдавали эту задачу через 4 минуты после начала контеста.

Задача С. Вот это уже интересно. Это уже надо думать, по крайней мере. Если бы у меня оставалось больше, чем полчаса — мог бы таки пораскинуть мозгами и намутить тот несчастный BFS или Дейкстру на графе этого арифметически-мозголомного квадрата и решить хотя бы смолл-тест. Но не судьба.

Ну ничего, впереди раунд 2. *что-то мне подсказывает, что для меня он станет последним: пробиться из 3000 сильнейшних в 500 уже задачка уровня мега* Google Code Jam плавно вступает в свою самую хардкорную стадию) Гудлак & хевфан ;)

Profile

skiminok: (Default)
skiminok

Most Popular Tags

Page Summary

July 2011

S M T W T F S
     12
3456789
10111213141516
17181920212223
242526272829 30
31