There is a meta-structure to the problems that people can and do train for. I dabbled in this as a student (part of the BCS UK-wide competition winning team in .. '99 or thereabouts). You basically need to memorise "Introduction to Algorithms" http://en.wikipedia.org/wiki/Introduction_to_Algorithms , have a good practice in writing microparsers and output-formatting code (usually scanf/printf will do, sometimes you need something a bit more complicated), and have the right kind of puzzle-solving mentality.
Like Project Euler, sometimes you have to find a conceptual shortcut because the brute-force solution isn't feasible.
The BCS format involved four people and one computer, so work discipline, coding on paper, and a sort of extreme pair programming were important.
Gennady Korotkevich a.k.a "tourist" - I heard this name about ~5 years ago among my friends who are into competitive programming. Only learned of his name today. It's impressive how good he is at such a young age.
