AtCoder ABC 125 A&B&C&D AtCoder - 125

2019/05/22 Fügen Sie den Problemnamen hinzu

2019/06/27 Seg-Tree-Lösung für C-Problem hinzugefügt

A - Biscuit Generator

Sie können Kekse hinzufügen, die t + 0,5 Stunden nicht überschreiten

	private void solveA() {
		int a = nextInt();
		int b = nextInt();
		int t = nextInt();

		int res = 0;

		//		double time = 0;
		//		while ((time += a) <= (t + 0.5)) {
		//			res += b;
		//		}

		res = t / a * b;

		out.println(res);
	}

B - Resale

--X ist $ \ sum_ {i = 1} ^ {n} V_i $ --Y ist $ \ sum_ {i = 1} ^ {n} C_i $

Weil es der Maximalwert von $ X-Y $ ist --X sollte größer sein
Zählen Sie keine Paare mit $ V_i <C_i $

	private void solveB() {
		int numN = nextInt();
		int[] v = IntStream.range(0, numN).map(i -> nextInt()).toArray();
		int[] c = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		long res = 0;
		for (int i = 0; i < numN; i++) {
			if (v[i] > c[i]) {
				res += (v[i] - c[i]);
			}
		}

		out.println(res);
	}

C - GCD on Blackboard

Kumulative Summe

Nehmen Sie die kumulative Summe der GCD von links und rechts und schließen Sie unnötige Teile aus

position						GCD
	1	2	3	4	5	1-5 GCD
i=1		2	3	4	5	2-5 GCD
i=2	1		3	4	5	1 und 3-5 GCD
i=3	1	2		4	5	1-2 und 4-5 GCD
i=4	1	2	3		5	1-3 und 5 GCD
i=5	1	2	3	4		1-4 GCD

-Wenn $ i = 3 $, wenn Sie GCD mit GCD $ von $ 1-2 und GCD $ von $ 4-5 nehmen, ist dies die gesamte GCD. - gcd(1-2,4-5)

Um dies zu erreichen, erstellen Sie "1-5 GCD" und "5-1 GCD" und führen Sie sie zusammen.

/*
	 *Kommentarsendung
	 * https://www.youtube.com/watch?v=8lm8o8L9Bmw
	 */
	private void solveC() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		long[] forward = new long[numN];
		long[] backward = new long[numN];

		long forGcd = 0;
		long backGcd = 0;
		for (int i = 0; i < numN; i++) {
			forGcd = forward[i] = getGcd(forGcd, wk[i]);
			backGcd = backward[numN - 1 - i] = getGcd(backGcd, wk[numN - 1 - i]);
		}
		long max = 1;

		for (int i = 0; i < numN; i++) {
			if (i == 0) {
				max = Long.max(max, backward[i + 1]);
			} else if (i == numN - 1) {
				max = Long.max(max, forward[i - 1]);
			} else {
				max = Long.max(max, getGcd(forward[i - 1], backward[i + 1]));
			}
		}
		out.println(max);
	}

	private long getGcd(long num1, long num2) {
		long max = Long.max(num1, num2);
		long min = Long.min(num1, num2);
		if (min == 0) {
			return max;
		}
		long amari = max % min;

		while (amari != 0) {
			max = min;
			min = amari;
			amari = max % min;
		}
		return min;

	}

TLE

――Nun, weil es eine Erinnerung ist, ist dies auch ...

	private void solveC2() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		long maxGcd = 0;

		for (int i = 0; i < numN; i++) {
			long max = 0;
			for (int j = 0; j < numN; j++) {
				if (i == j) {
					continue;
				}
				max = getGcd(max, wk[j]);
			}
			maxGcd = Long.max(maxGcd, max);
		}
		out.println(maxGcd);
	}

Mit Seg-Baum gelöst

