Sachverhalt:
A.
Mit Baugesuch vom 19. November 2012 beantragte X._ die Erteilung einer Baubewilligung für den Neubau eines Einfamilienhauses und Autounterstands auf Parzelle 3939 in Lenzerheide, Gemeinde Vaz/Obervaz. Innert Auflagefrist erhob die Helvetia Nostra Einsprache. Mit Entscheid vom 20. Dezember 2012 trat die Gemeinde Vaz/Obervaz auf die Einsprache der Helvetia Nostra nicht ein. Sie erteilte gleichentags mit separatem Entscheid die Baubewilligung unter Auflagen.
B.
Die dagegen erhobene Beschwerde der Helvetia Nostra wies das Verwaltungsgericht des Kantons Graubünden am 19. Februar 2013 ab. Es entschied, die Gemeinde sei zu Recht auf die Einsprache der Helvetia Nostra nicht eingetreten. Im Übrigen ging das Verwaltungsgericht davon aus, dass <ref-law> und seine Übergangsbestimmungen (<ref-law>) erst nach nach dem 1. Januar 2013 anwendbar seien. Daraus ergebe sich, dass auch in Gemeinden wie Vaz/Obervaz, in denen die kritische Grenze von 20% Zweitwohnungen überschritten sei, im Jahr 2012 noch Baubewilligungen für Zweitwohnungen nach bisherigem Recht erteilt werden könnten.
C.
Gegen den verwaltungsgerichtlichen Entscheid hat die Helvetia Nostra am 18. März 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht erhoben. Sie beantragt, der angefochtene Entscheid sei aufzuheben und die Sache zu neuem Entscheid an das Verwaltungsgericht zurückzuweisen. Eventualiter sei der angefochtene Entscheid in dem Sinne zu ändern, dass die dem Projekt des Beschwerdegegners X._ erteilte Baubewilligung aufgehoben werde.
D.
Am 22. Mai 2013 fällte das Bundesgericht die ersten Leitentscheide: Es bejahte die Beschwerdebefugnis der Helvetia Nostra (<ref-ruling>) sowie die direkte Anwendbarkeit von <ref-law> und <ref-law> ab dem 11. März 2012 (<ref-ruling> und 263).
E.
Mit Verfügung vom 8. Juli 2013 wurde dem Beschwerdegegner, der Gemeinde und dem Verwaltungsgericht Gelegenheit zur Stellungnahme eingeräumt. Alle drei haben auf eine Vernehmlassung verzichtet.

