This was a fun problem. I wish I spent a little more time on it. My solution and approach was pretty similar to the OP, code and write up here: https://github.com/mattdodge/538-riddler-nation

The biggest takeaway I think is that you don't even need to beat the "winning solution", you need to beat more of the general population than that solution does.