Referenz: Kenchons professioneller Andachtsrekord im Wettbewerb Für Sie, die einen Segmentbaum in Sora schreiben möchten Vollständige Dominanz- / Abfrageverarbeitungstechnik im Baum Datenstruktur im Programmierwettbewerb Programmierwettbewerb Challenge Book S.153 ～


	/**
	 * segment tree version
	 *
	 *Eingabewertprobe
	 * [P-1]
	 * 3
	 * 7 6 8
	 *
	 * [P-2]
	 * 6
	 * 12 3 6 9 15 11
	 *
	 */
	private void solveC3() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		SegTree tree = new SegTree(numN);

		/*
		 *Vor dem Einstellen
		 * [P-1]
		 * [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647]
		 *
		 * [P-2]
		 * [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647]
		 */
		for (int i = 0; i < wk.length; i++) {
			tree.set(i, wk[i]);
		}
		/*
		 *Unmittelbar nach Beendigung des Sets
		 * [P-1]
		 * [2147483647, 2147483647, 2147483647, 2147483647, 7, 6, 8, 2147483647]
		 *
		 * [P-2]
		 * [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 12, 3, 6, 9, 15, 11, 2147483647, 2147483647]
		 *
		 */
		tree.update();
		/*
		 *Unmittelbar nach Abschluss des Updates
		 * [P-1]
		 * [2147483647, 1, 1, 1, 7, 6, 8, 2147483647]
		 *
		 *Blatt ist ein Wert und Knoten ist eine versprochene Zahl
		 *  1( k 1)
		 *     |----------------------|
		 *     |                      |
		 *  1(2k 2)               1(2k+1 3)
		 *     |--------|             |----------|
		 *     |        |             |          |
		 *  7(2k 4) 6(2k+1 5)     8(2k 6)   2147483647(2k+1 7)
		 *
		 *
		 *  [P-2]
		 *  [2147483647, 1, 3, 1, 3, 3, 1, 2147483647, 12, 3, 6, 9, 15, 11, 2147483647, 2147483647]
		 *
		 *  1( k 1)
		 *     |----------------------------------------|
		 *     |                                        |
		 *  3(2k 2)                                  1(2k+1 3)
		 *     |-----------------|                      |------------------------|
		 *     |                 |                      |                        |
		 *  3(2k 4)            3(2k+1 5)             3(2k 6)                  2147483647(2k+1 7)
		 *     |-------|         |------------|         |----------|             |--------------------|
		 *     |       |         |            |         |          |             |                    |
		 * 12(2k 8)  3(2K+1 9)  6(2k 10)  9(2K+1 11) 15(2k 12)  11(2K+1 13)   2147483647(2k 14)    2147483647(2k+1 15)
		 */

		long res = 0;

		for (int i = 0; i < numN; i++) {
			/*
			 *Halboffener Abschnitt[)
			 * 0 - i
			 *(Ich nicht enthalten)
			 */
			long left = tree.get(0, i);
			/*
			 *Halboffener Abschnitt[)
			 * i+1 - numN(numN nicht enthalten)
			 *GCD
			 */
			long right = tree.get(i + 1, numN);
			res = Long.max(res, getGcd(left, right));

		}

		out.println(res);
	}

	/**
	 * segment tree
	 *Kompletter halber Baum
	 * @author pc9801bx2
	 *
	 */
	private static class SegTree {

		private long[] dat;
		private int numOfElmSize;
		private int numOfElm;

		private SegTree(int numOfElm) {
			this.numOfElm = numOfElm;
			numOfElmSize = 1;
			/*
			 *Größenanpassung
			 *Bestimmen der Anzahl der erforderlichen Elemente
			 *Beispiel: numOfElm==Wenn 3, dann numOfElmSize==4
			 */
			while (numOfElmSize < numOfElm) {
				numOfElmSize *= 2;
			}

			/*
			 *Array erstellen
			 * numOfElm==Wenn 3 Größe ist==8
			 */
			dat = new long[numOfElmSize * 2];
			Arrays.fill(dat, Integer.MAX_VALUE);
		}

		/**
		 *Erstellen Sie einen übergeordneten Knoten
		 */
		private void update() {
			/*
			 * segment tree
			 *Da die Blattanordnung von hinten gepackt ist, suchen Sie von hinten
			 * dat[numOfElmSize]← Blatt ganz links
			 * dat[numOfElmSize + n]← Blatt ganz rechts
			 */
			int k = numOfElmSize - 1;
			/*
			 *Zu diesem Zeitpunkt gibt es nur Daten auf den Blättern
			 *Machen Sie nacheinander vom rechten Ende des Arrays
			 */
			while (k > 0) {
				/*
				 *k Eltern
				 * K*2 linke Seite
				 * k*2+1 rechte Seite
				 *Erstellen Sie aus dem übergeordneten Blatt ganz links
				 */
				dat[k] = getInnerGcd(dat[k * 2], dat[k * 2 + 1]);
				k--;
			}

		}

		/**
		 *Wertesatz
		 *
		 * @param a
		 * @param val
		 */
		private void set(int a, int val) {
			/*
			 *Derjenige, der dem ersten Blatt entspricht
			 *Stellen Sie in der zweiten Hälfte des Arrays ein
			 *Stellen Sie es an einem Ort auf, der größer als numOfElmSize ist
			 */
			dat[a + numOfElmSize] = val;
		}

		/**
		 *
		6
		12 3 6 9 15 11
		 [2147483647, 1, 3, 1, 3, 3, 1, 2147483647, 12, 3, 6, 9, 15, 11, 2147483647, 2147483647]

		 1( k 1)
		    |----------------------------------------|
		    |                                        |
		 3(2k 2)                                  1(2k+1 3)
		    |-----------------|                      |------------------------|
		    |                 |                      |                        |
		 3(2k 4)            3(2k+1 5)             3(2k 6)                  2147483647(2k+1 7)
		    |-------|         |------------|         |----------|             |--------------------|
		    |       |         |            |         |          |             |                    |
		 12(2k 8)  3(2K+1 9)  6(2k 10)  9(2K+1 11) 15(2k 12)  11(2K+1 13)   2147483647(2k 14)    2147483647(2k+1 15)


Der Übergang, wenn i nacheinander nach rechts bewegt wird, wird unten beschrieben.
		-------------------
		 [0:0):GCD=0
		 left 8
		 right 8

		 [1:6):GCD=1
		 left 9 -> 5 -> 3
		 right 14 -> 7 -> 3
		-------------------
		 [2:6):GCD=1
		 left 10 -> 5 -> 3
		 right 14 -> 7 -> 3
		-------------------
		 [0:2):GCD=3
		 left 8 -> 4 -> 2
		 right 10 -> 5 -> 2

		 [3:6):GCD=1
		 left 11 -> 6 -> 3
		 right 14 -> 7 -> 3
		-------------------
		 [0:3):GCD=3
		 left 8 -> 4 -> 2
		 right 11 -> 5 -> 2

		 [4:6):GCD=1
		 left 12 -> 6 -> 3
		 right 14 -> 7 -> 3
		-------------------
		 [0:4):GCD=3
		 left 8 -> 4 -> 2 -> 1
		 right 12 -> 6 -> 3 -> 1

		 [5:6):GCD=11
		 left 13 -> 7
		 right 14 -> 7
		-------------------
		 [0:5):GCD=3
		 left 8 -> 4 -> 2 -> 1
		 right 13 -> 6 -> 3 -> 1

		 [6:6):GCD=0
		 left 14
		 right 14
		 */
		private long get(int a, int b) {
			long leftGcd = 0;
			long rightGcd = 0;
			int left = a + numOfElmSize;
			int right = b + numOfElmSize;
			//			System.out.println("a:b / " + a + " : " + b + " -- left : right / " + left + " : " + right);
			/*
			 *Schleife, während die Eltern anders sind
			 *Folgen Sie dem obersten Elternteil, um das maximale Engagement zu finden
			 *Wenn Sie dieselbe Blattposition angeben, wird diese nicht in die Schleife eingegeben.
			 *das ist(0,0)(n,n)Daher ist es überhaupt nicht zum Erwerb berechtigt.-> [:)
			 *Ich möchte also eher, dass 0 zurückgegeben wird.
			 */
			while (left < right) {
				/*
				 *Wenn der linke ein gerader Knoten ist, möchte ich den gesamten Bereich.
				 *Also möchte ich die Eltern bekommen, anstatt sie hier zu bekommen.
				 *Für gerade Knoten
				 *mich selber->Meine Eltern->Ungepaart direkt neben dem geraden Knoten->Übergang mit dem Elternteil auf der rechten Seite
				 ** Wenn alle gerade sind und es in der Mitte ungerade wird, gehen Sie zum Übergang von ungeraden Knoten über.
				 *
				 *Im Fall von ungeraden Knoten (die Blätter können gerade sein, aber die Knoten können ungerade sein),
				 *Ich muss nur das Kind nehmen und mich nach rechts bewegen, ohne das Elternteil zu nehmen
				 *Einzelne Werte abrufen (leftGcd==0 Mit anderen Worten, im Fall von Blättern nehmen Sie den Wert von Blättern)
				 *Übrigens leftGcd==Wenn 0, dat[i]Ist zurück gekommen.
				 *Wenn es ungerade Knoten gibt
				 *mich selber->Ungepaart direkt neben dem geraden Knoten->Übergang mit dem Elternteil auf der rechten Seite
				 */
				if ((left & 1) == 1) {
					leftGcd = getInnerGcd(leftGcd, dat[left]);
					left++;
				}
				/*
				 *Wenn der rechte ein ungerader Knoten ist, möchte ich den gesamten Bereich. .. Aber,
				 *Da es sich um einen halboffenen Abschnitt handelt, müssen Sie ihn nicht rechts lassen.
				 ** Ich nehme den numN-Teil nicht, aber gibt es ein Problem? Über,
				 *In der Tat wk[numN]Da Inf im Wert von enthalten ist, können Sie es ignorieren.
				 *
				 *Ich möchte, dass der Knoten so wie er ist zum übergeordneten Knoten wechselt(Ich möchte, dass der Wert im übergeordneten Element gespeichert wird)Also Übergang zu geraden Knoten
				 *Jetzt kannst du das nächste Mal zu deinen Eltern gehen, wenn du kommst.
				 * rightGcd==Wenn 0, dat[i]Ist zurück gekommen.
				 *Wenn es ungerade Knoten gibt
				 *mich selber->Gepaarte linke gerade Knoten->Übergang mit dem für Sie gemeinsamen Elternteil und dem linken Knoten
				 *
				 *Wenn das Recht ein gerader Knoten ist,
				 *mich selber->Übergang mit dem Elternteil
				 */
				if ((right & 1) == 1) {
					--right;
					rightGcd = getInnerGcd(rightGcd, dat[right]);
				}
				//Wählen Sie den übergeordneten Knoten aus
				left = left / 2;
				right = right / 2;
				//				System.out.println("left : right / " + left + " : " + right);
			}
			long res = getInnerGcd(leftGcd, rightGcd);
			//			System.out.println("res : " + res);
			return res;
		}

		/**
		 *GCD für SegTree
		 * @param num1
		 * @param num2
		 * @return
		 */
		private long getInnerGcd(long num1, long num2) {
			long max = Long.max(num1, num2);
			long min = Long.min(num1, num2);
			if (min == 0) {
				return max;
			}
			long amari = max % min;

			while (amari != 0) {
				max = min;
				min = amari;
				amari = max % min;
			}
			return min;

		}
	}

