[JAVA] ABC - 018 - A & B & C.

AtCoder ABC 018 A&B&C AtCoder - 018

A-Mame-Maki

»Aus irgendeinem Grund wollte ich nicht eins nach dem anderen beurteilen, also habe ich es in einer Schleife gedreht --Halten Sie den Anfangsindex und die Punktzahl

• Nach Punktzahl sortieren
• Ersetzen Sie die Punkte durch die Reihenfolge (Index)
• Nach Anfangsindex sortieren --Geben Sie die ersetzte Bestellung aus

	private void solveA() {
		int[][] wk = new int[3][2];
		for (int i = 0; i < 3; i++) {
			wk[i] = new int[] { i, nextInt() };
		}

		Arrays.sort(wk, (x, y) -> -Integer.compare(x[1], y[1]));

		for (int i = 0; i < 3; i++) {
			wk[i][1] = i + 1;
		}

		Arrays.sort(wk, (x, y) -> Integer.compare(x[0], y[0]));

		for (int[] is : wk) {
			out.println(is[1]);
		}

	}

B-invertierte Zeichenfolge

	private void solveB() {
		char[] wk = next().toCharArray();
		int n = nextInt();
		for (int i = 0; i < n; i++) {
			int s = nextInt() - 1;
			int e = nextInt() - 1;
			while (s < e) {
				wk[s] += wk[e];
				wk[e] = (char) (wk[s] - wk[e]);
				wk[s] = (char) (wk[s] - wk[e]);
				s++;
				e--;
			}
		}

		out.println(new String(wk));
	}

C-Rhombus Count: Minenräumer?

――Die Geschwindigkeit ist langsam, aber ich konnte AC. (Zuerst wurde es in einer Schleife implementiert, aber es scheint, dass TLE nicht aufgelöst werden kann, also habe ich es mir noch einmal überlegt.)

――Ist es nur eine Problemstellung? ?? ?? Als ich den Wert tatsächlich in Excel eingegeben habe, wurde Folgendes gefunden

• Fügen Sie $ (k-1) $ von der Mitte hinzu, um einen Diamanten herzustellen
• Die Rautenform darf kein x enthalten ――Wie viele Diamanten können Sie herstellen, um die oben genannten Bedingungen zu erfüllen?

――Es ist langsam, weil es eine vollständige Suche durchführt, also dachte ich noch einmal darüber nach, ob ich den Suchaufwand etwas weiter reduzieren könnte.

• Das Prinzip ist, wie man eine sichere Zone für Mine Sweeper findet ――Sie müssen doch suchen, um die Zahlen einzugeben, aber Sie können einige davon beschneiden, oder?

Eingabebeispiel: 8 8 3 oooooooo oooooooo oooooooo oooooooo oxoooooo oooooooo oooooxoo oooxoooo

• Verwandle es in einen Tisch

--K = 3, daher darf x nicht innerhalb von 3 von der Mitte entfernt sein ――Es ist auch NG, die Mauer zu überqueren

• Geben Sie einen Wert mit X = 3 / wall = 2 ein

―― Danach geben Sie einen Wert in die Peripherie ein und zählen die verbleibenden 0 ――Wenn Sie die Positionen 1, 2 und 3 zentrieren, ragt die Wand heraus oder verfängt sich in ×

• Die 0-Position kann die Mitte sein

--Markierungen, wenn TLE behoben ist --TLE wurde behoben, als "Fortfahren" bei der erneuten Suche in der Umgebung auf "Unterbrechen" gesetzt wurde (der Ort ist kommentiert). ――Ich erkannte, dass ich überlegen musste, wie ich die Suche richtig stoppen kann, anstatt fortzufahren.

	private void solveC() {
		int r = nextInt();
		int c = nextInt();
		int k = nextInt();

		int[][] dist = new int[r][c];
		for (int i = 0; i < r; i++) {
			char[] wk = next().toCharArray();
			for (int j = 0; j < c; j++) {
				/*
				 *Da X eine Landmine ist, ist max und alles andere 0
				 */
				if (wk[j] == 'x') {
					dist[i][j] = k;
				} else if (i == 0 || i == r - 1 || j == 0 || j == c - 1) {
					/*
					 *Füllen Sie den neben der Wand
					 */
					dist[i][j] = k - 1;
				} else {
					dist[i][j] = 0;
				}
			}
		}
		/*
		 *Aktualisieren Sie den numerischen Wert jedes Ortes und überprüfen Sie die Sicherheitszone
		 */
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				/*
				 *Wenn Sie 0 sind, können Sie nicht an andere verteilen
				 *sicherer Bereich
				 */
				if (dist[i][j] == 0) {
					continue;
				}
				allocateNum(r, c, dist, i, j);
			}
		}
		long res = 0;
		/*
		 *Zählen Sie die Anzahl der sicheren Zonen
		 */
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (dist[i][j] == 0) {
					res++;
				}
			}
		}
		out.println(res);

	}

	private static final int[] dx = new int[] { 0, 0, 1, -1 };
	private static final int[] dy = new int[] { 1, -1, 0, 0 };

	private void allocateNum(int r, int c, int[][] dist, int i, int j) {
		/*
		 *Verteilen Sie Ihren Wert in alle Richtungen
		 *Wenn es jedoch bereits einen Wert gibt, der größer ist als der Wert, der aus Ihrem eigenen Wert und Ihrer Entfernung berechnet wurde, ignorieren Sie ihn
		 *Wenn Sie in alle Richtungen verteilen, müssen Sie es bis zu Ihrem eigenen Wert verteilen, also doppelte Schleife
		 */
		int base = dist[i][j];
		for (int d4 = 0; d4 < 4; d4++) {
			for (int dLen = 1; dLen <= base; dLen++) {
				int wX = i + dx[d4] * dLen;
				int wY = j + dy[d4] * dLen;

				if (wX < 0 || r <= wX || wY < 0 || c <= wY || dist[wX][wY] >= base - dLen) {
					/*
					 *Behoben, weiterhin zu brechen (TLE wurde durch diesen Fix behoben)
					 *Da wir von einem Ort in der Nähe des Zentrums aus schauen, besteht keine Notwendigkeit, mehr zuzuweisen, wenn das Ziel einen großen Wert aufweist
					 */
					//					continue;
					break;
				}
				/*
				 *Mit zunehmender Entfernung verringert sich der Zuordnungsbetrag um dLen.
				 */
				dist[wX][wY] = base - dLen;
				//Ich habe den Wert aktualisiert, damit ich ihn wieder verteilen kann
				allocateNum(r, c, dist, wX, wY);
			}
		}
	}

