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

AtCoder ABC 018 A&B&C AtCoder - 018

A-Mame-maki

――Pour une raison quelconque, je ne voulais pas juger un par un, alors je l'ai tourné en boucle

• Conserver l'index initial et le score --Trier par score --Remplacer les points avec l'ordre (index) --Trier par index initial --Sortir la commande remplacée

	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]);
		}

	}

Chaîne B-inversée

	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: Mine Sweeper?

――La vitesse est lente, mais j'ai pu AC. (Au début, il était implémenté en boucle, mais il semble que TLE ne puisse pas être résolu, alors je l'ai reconsidéré.)

――Est-ce juste un problème ?? ?? Ainsi, lorsque j'ai entré la valeur dans Excel, ce qui suit a été trouvé --Ajouter $ (k-1) $ du centre pour faire un diamant

• La forme du diamant ne doit pas contenir x ――Combien de diamants pouvez-vous fabriquer qui remplissent les conditions ci-dessus?

C'est lent car il effectue une recherche complète, alors j'ai pensé à nouveau si je pouvais réduire un peu plus la quantité de recherche.

• Le principe est de savoir comment trouver une zone de sécurité pour le balayeur de mines ――Vous devez chercher après tout pour remplir les chiffres, mais vous pouvez en élaguer certains, non?

Exemple d'entrée: 8 8 3 oooooooo oooooooo oooooooo oooooooo oxoooooo oooooooo oooooxoo oooxoooo

• Transformez-le en table

--K = 3, donc x ne doit pas être à moins de 3 du centre ――C'est aussi mal de traverser le mur --Entrez une valeur avec X = 3 / mur = 2

――Après cela, mettez une valeur dans la périphérie et comptez les 0 restants ――Si vous centrez les positions 1, 2 et 3, le mur dépassera ou restera coincé × --La position 0 peut être le centre

--Remarques lorsque TLE est résolu --TLE a été résolu lorsque la poursuite a été définie pour interrompre lors de la nouvelle recherche dans la zone environnante (l'emplacement est commenté) «J'ai réalisé que je devais réfléchir à la manière d'arrêter correctement la recherche plutôt que de continuer.

	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++) {
				/*
				 *Puisque X est une mine terrestre, max et tout le reste est égal à 0
				 */
				if (wk[j] == 'x') {
					dist[i][j] = k;
				} else if (i == 0 || i == r - 1 || j == 0 || j == c - 1) {
					/*
					 *Remplissez celui à côté du mur
					 */
					dist[i][j] = k - 1;
				} else {
					dist[i][j] = 0;
				}
			}
		}
		/*
		 *Mettez à jour la valeur numérique de chaque lieu et vérifiez la zone de sécurité
		 */
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				/*
				 *Si vous êtes 0, vous ne pouvez pas distribuer à d'autres
				 *zone protégée
				 */
				if (dist[i][j] == 0) {
					continue;
				}
				allocateNum(r, c, dist, i, j);
			}
		}
		long res = 0;
		/*
		 *Comptez le nombre de zones de sécurité
		 */
		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) {
		/*
		 *Distribuez votre valeur dans toutes les directions
		 *Cependant, s'il existe déjà une valeur supérieure à la valeur calculée à partir de votre propre valeur et distance, ignorez-la
		 *Lors de la distribution dans toutes les directions, vous devez le distribuer à votre propre valeur, donc double boucle
		 */
		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) {
					/*
					 *Correction de la poursuite de l'arrêt (TLE a été résolu par ce correctif)
					 *Puisque nous recherchons d'un endroit près du centre, s'il y a une grande valeur dans la destination, il n'y a pas besoin d'allocation supplémentaire
					 */
					//					continue;
					break;
				}
				/*
				 *À mesure que la distance augmente, le montant d'allocation diminue de dLen.
				 */
				dist[wX][wY] = base - dLen;
				//J'ai mis à jour la valeur pour la redistribuer
				allocateNum(r, c, dist, wX, wY);
			}
		}
	}

Comptage C-Rhombus: Méthode décrite dans l'explication (somme cumulée?)

4 5 2 xoooo oooox ooooo oxxoo

Compte de côté UP

Compte du côté DOWN

	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++) {
				/*
				 *Centre confirmé
				 *Cependant, s'il est inférieur à k dans les deux sens vertical, il ne peut pas être le centre.
				 */
				if (up[i][j] < k || down[i][j] < k) {
					continue;
				}
				boolean canCnt = true;
				/*
				 *Élargissez votre recherche à gauche et à droite
				 */
				for (int l = 1; l < k; l++) {
					/*
					 *c est+Rechercher dans le sens de
					 * up/Les deux vers le bas satisfont la valeur numérique
					 */
					if (j + l >= c || up[i][j + l] < k - l || down[i][j + l] < k - l) {
						canCnt = false;
						break;
					}
					/*
					 *c est-Rechercher dans le sens de
					 * up/Les deux vers le bas satisfont la valeur numérique
					 */
					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);
	}

Nombre de losanges C: boucle normale (TLE)

-Vérifiez si $ (i, j) $ peut être transformé en un losange un par un. «Bien sûr, c'est TLE, mais je ne parviens à obtenir que des points partiels. .. ..

	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;
		/*
		 *Axe X et axe Y(k-1)Est nécessaire, alors soustrayez ce montant du début et de la fin
		 */
		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) {

		/*
		 *La largeur d'oscillation gauche et droite est k-1
		 */
		int wkK = k - 1;
		/*
		 *Axe X
		 * -(k-1) - 0 - (k-1)
		 */
		for (int i2 = -wkK; i2 <= wkK; i2++) {
			/*
			 *Axe Y
			 * -(k-1)
			 *  -
			 *  0
			 *  -
			 * (k-1)
			 */
			for (int j2 = -wkK; j2 <= wkK; j2++) {
				int x = i + i2;
				int y = j + j2;
				/*
				 *Réduisez la plage de recherche à un diamant
				 */
				if (Math.abs(i2) + Math.abs(j2) > wkK) {
					continue;
				}
				/*
				 *Out s'il y a protrusion ou noir
				 */
				if (x < 0 || r <= x || y < 0 || c <= y || wk[x][y] == 'x') {
					return false;
				}
			}
		}
		return true;
	}