D - Klappschilder: Kopie löschen

――Das ist einfacher als C. .. .. Ich hätte D machen sollen, ohne zu C zu gehen. .. ..

Invertieren Sie plus und minus zwei gleichzeitig ――Wenn das Minus gerade ist, können Sie ein Paar bilden und es zu einem Plus machen
Wenn das Minus ungerade ist, können Sie kein Paar bilden
Bei einer ungeraden Zahl kann die Summe maximiert werden, indem der kleinste absolute Wert negativ gemacht wird.

`-` ist gerade

Es ist möglich, - aus der Bedingung zu entfernen, dass $ A_i und A_ {i + 1} $ ausgewählt und invertiert sind.

Muster 1

	1	2	3	4	gesamt
	-1	-2	-3	-4	-10
1,Invertieren 2	1	2	-3	-4	-4
3,Invertieren 4	1	2	3	4	10

--Pattern 2 (Auch wenn - getrennt ist, können Sie- bewegen, um es verschwinden zu lassen)

	1	2	3	4	gesamt
	-1	2	3	-4	0
1,Invertieren 2	1	-2	3	-4	-2
2,Invertieren 3	1	2	-3	-4	-4
3,Invertieren 4	1	2	3	4	10

`-` ist seltsam

Es ist unmöglich, - zu eliminieren, da $ A_i und A_ {i + 1} $ ausgewählt und invertiert sind.

