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

AtCoder ABC 020 A&B&C AtCoder - 020

** 16.05.2019 ** - Hinzufügung des Problemnamens

Ein Quiz

	private void solveA() {
		int n = nextInt();

		out.println(n == 1 ? "ABC" : "chokudai");
	}

B - Takahashi-Kun- und Zeichenkettenkomprimierung

	private void solveB() {
		String res = IntStream.range(0, 2).mapToObj(i -> next()).collect(Collectors.joining());

		out.println(Integer.parseInt(res) * 2);
	}

C - Wand durch: AC mit DFS (Memo Recursive)

Die hypothetische Lösung lautet wie folgt

1. Kürzeste Routenberechnung mit Worshall Floyd / Bellmanford / Dyxtra
2. Eingrenzen Sie t durch Dichotomie

Zuerst habe ich genauso darüber nachgedacht wie die angenommene Lösungsmethode, also habe ich sie mit Worshall Floyd implementiert, aber obwohl sie die Probe oder meinen angenommenen Testfall durchläuft, wird ungefähr ein Viertel WA, wenn ich sie tatsächlich dem Richter vorwerfe. Ich kenne den Grund für WA nicht, also habe ich aufgegeben und es mit DFS implementiert. Ich muss es irgendwo wieder mit der angenommenen Lösungsmethode lösen. 　 ** Wenn Sie ein Worshall Floyd sind, sagen Sie mir bitte, dass jemand wirklich auf die Quelle schaut und WA wird **

Ein Memorandum bei Implementierung mit Memokonvertierung (TLE-Gegenmaßnahmen)

――Einige der für selbstverständlich gehaltenen Implementierungsmethoden sind langsamer als erwartet. ――Erstens war es die ganze Zeit TLE. Als Ergebnis der Überprüfung beim Ändern eines Codes konnte TLE sofort aufgelöst werden, indem nur Folgendes gestoppt wurde (während des Änderns kann es ohne Rückgabewert ungültig sein. Es war jedoch auch auf subtile Weise wirksam, es für nichtig zu erklären.

• Stoppen Sie mit Long # min () --Dramatisch verbessert, wenn das Memo aktualisiert wird (dist [] []) und der Vergleich des Memoinhalts um min --TLE kann behoben werden, indem die Quelle so geändert wird, dass beim Aktualisieren des Werts von dist [] [] nicht mehr Long # min () angezeigt wird (sodass Sie nicht min () ausführen müssen.)

	private void solveC() {
		int h = nextInt();
		int w = nextInt();
		long t = nextLong();
		char[][] wk = new char[h][w];

		int sX = 0;
		int sY = 0;
		int gX = 0;
		int gY = 0;
		for (int i = 0; i < wk.length; i++) {
			wk[i] = next().toCharArray();
			for (int j = 0; j < wk[i].length; j++) {
				if (wk[i][j] == 'S') {
					sX = i;
					sY = j;
				} else if (wk[i][j] == 'G') {
					gX = i;
					gY = j;
				}
			}
		}
		long low = 1;
		long high = t;
		long[][] memo = new long[h][w];

		while (high - low != 1) {
			long mid = (high + low) / 2;
			for (long[] l : memo) {
				Arrays.fill(l, Long.MAX_VALUE);
			}
			dfsC(wk, h, w, t, sX, sY, mid, 0, memo, new boolean[h][w]);
			if (memo[gX][gY] <= t) {
				low = mid;
			} else {
				high = mid;
			}
		}

		out.println(low);
	}


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

	private void dfsC(char[][] wk, int h, int w, long t, int currentH, int currentW, long x, long val,
			long[][] dist, boolean[][] pass) {

		/*
		 *Suchbereich überschreiten
		 *Oder
		 *Bereits gesucht
		 */
		if (currentH < 0 || currentH >= h || currentW < 0 || currentW >= w || pass[currentH][currentW]) {
			return;
		}

		/*
		 *Keine weitere Suche erforderlich, wenn der aktuelle Wert kleiner als der bereits vorhandene Wert ist
		 *Keine weitere Suche erforderlich, wenn der aktuelle Wert t überschreitet
		 */
		if (dist[currentH][currentW] < val || val > t) {
			return;
		} else {
			/*
			 *Aktualisieren Sie den Wert, da es sich um ein Suchziel handelt
			 *Ich möchte es wirklich auf min setzen, aber ich kann es nicht rechtzeitig schaffen
			 */
			dist[currentH][currentW] = val;
		}
		/*
		 *Weil es G ist, endet es
		 */
		if (wk[currentH][currentW] == 'G' || (val > 0 && wk[currentH][currentW] == 'S')) {
			return;
		}
		pass[currentH][currentW] = true;
		/*
		 *Suche in 4 Richtungen
		 */
		for (int i = 0; i < 4; i++) {
			int wkH = currentH + dx[i];
			int wkW = currentW + dy[i];
			if (wkH < 0 || wkH >= h || wkW < 0 || wkW >= w) {
				continue;
			}
			long currVal = 0;
			switch (wk[wkH][wkW]) {
			case 'S':
			case 'G':
			case '.':
				currVal = 1;
				break;
			case '#':
				currVal = x;
				break;
			default:
				break;
			}

			dfsC(wk, h, w, t, wkH, wkW, x, val + currVal, dist, pass);
		}
		pass[currentH][currentW] = false;
	}