ZCon

[Turbo]

В этой теме можно обсудить ваш подход к решению этой задачи. Прошу пока не выкладывать исходники целиком. Лучше описать решение словами.

[zhengxi]

Долго тормозил и хотел решать чуть ли не на Prolog'е
Посмотрел лучшие решения, по 2-секундному времени решил, что там не решают все 500 полей, а выбирают поля побольше размером и в небольшим числом цветов и тыкают в них как попало, а на остальные отвечают N.
Сделал так же
Потом добавил решение каждого такого поля несколько раз и выбор решения с лучшим баллом. Время выросло, но баллы выросли больше.

[Stanislav Markevich]

[Turbo]

Оставлю свой комментарий по задаче. Я её не планировал делать такой, что бы работал метод как описал zhengxi. Погорячился с нижней границей для C. В целом думаю самый эффективный метод это найти поля с максимальным размером и минимальным количеством цыетов, затем выбрать цвет который встречается чаще, потом покликать все остальное оставив одно или несколько огромных одноцветных полей. =)

В английскую базу задача пойдет с другим начислением очков, а именно (C*C)/(H*W) думаю это чуток подправит ситуацию.

[Werewolf]

Самый простой и эффективный метод - собирать область одного цвета максимального размера.
Для этого сначала надо найти этот цвет, учитывая, что область может быть разорвана колонкой, которая этот цвет не содержит.
Затем сканируя поле сверху вниз, уничтожать все области, которые не содержат этот цвет, каждый раз рекурсивно проверяя, не появилось-ли новой области после уничтожения очередной.
По завершению сканирования уничтожить области выбранного вначале цвета. И опять вернуться к сканированию.

Тоже вначале пытался применить эвристику, типа создания рейтингов областей и уничтожения области с большим рейтингом за очередной ход.
Для этого подсчитываем очки, которые мы можем получить за области, лежащие выше текущей. Затем убираем текущую на тестовом поле и опять подсчитываем очки за образовавшиеся выше области. Рейтинг представлял собой разность эти очков.
Такой метод конечно же не прошел по времени )
_________________
Þá skelfur askr Yggdrasils, ok engi hlutr er þá óttalaus á himni eða jörðu.

[DAle]

[DAle]

[petrovich]

Мое первое навороченное решение с многочисленными поисками и оптимизациями не прошло по времени даже для десяти тестов. В итоге оставил банальное удаление групп всех цветов подряд кроме цвета с максимальным количеством полей. Затем --- удаление всех групп без разбора.

[zhengxi]

Ну там не совсем рандом, тоже есть tabu_color (эффективнее оказалось выбирать цвет, шариков которого больше, а не цвет максимальноо блока). И эвристики вроде преимущество убирания горизонтальных соседей а не вертикальных, наличие одинаковых шариков над и под убираемой парой, равество их цвета _tabu_color...
Но я бы это все равно назвал рандомным решением, эти эвристики позволяют поднять результат с ?40M до ?70M, но это не анализ.
Ещё - нагенерил рандомных полей, и результаты работы эвристик на них хорошо коррелировали с результатами сабмитов. То есть можно было сделать автоматический поиск эвристик, на генетических алгоритмах, например.
В исходнике есть пара таких эвристик, которые я не понимаю почему работают, но они работают и на рандомном поле и на тестовых полях на spoj