Muster 1

	1	2	3	4	gesamt
	1	-2	-3	-4	-8
1,Invertieren 2	-1	2	-3	-4	-6
3,Invertieren 4	-1	2	3	4	8

--Pattern 2 (absichtlich auf einem Umweg geschrieben)

Bewegen Sie -, um die Gesamtsumme zu maximieren
Wenn es gerade ist, kann es gelöscht werden, aber wenn es seltsam ist, kann es nicht gelöscht werden. -stattdessen,-Kann auf den absoluten Mindestwert verschoben werden (in der Abbildung)|1|Zu-Bewegt sich)
Sie können das Ziel auswählen, um - hinzuzufügen
Infolgedessen kann es der gleiche Wert wie Muster 1 sein.

	1	2	3	4	gesamt
	-1	-2	-3	4	-8
1,Invertieren 2	1	2	-3	4	4
3,Invertieren 4	1	2	3	-4	2
3,Invertieren 4	1	2	-3	4	4
2,Invertieren 3	1	-2	3	4	6
1,Invertieren 2	-1	2	3	4	8

Eine andere Lösung ist nicht verständlich

	/*
	 *Prozesse zusammenführen
	 */
	private void solveD() {
		int numN = nextInt();
		int[] wk = new int[numN];

		int mCnt = 0;
		long res = 0;
		int zeroCnt = 0;
		for (int i = 0; i < numN; i++) {
			int val = nextInt();
			if (val < 0) {
				mCnt++;
			}
			if (val == 0) {
				zeroCnt++;
			}
			wk[i] = Math.abs(val);
			res += wk[i];
		}
		Arrays.sort(wk);
		if (mCnt % 2 == 0 || zeroCnt > 0) {
			out.println(res);
		} else {
			out.println(res - Math.abs(wk[0]) * 2);
		}

	}

