Sachverhalt:
A.
Die Z._ AG beabsichtigt, an der Fischerhäuserstrasse 61 und 67 in Schaffhausen (Parzelle Nr. 996) die bestehenden Gebäude abzubrechen und ein Mehrfamilienhaus mit Autoeinstellhalle zu bauen. Am 7. Dezember 2010 erteilte der Stadtrat Schaffhausen die Baubewilligung für den Neubau des Mehrfamilienhauses, am 10. Dezember 2010 das Bauinspektorat des Kantons Schaffhausen jene für die Autoeinstellhalle. Gegen die Baubewilligungen erhoben unter anderem A.X._ und B.X._ sowie der Heimatschutz Schaffhausen Rekurs. Mit Beschluss vom 31. Januar 2012 hiess der Regierungsrat des Kantons Schaffhausen das Rechtsmittel teilweise gut und ergänzte die Baubewilligung des Stadtrats mit der Auflage, die kurze Dachfläche des asymmetrischen Satteldachs sei im östlichen Teil so auszubilden, dass das Dachgeschoss vollständig im theoretisch möglichen symmetrischen Satteldach mit 45° Dachneigung Platz findet.
Daraufhin erhoben A.X._ und B.X._ sowie der Schweizer Heimatschutz Verwaltungsgerichtsbeschwerde beim Obergericht des Kantons Schaffhausen. Dieses vereinigte mit Entscheid vom 28. Dezember 2012 die beiden Verfahren, hiess die Beschwerden gut und hob den angefochtenen Regierungsratsbeschluss wie auch die Baubewilligungen vom 7. und 10. Dezember 2010 auf.
B.
B.a. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht vom 11. Februar 2013 beantragt die Einwohnergemeinde Schaffhausen, der Entscheid des Obergerichts sei aufzuheben und der Regierungsratsbeschluss zu bestätigen (Verfahren 1C_174/2013). Sie rügt eine Verletzung der Gemeindeautonomie.
Das Obergericht und die Baugesuchstellerin haben auf eine Vernehmlassung verzichtet. A.X._ und B.X._ sowie der Schweizer Heimatschutz beantragen die Abweisung, der Regierungsrat dagegen die Gutheissung der Beschwerde. Das ebenfalls zur Stellungnahme eingeladene kantonale Bauinspektorat hat sich nicht vernehmen lassen. Die Einwohnergemeinde Schaffhausen hält in ihrer Replik an ihren Anträgen fest.
B.b. Mit Eingabe vom 13. Februar 2013 erhebt die Z._ AG ebenfalls Beschwerde in öffentlich-rechtlichen Angelegenheiten und stellt im Wesentlichen die gleichen Anträge wie die Einwohnergemeinde Schaffhausen (Verfahren 1C_186/2013). Sie macht geltend, der Entscheid des Obergerichts verstosse gegen das Willkürverbot.
Das Obergericht hat auf eine Vernehmlassung verzichtet. Der Stadtrat und der Regierungsrat beantragen die Gutheissung der Beschwerde, A.X._ und B.X._ sowie der Schweizer Heimatschutz deren Abweisung. Das kantonale Bauinspektorat hat sich nicht vernehmen lassen. Die Z._ AG hält in ihrer Replik an ihren Anträgen fest.

