That was the problem. You actually have to explore, or else you will have to settle with a "B" rank. It usualy takes multiple time, at least in the later levels. This is much different than Sonic Generations, you HAVE to get a good time to get an A or S. You could collect 200 rings and you would still get an B if you had a bad time. Rings don't do crap in Generations, other than boost your rank by 5% or so.