Erwägungen:
1.
Die Plafonierung des Zweitwohnungsbaus gemäss <ref-law> stellt eine Bundesaufgabe dar, die der Schonung der Natur und des heimatlichen Landschaftsbildes dient. Die nach Art. 12 Abs. 1 lit. b des Bundesgesetzes vom 1. Juli 1966 über den Natur- und Heimatschutz (NHG; SR 451) beschwerdebefugten Organisationen im Bereich des Natur- und Heimatschutzes - zu denen auch die Helvetia Nostra gehört - können daher Baubewilligungen wegen Verletzung von <ref-law> und seiner Übergangs- und Ausführungsbestimmungen anfechten (<ref-ruling> E. 11 S. 276 ff.). Das Verwaltungsgericht Graubünden hat somit die Einsprache- und Beschwerdebefugnis der Beschwerdeführerin zu Unrecht verneint.
2.
Das Verwaltungsgericht ging überdies davon aus, dass die neuen Verfassungsbestimmungen nicht anwendbar seien auf Baubewilligungen, die zwischen dem 11. März 2012 und dem 31. Dezember 2012 erstinstanzlich erteilt wurden (<ref-law> e contrario).
Das Bundesgericht hat in <ref-ruling> (E. 9-11 S. 249 ff.) entschieden, dass <ref-law> seit seinem Inkrafttreten am 11. März 2012 anwendbar ist. Zwar bedarf diese Bestimmung in weiten Teilen der Ausführung durch ein Bundesgesetz. Unmittelbar anwendbar ist sie jedoch insoweit, als sie (in Verbindung mit <ref-law>) ein Baubewilligungsverbot für Zweitwohnungen in allen Gemeinden anordnet, in denen der 20 %-Zweitwohnungsanteil bereits erreicht oder überschritten ist. Dies hat zur Folge, dass Baubewilligungen für Zweitwohnungen, die zwischen dem 11. März und dem 31. Dezember 2012 in den betroffenen Gemeinden erteilt wurden, auf Beschwerde hin aufzuheben sind.
3.
Wird ein Nichteintretensentscheid angefochten, kann das Bundesgericht in der Regel nicht selbst in der Sache entscheiden, sondern muss diese zu materieller Beurteilung an die Vorinstanz zurückweisen. Auf eine Rückweisung kann jedoch ausnahmsweise verzichtet werden, wenn das Durchlaufen der kantonalen Instanz eine leere zwecklose Formalität wäre (vgl. <ref-ruling> E. 5a/bb S. 11 mit Hinweisen).
Vorliegend ist unstreitig, dass eine Baubewilligung für Zweitwohnungen Verfahrensgegenstand darstellt, und dass der 20 % Anteil in der Gemeinde überschritten ist. Damit steht bereits fest, dass die angefochtene Baubewilligung gegen <ref-law> verstösst. Die Beschwerdeführerin hat (im Eventualantrag) die Aufhebung der Baubewilligung, und damit (sinngemäss) die Abweisung des Baugesuchs, beantragt. Der Beschwerdegegner und die Gemeinde haben sich diesem Antrag nicht widersetzt.
Unter diesen Umständen erscheint es sinnvoll, in Gutheissung des Eventualantrags der Beschwerdeführerin in der Sache zu entscheiden, d.h. die Baubewilligung und den Einspracheentscheid aufzuheben und das Baugesuch abzuweisen.
4.
Bei diesem Ausgang des Verfahrens obsiegt die Beschwerdeführerin. Der private Beschwerdegegner wird daher kosten- und entschädigungspflichtig, und zwar sowohl für das bundesrechtliche Verfahren (Art. 66 und 68 BGG) als auch für das Verfahren vor Verwaltungsgericht (Art. 66 und 68 Abs. 5 BGG).
Zwar hat der Beschwerdegegner weder vor Verwaltungsgericht noch vor Bundesgericht die Abweisung der Beschwerde beantragt. Er hat jedoch durch die Einreichung des Baugesuchs das Verfahren veranlasst und ist deshalb im vorliegenden Verfahren notwendigerweise Gegenpartei bzw. Beschwerdegegner; als solche trägt er grundsätzlich das Prozess- und Kostenrisiko (<ref-ruling> E. 3c S. 158).
Da die Beschwerdeführerin weder vor Bundesgericht noch vor Verwaltungsgericht anwaltlich vertreten war, hat sie praxisgemäss keinen Anspruch auf eine Parteientschädigung.
Die Sache wird an die Gemeinde zurückgewiesen, um die Kosten des Baubewilligungs- und Einspracheverfahrens neu zu verlegen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutheissen, und der Entscheid des Verwaltungsgerichts des Kantons Graubünden vom 19. Februar 2013 sowie die Baubewilligung und der Einspracheentscheid der Gemeinde Vaz/ Obervaz vom 20. Dezember 2012 werden aufgehoben. Das Baugesuch des Beschwerdegegners für Parzelle 3939 in Lenzerheide, Gemeinde Vaz/Obervaz, wird abgewiesen.
2.
Die Gerichtskosten von Fr. 1'000.-- für das bundesgerichtliche Verfahren und von Fr. 1'033.-- für das verwaltungsgerichtliche Verfahren werden dem Beschwerdegegner X._ auferlegt.
3.
Es werden keine Parteientschädigungen zugesprochen.
4.
Die Sache wird zur Neuverlegung der Kosten des Baubewilligungs- und Einspracheverfahrens an die Gemeinde Vaz/Obervaz zurückgewiesen.
5.
Dieses Urteil wird den Parteien, der Gemeinde Vaz/Obervaz und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 13. November 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Haag