D - Flip Signs: Eine Erinnerung an den Denkprozess

――Ich habe es umgeschrieben, weil es viel zusätzliche Verarbeitung gibt, aber vielleicht ist der Ablauf leichter zu verstehen als die obige Version mit klarer Kopie?


	/*
	 *Zum Abrufen oder Zählen können Werte zusammengeführt werden
	 */
	private void solveD2() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		int mCnt = 0;
		long res = 0;
		int zeroCnt = 0;
		for (int i = 0; i < numN; i++) {
			/*
			 *Zähle Dinge unter 0
			 */
			if (wk[i] < 0) {
				mCnt++;
			}
			/*
			 *Holen Sie sich die Gesamtsumme (abs)
			 */
			res += Math.abs(wk[i]);
			/*
			 *Zähle 0
			 */
			if (wk[i] == 0) {
				zeroCnt++;
			}
		}
		/*
		 * -Wenn ist gerade oder mindestens eine 0
		 *Alle Werte+Kann konvertiert werden zu
		 *In diesem Fall einfach addieren
		 */
		if (mCnt % 2 == 0 || zeroCnt > 0) {
			out.println(res);
			return;
		} else {
			/*
			 * -Ist eine ungerade Zahl und es gibt keine 0
			 *In diesem Fall,|wk[i]|Der kleinste Wert in-Kann maximiert werden durch
			 *Schreiben Sie alles einmal mit abs neu
			 */
			for (int i = 0; i < wk.length; i++) {
				wk[i] = Math.abs(wk[i]);
			}
			//Sortieren
			Arrays.sort(wk);
			for (int i = 0; i < wk.length; i++) {
				/*
				 *× 2 ist
				 *・ Gesamtsumme, die nicht in der Gesamtsumme enthalten sein sollte- wk[i]
				 *・ Weiter von der Gesamtsumme ohne diesen Wert-Insgesamt insgesamt- wk[i] - wk[i]
				 */
				if (wk[i] > 0) {
					out.println(res - Math.abs(wk[i]) * 2);
					return;
				}
			}
		}

	}

