Lifestyle is clearly a big influence here. My understanding is that generally speaking foods are not sweetened as much there, portions are smaller, and people walk a hell of a lot more. I've also heard that the quality of ingredients in general tends to be higher across the board.
The cheap food, which I ate a whole lot of, aren't even something I could consider "healthy"—lots of fried food like tempura and kara-age, along with lots of noodles—but even without restraint eating those, I still ended up losing weight without trying. Interestingly I think my diet got a lot higher in carbohydrate intake and my protein intake shrank. Probably some amount of my weight loss involved muscle loss, but my belly shrank considerably as well, so I don't think it was exclusively that.
I think I just gradually got used to eating less, stimulating myself with sugar less frequently and intensely (omg, even diet soft drinks and gum are so powerfully sweet), and being more active, and now that I'm back I realize just how much of a premium I have to pay to not get huge portions of food completely saturated with fat and sugar.