Simulation-based reinforcement learning approaches are leading the next innovations in legged robot control. However, the resulting control policies are still not applicable on soft and deformable terrains, especially at high speed. The primary reason is that reinforcement learning approaches, in general, are not effective beyond the data distribution: The agent cannot perform well in environments that it has not experienced. To this end, we introduce a versatile and computationally efficient granular media model for reinforcement learning. Our model can be parameterized to represent diverse types of terrain from very soft beach sand to hard asphalt. In addition, we introduce an adaptive control architecture that can implicitly identify the terrain properties as the robot feels the terrain. The identified parameters are then used to boost the locomotion performance of the legged robot. We applied our techniques to the Raibo robot, a dynamic quadrupedal robot developed in-house. The trained networks demonstrated high-speed locomotion capabilities on deformable terrains: The robot was able to run on soft beach sand at 3.03 meters per second although the feet were completely buried in the sand during the stance phase. We also demonstrate its ability to generalize to different terrains by presenting running experiments on vinyl tile flooring, athletic track, grass, and a soft air mattress.