D Problem: DP-Lösung

--Ich verstehe nicht

Ich habe gerade versucht, das Editorial zu schreiben

Ich werde den Inhalt von dp [] [] entsprechend der Eingabe schreiben, aber ich verstehe die Bedeutung nicht. Kommen wir zurück, nachdem wir einen typischen dp-Wettbewerb durchgeführt haben.

[Eingabewert beachten]

5
10 -4 -8 -11 3

i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : 10 / dp[i][1] : -10
i:2 / dp[i][0] : 6 / dp[i][1] : 14
i:3 / dp[i][0] : 22 / dp[i][1] : 14
i:4 / dp[i][0] : 25 / dp[i][1] : 33
i:5 / dp[i][0] : 30 / dp[i][1] : 36
30

5
10 -4 -8 -11 9

i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : 10 / dp[i][1] : -10
i:2 / dp[i][0] : 6 / dp[i][1] : 14
i:3 / dp[i][0] : 22 / dp[i][1] : 14
i:4 / dp[i][0] : 25 / dp[i][1] : 33
i:5 / dp[i][0] : 34 / dp[i][1] : 42
34

5
8 8 8 8 8

i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : 8 / dp[i][1] : -8
i:2 / dp[i][0] : 16 / dp[i][1] : 0
i:3 / dp[i][0] : 24 / dp[i][1] : 8
i:4 / dp[i][0] : 32 / dp[i][1] : 16
i:5 / dp[i][0] : 40 / dp[i][1] : 24
40

5
-8 -8 -8 -8 -8

i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : -8 / dp[i][1] : 8
i:2 / dp[i][0] : 16 / dp[i][1] : 0
i:3 / dp[i][0] : 8 / dp[i][1] : 24
i:4 / dp[i][0] : 32 / dp[i][1] : 16
i:5 / dp[i][0] : 24 / dp[i][1] : 40
24

	private void solveD3() {
		int numN = nextInt();
		long[] wk = LongStream.range(0, numN).map(i -> nextInt()).toArray();

		long[][] dp = new long[numN + 1][2];
		dp[0][0] = 0;
		dp[0][1] = Integer.MIN_VALUE;

		for (int i = 0; i < numN; i++) {
			dp[i + 1][0] = Long.max(dp[i][0] + wk[i], dp[i][1] - wk[i]);
			dp[i + 1][1] = Long.max(dp[i][0] - wk[i], dp[i][1] + wk[i]);
			out.println("i:" + i + " / dp[i][0] : " + dp[i][0] + " / dp[i][1] : " + dp[i][1]);
		}
		out.println("i:" + numN + " / dp[i][0] : " + dp[numN][0] + " / dp[i][1] : " + dp[numN][1]);
		out.println(dp[numN][0]);
	}

[JAVA] ABC - 125 - A & B & C & D.