Хороший вопрос, поддерживаю. Лично я участвовал один раз, впрочем, не очень плохо. Решал такую задачу. Пользовался генетическим алгоритмом. Ключевым моментом была скорость создания новых особей - соптимайзив ее почти до максимума, получилось добраться из середины почти до top10. В этом помогли, во-первых, некоторые навыки ДП (как ни странно) и, во-вторых, большое количество эвристик. Ассемблерных вставок и прочих извращений не использовал, хотя и STL тоже. Так что этот метод может быть вполне юзабельным.

а можно поконкретнее? как пользовался генетическим алгоритмом? .. или мне почитать про эти алгоритмы и всё станет ясно?? .. просто я открыл вики, и мне показалось что там как-то совсем абстрактно про это. разве нет?

этот вопрос задай лучше Андрею Лопатину, он аццкий батька в этом деле))))

Сам в Марафонах никогда хорошо не участвовал.
Общался с одним чуваком, который на них неплохо укатывал, и один раз был в шаге от ТЦО. Он использует всегда генетические алгоритмы.

Я думаю на самом деле что большинство участников используют генетические алгоритмы. Но я не изучал вопрос - это только предположение.

Ну, в любом случае, после каждого марафона в разделе, ему посвященном, открывается тема "Post your approach", где можно ознакомиться с идеями лидеров

Из моего не слишком большого опыта в марафонах(12 контестов) сложилось следующее впечатление: есть два больших класса задач: оптимизационные(где надо что-нибудь минимизировать/максимизировать и есть возможность оценки своего решения) и всё остальное.
В оптимизационных задачах обычно используют стандартные методы(генетические алгоритмы, имитация отжига и т.п.), а для прохождения в топ нужно использовать всяческие умные ускорения, как асимптотические, так и неасимптотические, и различные эвристики. Такими были, например, первые два раунда последнего ТСО. Еще был случай(Nasa Topcoder Challenge), когда очень и очень неплохие результаты давала обычная динамика. Но всё-таки к таким задачам подход вполне однообразный.
Среди остальных же задач встречается всякое, различные ИИ, дешифрование, поиск различных вещей , ну и вообще почти всё что угодно:) Здесь нужно хорошенько поработать над задачей и искать интересные идеи. Для меня показателен пример контеста про разбитую плитку, где можно было получить баллов 90 из 100 максимальных просто рассмотрев, как строятся тесты, и сделав соответственный прекалк.
Вообще, обычно в марафонах рулят хорошие свои идеи, стандартные алгоритмы если и встречаются, то только как кусочек задачи. Поэтому подход к каждой задачке свой, хотя, думаю, опыт "красных" тоже им неплохо помогает:)