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

AtCoder ABC 018 A&B&C AtCoder - 018

A-Mame-maki

――For some reason, I didn't want to judge one by one, so I turned it in a loop --Keep the initial index and score --Sort by score --Replace the points with the order (index) --Sort by initial index --Output the replaced order

	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-Inversion of string

	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: Minesweeper?

――The speed is slow, but I was able to AC. (At first, it was implemented in a loop, but it seems that TLE cannot be resolved, so I reconsidered it.)

――Is it just a problem statement? ?? ?? So when I actually entered the value in Excel, the following was found --Add $ (k-1) $ from the center to make a rhombus --The diamond must not contain a cross ――How many rhombuses can make the above conditions?

――It's slow because it does a full search, so I thought again if I could reduce the amount of search a little more. --The principle is how to find a safe zone for Minesweeper ――You have to search after all to fill in the numbers, but you can prun some of them, right?

Input example: 8 8 3 oooooooo oooooooo oooooooo oooooooo oxoooooo oooooooo oooooxoo oooxoooo

--Turn it into a table

--K = 3, so x must not be within 3 from the center ――It is also NG to cross the wall --Enter a value with X = 3 / wall = 2

――After that, put a value in the periphery and count the remaining 0s ――If you center the positions 1, 2 and 3, the wall will stick out or get caught in × --The 0 position can be the center

--Remarks when TLE is resolved --TLE was resolved when continue was set to break when re-searching the surrounding area (the location is commented). ――I realized that I had to consider how to stop the search properly rather than continue.

	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++) {
				/*
				 *Since X is a land mine, max and others are 0 once
				 */
				if (wk[j] == 'x') {
					dist[i][j] = k;
				} else if (i == 0 || i == r - 1 || j == 0 || j == c - 1) {
					/*
					 *Fill the one next to the wall
					 */
					dist[i][j] = k - 1;
				} else {
					dist[i][j] = 0;
				}
			}
		}
		/*
		 *Update the values at each location and check the safety zone
		 */
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				/*
				 *If you are 0, you cannot distribute it to others
				 *safe area
				 */
				if (dist[i][j] == 0) {
					continue;
				}
				allocateNum(r, c, dist, i, j);
			}
		}
		long res = 0;
		/*
		 *Count the number of safe zones
		 */
		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) {
		/*
		 *Distribute your value in all directions
		 *However, if there is already a value larger than the value calculated from your own value and distance, ignore it
		 *When distributing in all directions, you have to distribute it up to your own value, so double loop
		 */
		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) {
					/*
					 *Fixed continue to break (TLE resolved with this fix)
					 *Since we are looking from a place near the center, if there is a large value in the destination, there is no need to allocate any more
					 */
					//					continue;
					break;
				}
				/*
				 *As the distance increases, the allocation amount decreases by dLen.
				 */
				dist[wX][wY] = base - dLen;
				//I updated the value so I will distribute it again
				allocateNum(r, c, dist, wX, wY);
			}
		}
	}

C-Rhombus count: The method described in the explanation (cumulative sum?)

4 5 2 xoooo oooox ooooo oxxoo

UP side count

DOWN side count

	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++) {
				/*
				 *Center confirmed
				 *However, if it is less than k in both the vertical direction, it cannot be the center.
				 */
				if (up[i][j] < k || down[i][j] < k) {
					continue;
				}
				boolean canCnt = true;
				/*
				 *Expand your search to the left and right
				 */
				for (int l = 1; l < k; l++) {
					/*
					 *c is+Search in the direction of
					 * up/Both down satisfy the numerical value
					 */
					if (j + l >= c || up[i][j + l] < k - l || down[i][j + l] < k - l) {
						canCnt = false;
						break;
					}
					/*
					 *c is-Search in the direction of
					 * up/Both down satisfy the numerical value
					 */
					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 count: Normal loop (TLE)

-Look at whether $ (i, j) $ can be made into diamonds one by one. ――Of course, it's TLE, but you can manage to get only partial points. .. ..

	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;
		/*
		 *Both X-axis and Y-axis(k-1)Is necessary, so subtract that amount from the start and end
		 */
		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) {

		/*
		 *Left and right swing width is k-1
		 */
		int wkK = k - 1;
		/*
		 *X axis
		 * -(k-1) - 0 - (k-1)
		 */
		for (int i2 = -wkK; i2 <= wkK; i2++) {
			/*
			 *Y axis
			 * -(k-1)
			 *  -
			 *  0
			 *  -
			 * (k-1)
			 */
			for (int j2 = -wkK; j2 <= wkK; j2++) {
				int x = i + i2;
				int y = j + j2;
				/*
				 *Narrow the search range to a rhombus
				 */
				if (Math.abs(i2) + Math.abs(j2) > wkK) {
					continue;
				}
				/*
				 *Out if there is protrusion or black
				 */
				if (x < 0 || r <= x || y < 0 || c <= y || wk[x][y] == 'x') {
					return false;
				}
			}
		}
		return true;
	}