C-Rhombus-Zählung: In der Erklärung beschriebene Methode (kumulative Summe?)

4 5 2 xoooo oooox ooooo oxxoo

UP Seitenzahl

DOWN Seitenzahl

	private void solveC() {
		int r = nextInt();
		int c = nextInt();
		int k = nextInt();

		char[][] wk = new char[r][c];
		for (int i = 0; i < r; i++) {
			wk[i] = next().toCharArray();
		}
		int[][] up = new int[r][c];
		int[][] down = new int[r][c];

		for (int i = 0; i < c; i++) {
			int uCnt = 0;
			int dCnt = 0;
			for (int j = 0; j < r; j++) {
				if (wk[j][i] == 'o') {
					uCnt++;
				} else {
					uCnt = 0;
				}
				if (wk[r - 1 - j][i] == 'o') {
					dCnt++;
				} else {
					dCnt = 0;
				}
				up[j][i] = uCnt;
				down[r - 1 - j][i] = dCnt;
			}
		}

		long res = 0;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				/*
				 *Zentrum bestätigt
				 *Wenn es jedoch in beiden vertikalen Richtungen kleiner als k ist, kann es nicht das Zentrum sein.
				 */
				if (up[i][j] < k || down[i][j] < k) {
					continue;
				}
				boolean canCnt = true;
				/*
				 *Erweitern Sie Ihre Suche nach links und rechts
				 */
				for (int l = 1; l < k; l++) {
					/*
					 *c ist+Suche in Richtung
					 * up/Beide Daunen erfüllen den numerischen Wert
					 */
					if (j + l >= c || up[i][j + l] < k - l || down[i][j + l] < k - l) {
						canCnt = false;
						break;
					}
					/*
					 *c ist-Suche in Richtung
					 * up/Beide Daunen erfüllen den numerischen Wert
					 */
					if (j - l < 0 || up[i][j - l] < k - l || down[i][j - l] < k - l) {
						canCnt = false;
						break;
					}
				}
				if (canCnt) {
					res++;
				}
			}
		}
		out.println(res);
	}

C-Rhombus-Anzahl: Normale Schleife (TLE)

• Sehen Sie sich an, ob $ (i, j) $ einzeln in eine Diamantform gebracht werden kann. ―― Natürlich TLE, aber irgendwie können nur Teilpunkte genommen werden. .. ..

	private void solveC2() {
		int r = nextInt();
		int c = nextInt();
		int k = nextInt();

		char[][] wk = new char[r][c];
		for (int i = 0; i < wk.length; i++) {
			wk[i] = next().toCharArray();
		}
		long res = 0;
		/*
		 *Sowohl X-Achse als auch Y-Achse(k-1)Ist notwendig, also subtrahieren Sie diesen Betrag vom Anfang und Ende
		 */
		for (int i = k - 1; i < r - (k - 1); i++) {
			for (int j = k - 1; j < c - (k - 1); j++) {

				if (chkBlack(wk, k, i, j, r, c)) {
					res++;
				}

			}
		}

		out.println(res);
	}

	private boolean chkBlack(char[][] wk, int k, int i, int j, int r, int c) {

		/*
		 *Die linke und rechte Schwungbreite beträgt k-1
		 */
		int wkK = k - 1;
		/*
		 *X-Achse
		 * -(k-1) - 0 - (k-1)
		 */
		for (int i2 = -wkK; i2 <= wkK; i2++) {
			/*
			 *Y-Achse
			 * -(k-1)
			 *  -
			 *  0
			 *  -
			 * (k-1)
			 */
			for (int j2 = -wkK; j2 <= wkK; j2++) {
				int x = i + i2;
				int y = j + j2;
				/*
				 *Grenzen Sie den Suchbereich auf einen Diamanten ein
				 */
				if (Math.abs(i2) + Math.abs(j2) > wkK) {
					continue;
				}
				/*
				 *Heraus, wenn es Vorsprung oder Schwarz gibt
				 */
				if (x < 0 || r <= x || y < 0 || c <= y || wk[x][y] == 'x') {
					return false;
				}
			}
		}
		return true;
	}