I've installed and re-installed VC++2015 couple times but had no luck.
So I tried installing all Windows update even though SP1 was already there, updated my GPU driver and pretty much did all the thing in the troubleshooting guide but it still insist that I do not have VC installed.
I'm running Windows 7 x64bit. And other specs are definitely higher than the requirement.
Launched the game and pressed new game.