Erwägungen:
1.
1.1. Die vorliegenden Beschwerden richten sich gegen denselben Entscheid und hängen inhaltlich eng zusammen. Die Verfahren 1C_174/2013 und 1C_186/2013 sind deshalb zu vereinigen.
1.2. Angefochten ist ein kantonal letztinstanzlicher Endentscheid über eine Baubewilligung. Dagegen steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (<ref-law>).
1.3. Die private Beschwerdeführerin hat am vorinstanzlichen Verfahren teilgenommen und ist als Baugesuchstellerin vom angefochtenen Entscheid besonders betroffen. Sie ist gemäss <ref-law> zur Beschwerde legitimiert.
1.4. Die beschwerdeführende Gemeinde beruft sich auf ihre Autonomie (<ref-law>) bei der Anwendung von Art. 21 der Bauordnung vom 10. Mai 2005 für die Stadt Schaffhausen (RSS 700.1; im Folgenden: BauO) und ist damit ohne Weiteres zur Beschwerde legitimiert. Es genügt hierfür, dass sie durch den angefochtenen Erlass in ihrer Stellung als Hoheitsträger berührt ist. Ob ihr die beanspruchte Autonomie tatsächlich zukommt, ist eine Frage der materiellen Beurteilung (<ref-ruling> E. 1.2 S. 45 mit Hinweisen).
1.5. Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerden ist einzutreten.
2.
2.1. Die Einwohnergemeinde Schaffhausen begründet die Rüge der Verletzung ihrer Autonomie damit, dass das Obergericht in ihren Entscheidungsspielraum bei der Auslegung der die Gebäudehöhe und Geschosszahl regelnden Vorschrift von Art. 21 Abs. 1 lit. b BauO eingegriffen habe. Art. 21 BauO hat, soweit hier von Bedeutung, folgenden Wortlaut:
Art. 21 (Gebäudehöhe, Geschosszahl)
1 In den Wohnzonen wird die Gebäudehöhe nach Anzahl der Vollgeschosse von durchschnittlich 3.00 m Höhe festgelegt. Massgebend ist die Geschosszahl auf der Talseite der Bauten.
a) [...]
b) Dachgeschosse gelten als Vollgeschoss, wenn
- die Firsthöhe oder die Fläche der Giebelfassade grösser ist als bei einem symmetrischen Satteldach mit einer Dachneigung von 45° und einem Kniestock von 60 cm,
- Dachaufbauten breiter sind als 1/3 der entsprechenden Fassade (vgl. Anhang 2 und 3).
c) Eingeschossige Aufbauten auf Flachdächern (Attika) gelten als Vollgeschoss, wenn ihre Bruttogeschossfläche mehr als 50% der Vollgeschosse beträgt.
2 [...]
2.2. Die Bundesverfassung gewährleistet die Gemeindeautonomie nach Massgabe des kantonalen Rechts (<ref-law>). Im Kanton Schaffhausen ist die Gemeindeautonomie in Art. 105 KV/SH (SR 131.223) verankert. Danach sind die Gemeinden im Rahmen von Verfassung und Gesetz befugt, sich selbst zu organisieren, ihre Behörden zu wählen, ihre Aufgaben nach eigenem Ermessen zu erfüllen, die erforderlichen Abgaben zu erheben und ihre öffentlichen Sachen selbständig zu verwalten.
Nach der Rechtsprechung sind Gemeinden in einem Sachbereich autonom, wenn das kantonale (oder eidgenössische) Recht diesen nicht abschliessend ordnet, sondern ihn ganz oder teilweise der Gemeinde zur Regelung überlässt und ihr dabei eine relativ erhebliche Entscheidungsfreiheit einräumt. Der geschützte Autonomiebereich kann sich auf die Befugnis zum Erlass oder Vollzug eigener kommunaler Vorschriften beziehen oder einen entsprechenden Spielraum bei der Anwendung kantonalen oder eidgenössischen Rechts betreffen. Der Schutz der Gemeindeautonomie setzt eine solche nicht in einem ganzen Aufgabengebiet, sondern lediglich im streitigen Bereich voraus. Im Einzelnen ergibt sich der Umfang der kommunalen Autonomie aus dem für den entsprechenden Bereich anwendbaren kantonalen Verfassungs- und Gesetzesrecht (<ref-ruling> E. 5.2 S. 244 f. mit Hinweisen).
2.3. Gemäss Art. 7 Abs. 1 des Gesetzes vom 1. Dezember 1997 über die Raumplanung und das öffentliche Baurecht im Kanton Schaffhausen (Baugesetz; SHR 700.100) können die Gemeinden unter Vorbehalt der Baubegriffe und Messweisen gemäss dem Anhang zum Baugesetz und soweit es ein überwiegendes öffentliches Interesse erfordert, in den Bauordnungen Vorschriften über eine Reihe baurechtlicher Regelungsbereiche aufstellen. Dazu gehören unter anderem die Gesamthöhen und Geschosszahlen sowie die Gebäudelängen und -breiten (Ziff. 3), die Abstände zu anderen Gebäuden und zu den Grenzen privaten Grundeigentums (Ziff. 4) sowie die Höchst- und Mindestausnützung des Baugrundes (Ziff. 5).
Das kantonale Baugesetz enthält in seinem Anhang gewisse Begriffe und Messweisen, welche insbesondere auch die Gebäudehöhe und die Geschosse betreffen (Ziff. 5 und 6 des Anhangs zum Baugesetz). Es schreibt jedoch weder eine maximale Gesamthöhe noch eine bestimmte Geschosszahl vor. Diese Bereiche sind im Wesentlichen der kommunalen Regelung überlassen, wobei den Gemeinden eine relativ erhebliche Entscheidungsfreiheit eingeräumt wird (vgl. die ebenfalls Gebäudehöhe und Geschosszahl betreffenden Ausführungen im Urteil 1C_506/2011 vom 22. Februar 2012 E. 3.1 mit Hinweis; vgl. auch etwa das Urteil 1C_53/2013 vom 7. Mai 2013 E. 5.1, wo der kommunalen Baubehörde bei der Beurteilung, welche Fassade die Hauptwohnseite im Sinne der anwendbaren Bau- und Zonenordnung ist, ein Beurteilungsspielraum und damit Autonomie zugestanden wurde). Der Einwohnergemeinde Schaffhausen kommt somit bei der Auslegung von Art. 21 BZO Autonomie zu.
2.4. Besteht Autonomie, kann sich die Gemeinde dagegen zur Wehr setzen, dass eine kantonale Behörde im Rechtsmittelverfahren die den betreffenden Sachbereich ordnenden kommunalen, kantonalen oder bundesrechtlichen Normen falsch anwendet oder ihre Prüfungsbefugnis überschreitet. Die Gemeinden können in diesem Rahmen auch geltend machen, die kantonalen Instanzen hätten die Tragweite eines Grundrechts verkannt und dieses zu Unrecht als verletzt erachtet (<ref-ruling> E. 2b S. 9; zur Publ. vorgesehenes Urteil 2C_794/2012 vom 11. Juli 2013 E. 2.1; je mit Hinweisen).
Soweit nicht die Handhabung von eidgenössischem oder kantonalem Verfassungsrecht infrage steht, prüft das Bundesgericht den Entscheid der kantonalen Behörde bei der Autonomiebeschwerde nur unter dem Gesichtswinkel der Willkür (<ref-ruling> E. 5.2 S. 245 mit Hinweisen).
3.
3.1. Die geplante Baute weist zwei Teile auf. Während sich der westliche Teil an die bestehende Häuserzeile fügt und wie diese ein längs verlaufendes Satteldach aufweist, ist das Satteldach im östlichen Teil, der die Häuserzeile abschliesst, um 90° gedreht. Das östliche Satteldach ist höher als das westliche und im Gegensatz zu diesem asymmetrisch ausgestaltet. Es steigt im Anschluss an den Westteil steil an, fällt dagegen auf der anderen Seite des Firsts mit einer Neigung von nur 10° ab. In diesem Bereich ist zudem eine Terrasse in der Form eines Dacheinschnitts vorgesehen.
Umstritten ist, ob die geplante Baute in ihrem östlichen Teil die nach Art. 36 Abs. 1 BauO zulässige Anzahl von vier Vollgeschossen einhält. Aufgrund der zweiteiligen Struktur der Baute betrachteten sowohl das Obergericht als auch dessen Vorinstanzen die beiden Gebäudeteile separat.
3.2. Das Obergericht führt aus, die beiden Gebäudeteile seien dort abzugrenzen, wo der dreigeschossige Westteil auf den viergeschossigen Ostteil treffe. Damit ergebe sich für den umstrittenen Ostteil eine Fassadenlänge von 25.5 m. Die Schmalseite dieses Teils messe am Ende der Häuserzeile 15.3 m, an der breitesten Stelle (beim Treppenhaus) 16.46 m. Der First des asymmetrischen Satteldachs stehe mithin quer zur Gebäudelängsseite.
Werde das geplante Dach im Sinne von Art. 21 Abs. 1 lit. b BauO mit einem fiktiven, symmetrischen Dach verglichen, welches mit einer Neigung von 45° und einem Kniestock von 60 cm auf das vierte Vollgeschoss gesetzt werde, so überschreite es weder dessen Firsthöhe noch dessen Giebelfassadenfläche und sei damit zulässig. Zu berücksichtigen sei indessen, dass der Dachfirst im Regelfall parallel zur Gebäudelängsseite verlaufe und dass bei einer Querstellung regelmässig grössere Ausnützungen des Dachgeschosses möglich wären. Vorliegend betrage das Verhältnis zwischen Schmal- und Längsseite 3:5 bzw. 1:1.66. Diese klare Längsausrichtung überschreite auch das bei einem Haus im "Chaletstil" Übliche. Aus diesem Grund sei die Giebelfläche des geplanten Baus mit der Fläche eines fiktiven Giebels zu vergleichen, der an der Schmalseite der Baute ansetze. Diese Fläche werde indessen klar überschritten, weshalb das fünfte Geschoss ebenfalls als Vollgeschoss zu qualifizieren sei. Dieses Resultat entspreche im Übrigen der Praxis im Kanton Zürich, wo ebenfalls vom Grundsatz ausgegangen werde, dass Dachgeschosse noch als solche erkennbar sein müssten und nicht den Eindruck eines Vollgeschosses vermitteln dürften. Dasselbe Anliegen werde in der Stadt Schaffhausen verfolgt: So dürften Dachaufbauten nicht breiter sein als 1/3 der entsprechenden Fassade, und die Bruttogeschossfläche von Attikageschossen dürfe nicht mehr als 50 % der Vollgeschosse betragen (Art. 21 Abs. 1 lit. b und c BauO). Dafür, dass beim strittigen fünften Geschoss von einem Vollgeschoss auszugehen sei, spreche schliesslich auch, dass je nach Raumaufteilung eine Bruttogeschossfläche realisiert werden könne, die nur wenig kleiner sei als diejenige des darunter liegenden Vollgeschosses.
Abschliessend prüfte das Obergericht, ob für die Baute eine Ausnahmebewilligung nach Art. 51 BauG erteilt werden könne, was es jedoch verneinte.
3.3. Mit weitgehend ähnlicher Begründung rügen die Beschwerdeführerinnen, das Obergericht habe Art. 21 Abs. 1 lit. b BauO willkürlich angewendet. Die Bestimmung, die zudem im Anhang 2 zur BauO illustriert werde, sei klar und weise auch keine Lücke auf. Das Obergericht habe eine Messweise angewendet, für die es im Gesetz keine Anhaltspunkte gebe. Wenn es argumentiere, damit liessen sich überdimensionierte Dächer verhindern, übersehe es, dass das Volumen einer Baute in der Bauordnung abschliessend auf andere Weise geregelt sei, nämlich insbesondere unter dem Titel der Ausnützungsziffer, der Gebäudeabmessungen und der Grenzabstände.
Die Beschwerdeführerinnen weisen darauf hin, dass das geplante Gebäude nicht zu hoch sei, auch nicht nach der Messweise des Obergerichts. Sie bestreiten zudem, dass die gewählte Dachgestaltung dazu führe, dass das Dachgeschoss wie ein Vollgeschoss wirke. Das oberste Geschoss sei vielmehr ohne Weiteres als Dachgeschoss erkennbar und von den unterliegenden Vollgeschossen zu unterscheiden. Darüber hinaus komme es gar nicht auf den Eindruck an. Selbst Attikageschosse dürften nach Art. 21 Abs. 1 lit. c BauO als Vollgeschosse in Erscheinung treten, sofern ihre Bruttogeschossfläche nicht mehr als 50 % der Vollgeschosse betrage. Der neue Ansatz des Obergerichts hätte diesbezüglich zur Folge, dass Attikawohnungen entgegen der genannten Bestimmung nicht mehr frei platziert werden könnten. Verfehlt sei auch das Argument, es könne nach der Berechnungsweise, wie sie die Stadt Schaffhausen angewendet habe, eine Bruttogeschossfläche realisiert werden, die nur wenig kleiner als diejenige des darunter liegenden Vollgeschosses sei. Die Bruttogeschossfläche sei in diesem Zusammenhang irrelevant, dies selbst dann, wenn man auf das äussere Erscheinungsbild abstellen wollte. Zudem überzeuge das Argument gerade im vorliegenden Fall nicht, wo das Dachgeschoss nur 75 % der Bruttogeschossfläche der Vollgeschosse aufweise.
Die Beschwerdeführerinnen kritisieren den Rückgriff des Obergerichts auf die zürcherische Rechtsprechung bzw. auf das züricherische Recht. Die Schaffhauser Bauordnung habe einen anderen Inhalt und stelle insbesondere nicht auf die Erscheinung des Gebäudes ab. Das Obergericht habe zudem lediglich die Rechtsprechung zu Attikageschossen herangezogen und dabei übersehen, dass die Schaffhauser Bauordnung zwischen solchen und Schrägdachbauten klar unterscheide (lit. b und c von Art. 21 Abs. 1 BauO). Im Gegensatz zu Attikageschossen könne bei einem Schrägdachbau das Dachgeschoss immer vom darunter liegenden Vollgeschoss unterschieden werden, was auch in der Zürcher Rechtsprechung anerkannt werde.
3.4. Es trifft zu, wie dies das Obergericht festhält, dass die Ausrichtung des Firsts nach der Breitseite des Gebäudes ein grösseres Dachgeschoss ermöglicht. Ob dies nach der Konzeption des Gesetzes als unerwünscht oder als erlaubt zu qualifizieren ist, muss durch Auslegung der anwendbaren Norm ermittelt werden. Die Rechtslage im Kanton Zürich, welche sich in verschiedener Hinsicht von jener im Kanton Schaffhausen bzw. in der Stadt Schaffhausen unterscheidet, ist dabei nicht massgeblich.
Nach dem insofern klaren Wortlaut von Art. 21 Abs. 1 lit. a BauO ist auf der Giebelseite zu messen, unabhängig von der Firstrichtung. Eine Beschränkung in der Wahl der Firstrichtung besteht somit nicht; eine solche ergibt sich im Übrigen, soweit ersichtlich, auch nicht aus anderen Bestimmungen der Bauordnung. Neben der Orientierung des Gebäudes sind nach dem Wortlaut von Art. 21 Abs. 1 lit. a BauO zudem auch das Erscheinungsbild oder die Bruttogeschossfläche unmassgeblich.
Aus dem Kontext der Bestimmung ergibt sich nichts, was darauf hindeuten würde, dass ihr Wortlaut nicht den wahren Sinn wiedergeben würde. Wie die Beschwerdeführerinnen zu Recht vorbringen, kann gemäss Art. 21 Abs. 1 lit. b BauO auch ein Attikageschoss so angeordnet werden, dass es visuell wie ein Vollgeschoss wirkt. Wenn das Verwaltungsgericht aus der Regelung von Dachaufbauten und Attikageschossen den Grundsatz ableiten will, dass Dachgeschosse nach der Bauordnung als solche erkennbar sein müssen, so überzeugt dies deshalb nicht.
Die Betrachtungsweise des Verwaltungsgerichts ist auch aus einem weiteren Grund problematisch. In der Essenz beruht sie darauf, dass ab einem bestimmten Seitenverhältnis für die Bemessung der Firsthöhe und der Fläche der Giebelfassade von der Giebelseite zur Traufseite gewechselt wird. Ab welchem Verhältnis dies der Fall sein soll, geht aus dem angefochtenen Entscheid nicht klar hervor. Da das Obergericht im Anschluss an den Hinweis auf eine Literaturmeinung, wonach ein Gebäude im "Chaletstil" mit den Proportionen von 1:1.5 nach Zürcher Recht wohl zulässig sei, festhält, das Seitenverhältnis der strittigen Baute von 1:1.66 überschreite das bei einem Haus im "Chaletstil" Übliche, scheint es davon auszugehen, dass die kritische Grenze bei 1:1.5 liegen soll. Ein solches System, bei dem ab einer bestimmten Schwelle die Bemessungsweise geändert wird, kann dazu führen, dass ein minimer Unterschied im Seitenverhältnis erhebliche Auswirkungen hinsichtlich der Geschosszahl bzw. der Dachgestaltung hat. So könnte beispielsweise - ausgehend von einem maximalen Seitenverhältnis von 1:1.5 - bei einem Gebäude A (mit quer gestelltem First) mit einer Länge von 15 m und einer Breite von 10 m die Längsseite für die Berechnung der zulässigen Gebäudehöhe und Fläche der Giebelfassade herangezogen werden, während es bei einem Gebäude B (ebenfalls mit quer gestelltem First) von 15.1 m Länge und 10 m Breite zwingend die Gebäudebreite sein müsste. Eine derartige Differenzierung ist zwar nicht a priori unsachlich, sie müsste aber in der Bauordnung ausdrücklich vorgesehen sein.
Insgesamt ist kein Grund ersichtlich, vom klaren Wortlaut von Art. 21 Abs. 1 lit. a BauO abzuweichen. Indem das Obergericht die sich an diesen haltende Auslegung der Einwohnergemeinde Schaffhausen korrigiert und durch eine gesetzlich nicht vorgesehene Messweise ergänzt hat, hat es gegen das Willkürverbot (<ref-law>) verstossen und damit auch die Gemeindeautonomie (<ref-law>) verletzt. Die Kritik der Beschwerdeführerinnen erweist sich demnach als begründet und der angefochtene Entscheid ist aufzuheben.
3.5. Im vorinstanzlichen Verfahren rügten die damaligen Beschwerdeführer auch die ungenügende städtebauliche Einordnung. Da das Obergericht die Baubewilligungen wegen Überschreiten der zulässigen Geschosszahl aufhob, setzte es sich mit dieser Frage nicht auseinander. Die Angelegenheit ist deshalb ans Obergericht zurückzuweisen, damit es die offen gebliebenen Punkte klärt und einen neuen Entscheid fällt.
4.
Die Beschwerden sind aus den genannten Gründen insofern gutzuheissen, als die Beschwerdeführerinnen die Aufhebung des angefochtenen Entscheids beantragen. In Bezug auf den darüber hinausgehenden Antrag, bereits jetzt den Beschluss des Regierungsrats bzw. die dem Verfahren zu Grunde liegenden Baubewilligungen zu bestätigen, ist die Beschwerde dagegen abzuweisen. Die Sache wird diesbezüglich zur Neubeurteilung ans Obergericht zurückgewiesen.
Bei diesem Verfahrensausgang obsiegen die Beschwerdeführerinnen im Wesentlichen. Die Gerichtskosten sind deshalb A.X._ und B.X._ sowie dem Schweizer Heimatschutz aufzuerlegen (<ref-law>). Diese haben der privaten Beschwerdeführerin zudem eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG). Dabei ist zu berücksichtigen, dass der vorinstanzliche Entscheid auf einer Gesetzesauslegung beruht, die im vorangegangenen kantonalen Verfahren nicht zur Diskussion stand, und die Beschwerde ans Bundesgericht deshalb einen erhöhten Begründungsaufwand erforderte. Die Einwohnergemeinde Schaffhausen hat keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Verfahren 1C_174/2013 und 1C_186/2013 werden vereinigt.
2.
Die Beschwerden werden insofern gutgeheissen, als damit die Aufhebung des angefochtenen Entscheids beantragt wird. Die Sache wird zur neuen Beurteilung ans Obergericht des Kantons Schaffhausen zurückgewiesen. Im Übrigen werden die Beschwerden abgewiesen.
3.
Die Gerichtskosten des bundesgerichtlichen Verfahrens von Fr. 5'000.-- werden A.X._ und B.X._ sowie dem Schweizer Heimatschutz auferlegt.
4.
A.X._ und B.X._ sowie der Schweizer Heimatschutz haben die private Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 6'000.-- zu entschädigen.
5.
Dieses Urteil wird den Parteien, dem Planungs- und Naturschutzamt / Bauinspektorat des Kantons Schaffhausen, dem Regierungsrat des Kantons Schaffhausen, dem Stadtrat Schaffhausen und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 6. Februar 2014
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold